C++ Program To Implement Circular Doubly Linked List

«
»
This C++ Program demonstrates circular doubly linked list.

Here is source code of the C++ Program to demonstrate circular doubly linked list. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Implement Circular Doubly Linked List
  3.  */
  4. #include<iostream>
  5. #include<cstdio>
  6. #include<cstdlib>
  7. using namespace std;
  8.  
  9. /*
  10.  * Node Declaration
  11.  */
  12. struct node
  13. {
  14.     int info;
  15.     struct node *next;
  16.     struct node *prev;
  17. }*start, *last;
  18. int counter = 0;
  19. /*
  20.  * Class Declaration
  21.  */
  22. class double_clist
  23. {
  24.     public:
  25.         node *create_node(int);
  26.         void insert_begin();
  27.         void insert_last();
  28.         void insert_pos();
  29.         void delete_pos();
  30.         void search();
  31.         void update();
  32.         void display();
  33.         void reverse();
  34.         void sort();
  35.         double_clist()
  36.         {
  37.             start = NULL;
  38.             last = NULL;			
  39.         }
  40. };
  41.  
  42. /*
  43.  * Main: Contains Menu
  44.  */
  45. int main()
  46. {
  47.     int choice;
  48.     double_clist cdl;
  49.     while (1)
  50.     {
  51.         cout<<"\n-------------------------------"<<endl;
  52.         cout<<"Operations on Doubly Circular linked list"<<endl;
  53.         cout<<"\n-------------------------------"<<endl;         
  54.         cout<<"1.Insert at Beginning"<<endl;
  55.         cout<<"2.Insert at Last"<<endl;
  56.         cout<<"3.Insert at Position"<<endl;
  57.         cout<<"4.Delete at Position"<<endl;
  58.         cout<<"5.Update Node"<<endl;
  59.         cout<<"6.Search Element"<<endl;
  60.         cout<<"7.Sort"<<endl;
  61.         cout<<"8.Display List"<<endl;
  62.         cout<<"9.Reverse List"<<endl;
  63.         cout<<"10.Exit"<<endl;
  64.         cout<<"Enter your choice : ";
  65.         cin>>choice;
  66.         switch(choice)
  67.         {
  68.         case 1:
  69.             cdl.insert_begin();
  70.             break;
  71.         case 2:
  72.             cdl.insert_last();
  73.             break;   
  74.         case 3:
  75.             cdl.insert_pos();
  76.             break; 
  77.         case 4:
  78.             cdl.delete_pos();
  79.             break;
  80.         case 5:
  81.             cdl.update();
  82.             break;
  83.         case 6:
  84.             cdl.search();
  85.             break;
  86.         case 7:
  87.             cdl.sort();
  88.             break;
  89.         case 8:
  90.             cdl.display();
  91.             break;
  92.         case 9:
  93.             cdl.reverse();
  94.             break;
  95.         case 10:
  96.             exit(1); 
  97.         default:
  98.             cout<<"Wrong choice"<<endl;	
  99.         }
  100.     }
  101.     return 0;
  102. }
  103.  
  104. /*
  105.  *MEMORY ALLOCATED FOR NODE DYNAMICALLY
  106.  */
  107. node* double_clist::create_node(int value)
  108. {
  109.     counter++;  
  110.     struct node *temp;
  111.     temp = new(struct node);
  112.     temp->info = value;
  113.     temp->next = NULL;
  114.     temp->prev = NULL;
  115.     return temp;
  116. }
  117. /*
  118.  *INSERTS ELEMENT AT BEGINNING
  119.  */
  120. void double_clist::insert_begin()
  121. {
  122.     int value;
  123.     cout<<endl<<"Enter the element to be inserted: ";
  124.     cin>>value;
  125.     struct node *temp;
  126.     temp = create_node(value);
  127.     if (start == last && start == NULL)
  128.     {    
  129.         cout<<"Element inserted in empty list"<<endl;
  130.         start = last = temp;
  131.         start->next = last->next = NULL;
  132.         start->prev = last->prev = NULL;
  133.     }
  134.     else
  135.     {
  136.         temp->next = start;
  137.         start->prev = temp;
  138.         start = temp;
  139.         start->prev = last;
  140.         last->next = start;
  141.         cout<<"Element inserted"<<endl;
  142.     }
  143. }
  144.  
  145. /*
  146.  *INSERTS ELEMNET AT LAST
  147.  */
  148. void double_clist::insert_last()
  149. {
  150.     int value;    
  151.     cout<<endl<<"Enter the element to be inserted: ";
  152.     cin>>value; 
  153.     struct node *temp;
  154.     temp = create_node(value);
  155.     if (start == last && start == NULL)
  156.     {
  157.         cout<<"Element inserted in empty list"<<endl;
  158.         start = last = temp;
  159.         start->next = last->next = NULL;    
  160.         start->prev = last->prev = NULL;
  161.     }
  162.     else
  163.     {
  164.         last->next = temp;
  165.         temp->prev = last;
  166.         last = temp;
  167.         start->prev = last;
  168.         last->next = start;
  169.     }
  170. }
  171. /*
  172.  *INSERTS ELEMENT AT POSITION
  173.  */
  174. void double_clist::insert_pos()
  175. {    
  176.     int value, pos, i;
  177.     cout<<endl<<"Enter the element to be inserted: ";
  178.     cin>>value;
  179.     cout<<endl<<"Enter the postion of element inserted: ";
  180.     cin>>pos;
  181.     struct node *temp, *s, *ptr;
  182.     temp = create_node(value);
  183.     if (start == last && start == NULL)
  184.     {
  185.         if (pos == 1)
  186.         {
  187.             start = last = temp;
  188.             start->next = last->next = NULL;    
  189.             start->prev = last->prev = NULL;
  190.         }
  191.         else
  192.         {
  193.             cout<<"Position out of range"<<endl;
  194.             counter--;
  195.             return;
  196.         }
  197.     }  
  198.     else
  199.     {
  200.         if (counter < pos)
  201.         {
  202.              cout<<"Position out of range"<<endl;
  203.              counter--;
  204.              return;   		
  205.         }
  206.         s = start;		
  207.         for (i = 1;i <= counter;i++)
  208.         {
  209.             ptr = s;
  210.             s = s->next;
  211.             if (i == pos - 1)
  212.             {
  213.                 ptr->next = temp;
  214.                 temp->prev = ptr;
  215.                 temp->next = s;
  216.                 s->prev = temp;
  217.                 cout<<"Element inserted"<<endl;
  218.                 break;
  219.             }
  220.         }
  221.     }
  222. }
  223. /*
  224.  * Delete Node at Particular Position
  225.  */
  226. void double_clist::delete_pos()
  227. {    
  228.     int pos, i;
  229.     node *ptr, *s;
  230.     if (start == last && start == NULL)
  231.     {
  232.         cout<<"List is empty, nothing to delete"<<endl;
  233.         return;
  234.     }
  235.     cout<<endl<<"Enter the postion of element to be deleted: ";
  236.     cin>>pos;
  237.     if (counter < pos)
  238.     {
  239.         cout<<"Position out of range"<<endl;
  240.         return;
  241.     }
  242.     s = start;
  243.     if(pos == 1)
  244.     {
  245.         counter--;
  246.         last->next = s->next;
  247.         s->next->prev = last;
  248.         start = s->next;
  249.         free(s);
  250.         cout<<"Element Deleted"<<endl;
  251.         return;	   
  252.     }
  253.     for (i = 0;i < pos - 1;i++ )
  254.     {  
  255.         s = s->next;
  256.         ptr = s->prev;    	  
  257.     }    
  258.     ptr->next = s->next;
  259.     s->next->prev = ptr;
  260.     if (pos == counter)
  261.     {
  262.         last = ptr; 	   
  263.     }
  264.     counter--;
  265.     free(s);
  266.     cout<<"Element Deleted"<<endl;
  267. }
  268. /*
  269.  * Update value of a particular node 
  270.  */
  271. void double_clist::update()
  272. {
  273.     int value, i, pos;
  274.     if (start == last && start == NULL)
  275.     {
  276.         cout<<"The List is empty, nothing to update"<<endl;
  277.         return; 
  278.     }
  279.     cout<<endl<<"Enter the postion of node to be updated: ";
  280.     cin>>pos;
  281.     cout<<"Enter the new value: ";
  282.     cin>>value;
  283.     struct node *s;
  284.     if (counter < pos)
  285.     {
  286.         cout<<"Position out of range"<<endl;
  287.         return;
  288.     }
  289.     s = start;  
  290.     if (pos == 1)
  291.     {
  292.        s->info = value;
  293.        cout<<"Node Updated"<<endl;
  294.        return;   
  295.     }
  296.     for (i=0;i < pos - 1;i++)
  297.     {
  298.         s = s->next; 		 
  299.     }
  300.     s->info = value;
  301.     cout<<"Node Updated"<<endl;
  302. }
  303. /*
  304.  * Search Element in the list
  305.  */
  306. void double_clist::search()
  307. {
  308.     int pos = 0, value, i;
  309.     bool flag = false;
  310.     struct node *s;
  311.     if (start == last && start == NULL)
  312.     {
  313.         cout<<"The List is empty, nothing to search"<<endl;
  314.         return;
  315.     }
  316.     cout<<endl<<"Enter the value to be searched: ";
  317.     cin>>value;
  318.     s = start;
  319.     for (i = 0;i < counter;i++)
  320.     {
  321.         pos++;
  322.         if (s->info == value)
  323.         {
  324.             cout<<"Element "<<value<<" found at position: "<<pos<<endl;
  325.             flag = true;
  326.         }    
  327.         s = s->next;
  328.     }
  329.     if (!flag)
  330.         cout<<"Element not found in the list"<<endl;   
  331. }
  332. /*
  333.  * Sorting Doubly Circular Link List
  334.  */
  335. void double_clist::sort()
  336. {
  337.     struct node *temp, *s;
  338.     int value, i;
  339.     if (start == last && start == NULL)
  340.     {
  341.         cout<<"The List is empty, nothing to sort"<<endl;
  342.         return;
  343.     }
  344.     s = start;
  345.     for (i = 0;i < counter;i++)
  346.     {
  347.         temp = s->next;
  348.         while (temp != start)
  349.         {
  350.             if (s->info > temp->info)
  351.             {
  352.                 value = s->info;
  353.                 s->info = temp->info;
  354.                 temp->info = value;
  355.             }
  356.             temp = temp->next;
  357.         }
  358.         s = s->next;
  359.     }
  360. }
  361. /*
  362.  * Display Elements of the List 
  363.  */
  364. void double_clist::display()
  365. {
  366.     int i;
  367.     struct node *s;
  368.     if (start == last && start == NULL)
  369.     {
  370.         cout<<"The List is empty, nothing to display"<<endl;
  371.         return;
  372.     }
  373.     s = start;
  374.     for (i = 0;i < counter-1;i++)
  375.     {	
  376.         cout<<s->info<<"<->";
  377.         s = s->next; 
  378.     }
  379.     cout<<s->info<<endl;
  380. }
  381. /*
  382.  * Reverse Doubly Circular Linked List 
  383.  */
  384. void double_clist::reverse()
  385. {
  386.     if (start == last && start == NULL)
  387.     {
  388.         cout<<"The List is empty, nothing to reverse"<<endl;
  389.         return;
  390.     }
  391.     struct node *p1, *p2;
  392.     p1 = start;
  393.     p2 = p1->next;
  394.     p1->next = NULL;
  395.     p1->prev = p2;
  396.     while (p2 != start)
  397.     {
  398.         p2->prev = p2->next;
  399.         p2->next = p1;
  400.         p1 = p2;
  401.         p2 = p2->prev;
  402.     }
  403.     last = start;
  404.     start = p1;
  405.     cout<<"List Reversed"<<endl; 	 
  406. }

