Header Ads Widget

Circular Doubly Linked List

Circular doubly linked list is a more complexed type of data structure in which a node contain pointers to its previous node as well as the next node. Circular doubly linked list doesn't contain NULL in any of the node. The last node of the list contains the address of the first node of the list. The first node of the list also contain address of the last node in its previous pointer.

A circular doubly linked list is shown in the following figure.


Circular Doubly Linked List

Due to the fact that a circular doubly linked list contains three parts in its structure therefore, it demands more space per node and more expensive basic operations. However, a circular doubly linked list provides easy manipulation of the pointers and the searching becomes twice as efficient.

Memory Management of Circular Doubly linked list

The following figure shows the way in which the memory is allocated for a circular doubly linked list. The variable head contains the address of the first element of the list i.e. 1 hence the starting node of the list contains data A is stored at address 1. Since, each node of the list is supposed to have three parts therefore, the starting node of the list contains address of the last node i.e. 8 and the next node i.e. 4. The last node of the list that is stored at address 8 and containing data as 6, contains address of the first node of the list as shown in the image i.e. 1. In circular doubly linked list, the last node is identified by the address of the first node which is stored in the next part of the last node therefore the node which contains the address of the first node, is actually the last node of the list.

Circular Doubly Linked List

Operations on circular doubly linked list :

There are various operations which can be performed on circular doubly linked list. The node structure of a circular doubly linked list is similar to doubly linked list. However, the operations on circular doubly linked list is described in the following table.

SNOperationDescription
1Insertion at beginning
Adding a node in circular doubly linked list at the beginning.
2Insertion at end
Adding a node in circular doubly linked list at the end.
3Deletion at beginning
Removing a node in circular doubly linked list from beginning.
4Deletion at end
Removing a node in circular doubly linked list at the end.

Traversing and searching in circular doubly linked list is similar to that in the circular singly linked list.

C program to implement all the operations on circular doubly linked list

  1. #include<stdio.h>  
  2. #include<stdlib.h>  
  3. struct node  
  4. {  
  5.     struct node *prev;  
  6.     struct node *next;  
  7.     int data;  
  8. };  
  9. struct node *head;  
  10. void insertion_beginning();  
  11. void insertion_last();  
  12. void deletion_beginning();  
  13. void deletion_last();  
  14. void display();  
  15. void search();  
  16. void main ()  
  17. {  
  18. int choice =0;  
  19.     while(choice != 9)  
  20.     {  
  21.         printf("\n*********Main Menu*********\n");  
  22.         printf("\nChoose one option from the following list ...\n");  
  23.         printf("\n===============================================\n");  
  24.         printf("\n1.Insert in Beginning\n2.Insert at last\n3.Delete from Beginning\n4.Delete from last\n5.Search\n6.Show\n7.Exit\n");  
  25.         printf("\nEnter your choice?\n");  
  26.         scanf("\n%d",&choice);  
  27.         switch(choice)  
  28.         {  
  29.             case 1:  
  30.             insertion_beginning();  
  31.             break;  
  32.             case 2:  
  33.                     insertion_last();  
  34.             break;  
  35.             case 3:  
  36.             deletion_beginning();  
  37.             break;  
  38.             case 4:  
  39.             deletion_last();  
  40.             break;  
  41.             case 5:  
  42.             search();  
  43.             break;  
  44.             case 6:  
  45.             display();  
  46.             break;  
  47.             case 7:  
  48.             exit(0);  
  49.             break;  
  50.             default:  
  51.             printf("Please enter valid choice..");  
  52.         }  
  53.     }  
  54. }  
  55. void insertion_beginning()  
  56. {  
  57.    struct node *ptr,*temp;   
  58.    int item;  
  59.    ptr = (struct node *)malloc(sizeof(struct node));  
  60.    if(ptr == NULL)  
  61.    {  
  62.        printf("\nOVERFLOW");  
  63.    }  
  64.    else  
  65.    {  
  66.     printf("\nEnter Item value");  
  67.     scanf("%d",&item);  
  68.     ptr->data=item;  
  69.    if(head==NULL)  
  70.    {  
  71.       head = ptr;  
  72.       ptr -> next = head;   
  73.       ptr -> prev = head;   
  74.    }  
  75.    else   
  76.    {  
  77.        temp = head;   
  78.     while(temp -> next != head)  
  79.     {  
  80.         temp = temp -> next;   
  81.     }  
  82.     temp -> next = ptr;  
  83.     ptr -> prev = temp;  
  84.     head -> prev = ptr;  
  85.     ptr -> next = head;  
  86.     head = ptr;  
  87.    }  
  88.    printf("\nNode inserted\n");  
  89. }  
  90.      
  91. }  
  92. void insertion_last()  
  93. {  
  94.    struct node *ptr,*temp;  
  95.    int item;  
  96.    ptr = (struct node *) malloc(sizeof(struct node));  
  97.    if(ptr == NULL)  
  98.    {  
  99.        printf("\nOVERFLOW");  
  100.    }  
  101.    else  
  102.    {  
  103.        printf("\nEnter value");  
  104.        scanf("%d",&item);  
  105.         ptr->data=item;  
  106.        if(head == NULL)  
  107.        {  
  108.            head = ptr;  
  109.            ptr -> next = head;   
  110.            ptr -> prev = head;   
  111.        }  
  112.        else  
  113.        {  
  114.           temp = head;  
  115.           while(temp->next !=head)  
  116.           {  
  117.               temp = temp->next;  
  118.           }  
  119.           temp->next = ptr;  
  120.           ptr ->prev=temp;  
  121.           head -> prev = ptr;  
  122.       ptr -> next = head;  
  123.         }  
  124.    }  
  125.      printf("\nnode inserted\n");  
  126. }  
  127.   
  128. void deletion_beginning()  
  129. {  
  130.     struct node *temp;  
  131.     if(head == NULL)  
  132.     {  
  133.         printf("\n UNDERFLOW");  
  134.     }  
  135.     else if(head->next == head)  
  136.     {  
  137.         head = NULL;   
  138.         free(head);  
  139.         printf("\nnode deleted\n");  
  140.     }  
  141.     else  
  142.     {  
  143.         temp = head;   
  144.         while(temp -> next != head)  
  145.         {  
  146.             temp = temp -> next;  
  147.         }  
  148.         temp -> next = head -> next;  
  149.         head -> next -> prev = temp;  
  150.         free(head);  
  151.         head = temp -> next;  
  152.     }  
  153.   
  154. }  
  155. void deletion_last()  
  156. {  
  157.     struct node *ptr;  
  158.     if(head == NULL)  
  159.     {  
  160.         printf("\n UNDERFLOW");  
  161.     }  
  162.     else if(head->next == head)  
  163.     {  
  164.         head = NULL;   
  165.         free(head);   
  166.         printf("\nnode deleted\n");  
  167.     }  
  168.     else   
  169.     {  
  170.         ptr = head;   
  171.         if(ptr->next != head)  
  172.         {  
  173.             ptr = ptr -> next;   
  174.         }  
  175.         ptr -> prev -> next = head;  
  176.         head -> prev = ptr -> prev;    
  177.         free(ptr);  
  178.         printf("\nnode deleted\n");  
  179.     }  
  180. }  
  181.   
  182. void display()  
  183. {  
  184.     struct node *ptr;  
  185.     ptr=head;  
  186.     if(head == NULL)  
  187.     {  
  188.         printf("\nnothing to print");  
  189.     }     
  190.     else  
  191.     {  
  192.         printf("\n printing values ... \n");  
  193.           
  194.         while(ptr -> next != head)  
  195.         {  
  196.           
  197.             printf("%d\n", ptr -> data);  
  198.             ptr = ptr -> next;  
  199.         }  
  200.         printf("%d\n", ptr -> data);  
  201.     }  
  202.               
  203. }  
  204.   
  205. void search()  
  206. {  
  207.     struct node *ptr;  
  208.     int item,i=0,flag=1;  
  209.     ptr = head;   
  210.     if(ptr == NULL)  
  211.     {  
  212.         printf("\nEmpty List\n");  
  213.     }  
  214.     else  
  215.     {   
  216.         printf("\nEnter item which you want to search?\n");   
  217.         scanf("%d",&item);  
  218.         if(head ->data == item)  
  219.         {  
  220.         printf("item found at location %d",i+1);  
  221.         flag=0;  
  222.         }  
  223.         else   
  224.         {  
  225.         while (ptr->next != head)  
  226.         {  
  227.             if(ptr->data == item)  
  228.             {  
  229.                 printf("item found at location %d ",i+1);  
  230.                 flag=0;  
  231.                 break;  
  232.             }   
  233.             else  
  234.             {  
  235.                 flag=1;  
  236.             }  
  237.             i++;  
  238.             ptr = ptr -> next;  
  239.         }  
  240.         }  
  241.         if(flag != 0)  
  242.         {  
  243.             printf("Item not found\n");  
  244.         }  
  245.     }     
  246.           
  247. }  

Output:

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit

Enter your choice?
1

Enter Item value123

Node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit

Enter your choice?
2

Enter value234

node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit

Enter your choice?
1

Enter Item value90

Node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit

Enter your choice?
2

Enter value80

node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit

Enter your choice?
3

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit

Enter your choice?
4

node deleted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit

Enter your choice?
6

 printing values ... 
123

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit

Enter your choice?
5

Enter item which you want to search?
123
item found at location 1
*********Main Menu*********

Choose one option from the following list ...

============================================

1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit

Enter your choice?
7

Post a Comment

0 Comments