C++ Program to Implement Sorted Circularly Doubly Linked List

«
»
This C++ program displays the nodes of a doubly linked list with the last node pointing back to the first as well as the first node pointing back to the last giving a circularly doubly linked list.

Here is the source code of the C++ program to display the values present in the nodes cyclically.
This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is given below.

  1. /*
  2.  * C++ Program to Implement Sorted Circularly Doubly Linked List
  3.  */
  4. #include<stdio.h>
  5. #include<conio.h>
  6. #include<iostream>
  7. using namespace std;
  8. struct node
  9. {
  10.     int data;
  11.     node *next, *prev;
  12. }*p = NULL, *head = NULL, *r = NULL, *np = NULL, *tail = NULL;
  13. int c = 0;
  14. void create(int x)
  15. {
  16.     np = new node;
  17.     np->data = x;
  18.     np->next = NULL;
  19.     np->prev = NULL;
  20.     if (c == 0)
  21.     {
  22.         tail = np;
  23.         head = np;
  24.         p = head;
  25.         p->next = head;
  26.         p->prev = head;
  27.         c++;
  28.     }
  29.     else if (c == 1)
  30.     {
  31.         p = head;
  32.         r = p;
  33.     if (np->data < p->data)
  34.     {
  35.         np->next = p;
  36.         p->prev = np;
  37.         head = np;
  38.         p->next = np;
  39.         np->prev = p;
  40.         tail = p;
  41.     }
  42.     else if (np->data > p->data)
  43.     {
  44.         p->next = np;
  45.         np->prev = p;
  46.         np->next = head;
  47.         p->prev = np;
  48.     }
  49.     c++;
  50.     } else {
  51.         p = head;
  52.         r = p;
  53.     if (np->data < p->data)
  54.     {
  55.         np->next = p;
  56.         p->prev = np;
  57.         head = np;
  58.         do
  59.         {
  60.             p = p->next;
  61.         }
  62.         while (p->next != r);
  63.         tail = p;
  64.         p->next = np;
  65.         np->prev = p;
  66.     }
  67.     else if (np->data > p->data)
  68.     {
  69.         while (p->next != head && np->data > p->data)
  70.         {
  71.             r = p;
  72.             p = p->next;
  73.         if (p->next == head  && (p->data < np->data))
  74.         {
  75.             p->next = np;
  76.             np->prev = p;
  77.             np->next = head;
  78.             tail = np;
  79.             head->prev = np;
  80.             break;
  81.         }
  82.         else if (np->data < p->data)
  83.         { 
  84.             r->next = np;
  85.             np->prev = r;
  86.             np->next = p;
  87.             p->prev = np;
  88.             if (p->next != head)
  89.             {
  90.                 do
  91.                 {
  92.                     p = p->next;
  93.                 }
  94.                 while (p->next != head);
  95.             }
  96.             tail = p;
  97.             break;
  98.          }
  99.        }
  100.     }
  101.   }
  102. }
  103. void traverse_tail(int i)
  104. {
  105.     node *t = tail;
  106.     int x = 0;
  107.     while (x <= i)
  108.     {
  109.         cout<<t->data<<"\t";
  110.         t = t->prev;
  111.         x++;
  112.     }
  113.     cout<<endl;
  114. }
  115. void traverse_head(int i)
  116. {
  117.     node *t = head;
  118.     int c = 0;
  119.     while (c <= i)
  120.     {
  121.         cout<<t->data<<"\t";
  122.         t = t->next;
  123.         c++;
  124.     }
  125.     cout<<endl;
  126. }
  127. int main()
  128. {
  129.     int i = 0, n, x, ch;
  130.     cout<<"enter the no of nodes\n";
  131.     cin>>n;
  132.     while (i < n)
  133.     {
  134.         cout<<"\nenter value of node\n";
  135.         cin>>x;
  136.         create(x);
  137.         i++;
  138.     }
  139.     cout<<"\nTraversing Doubly Linked List head first\n";
  140.     traverse_head(n);
  141.     cout<<"\nTraversing Doubly Linked List tail first\n";
  142.     traverse_tail(n);
  143.     getch();
  144. }

advertisement
Output
 
enter the no of nodes
7
 
enter value of node
5
 
enter value of node
1
 
enter value of node
3
 
enter value of node
8
 
enter value of node
6
 
enter value of node
9
 
enter value of node
7
 
Traversing Doubly Linked List head first
1       3       5       6       7       8       9       1
 
Traversing Doubly Linked List tail first
9       8       7       6       5       3       1       9

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

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.