advertisement
$ g++ doublycircular_llist.cpp
$ a.out
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 4
List is empty, nothing to delete
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 5
The List is empty, nothing to update
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 6
The List is empty, nothing to search
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 7
The List is empty, nothing to sort
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 8
The List is empty, nothing to display
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 9
The List is empty, nothing to reverse
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 1
 
Enter the element to be inserted: 100
Element inserted in empty list
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 2
 
Enter the element to be inserted: 200
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 8
100<->200
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 3
 
Enter the element to be inserted: 150
 
Enter the postion of element inserted: 2
Element inserted
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 8
100<->150<->200
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 3
 
Enter the element to be inserted: 1010
 
Enter the postion of element inserted: 3
Element inserted
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 8
100<->150<->1010<->200
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 3
 
Enter the element to be inserted: 1111
 
Enter the postion of element inserted: 50
Position out of range
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 4
 
Enter the postion of element to be deleted: 3
Element Deleted
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 8
100<->150<->200
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 5
 
Enter the postion of node to be updated: 2
Enter the new value: 1111
Node Updated
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 8
100<->1111<->200
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 6
 
Enter the value to be searched: 200
Element 200 found at position: 3
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 5
 
Enter the postion of node to be updated: 14
Enter the new value: 45
Position out of range
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 8
100<->1111<->200
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 7
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 8
100<->200<->1111
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 9
List Reversed
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 8
1111<->200<->100
 
---------------------------------
 
Operations on Doubly Circular linked list
 
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 10
 
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn