C++ Program to Implement Sorted Doubly Linked List

«
»
This C++ program displays the nodes of a doubly linked list in which linked list can be traversed from the last node to first node or vice versa.

Here is the source code of the C++ program to display the values present in the nodes from head to the tail and in reverse. 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 Doubly Linked List
  3.  */
  4. #include<stdio.h>
  5. #include<conio.h>
  6. #include<iostream>
  7. using namespace std;
  8. int c = 0;
  9. struct node
  10. {
  11.     node *next, *prev;
  12.     int data;
  13. }*head = NULL, *tail = NULL, *p = NULL, *r = NULL, *np = NULL;
  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 = NULL;
  26.         p->prev = NULL;
  27.         c++;
  28.     }
  29.     else
  30.     {
  31.         p = head;
  32.         r = p;
  33.     if (np->data < p->data)
  34.     {
  35.         np->next = p;
  36.         p->prev = np;
  37.         np->prev = NULL;
  38.         head = np;
  39.         p = head;
  40.         do
  41.         {
  42.             p = p->next;
  43.         }
  44.         while (p->next != NULL);
  45.         tail = p;
  46.     }
  47.     else if (np->data > p->data)
  48.     {
  49.         while (p != NULL && np->data > p->data)
  50.         {
  51.             r = p;
  52.             p = p->next;
  53.         if (p == NULL)
  54.         {
  55.             r->next = np;
  56.             np->prev = r;
  57.             np->next = NULL;
  58.             tail = np;
  59.             break;
  60.         }
  61.         else if (np->data < p->data)
  62.         { 
  63.             r->next = np;
  64.             np->prev = r;
  65.             np->next = p;
  66.             p->prev = np;
  67.             if (p->next != NULL)
  68.             {
  69.                 do
  70.                 {
  71.                     p = p->next;
  72.                 }
  73.                 while (p->next !=NULL);
  74.             }
  75.             tail = p;
  76.             break;
  77.          }
  78.        }
  79.      }
  80.    }
  81. }
  82. void traverse_tail()
  83. {
  84.     node *t = tail;
  85.     while (t != NULL)
  86.     {
  87.         cout<<t->data<<"\t";
  88.         t = t->prev;
  89.     }
  90.     cout<<endl;
  91. }
  92. void traverse_head()
  93. {
  94.     node *t = head;
  95.     while (t != NULL)
  96.     {
  97.         cout<<t->data<<"\t";
  98.         t = t->next;
  99.     }
  100.     cout<<endl;
  101. }
  102. int main()
  103. {
  104.     int i = 0, n, x, ch;
  105.     cout<<"enter the no of nodes\n";
  106.     cin>>n;
  107.     while (i < n)
  108.     {
  109.         cout<<"\nenter value of node\n";
  110.         cin>>x;
  111.         create(x);
  112.         i++;
  113.     }
  114.     cout<<"\nTraversing Doubly Linked List head first\n";
  115.     traverse_head();
  116.     cout<<"\nTraversing Doubly Linked List tail first\n";
  117.     traverse_tail();
  118.     getch();
  119. }

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

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

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.