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.

```
/*
```

 * C++ Program to Implement Sorted Doubly Linked List

```
 */
```
```
#include<stdio.h>
```
```
#include<conio.h>
```
```
#include<iostream>
```
```
using namespace std;
```
```
int c = 0;
```
```
struct node
```
```
{
```
```
    node *next, *prev;
```
```
    int data;
```

}*head = NULL, *tail = NULL, *p = NULL, *r = NULL, *np = NULL;

```
void create(int x)
```
```
{
```
```
    np = new node;
```
```
    np->data = x;
```
```
    np->next = NULL;
```
```
    np->prev = NULL;
```
```
    if (c == 0)
```
```
    {
```
```
        tail = np;
```
```
        head = np;
```
```
        p = head;
```
```
        p->next = NULL;
```
```
        p->prev = NULL;
```
```
        c++;
```
```
    }
```
```
    else
```
```
    {
```
```
        p = head;
```
```
        r = p;
```
```
    if (np->data < p->data)
```
```
    {
```
```
        np->next = p;
```
```
        p->prev = np;
```
```
        np->prev = NULL;
```
```
        head = np;
```
```
        p = head;
```
```
        do
```
```
        {
```
```
            p = p->next;
```
```
        }
```
```
        while (p->next != NULL);
```
```
        tail = p;
```
```
    }
```
```
    else if (np->data > p->data)
```
```
    {
```

        while (p != NULL && np->data > p->data)

```
        {
```
```
            r = p;
```
```
            p = p->next;
```
```
        if (p == NULL)
```
```
        {
```
```
            r->next = np;
```
```
            np->prev = r;
```
```
            np->next = NULL;
```
```
            tail = np;
```
```
            break;
```
```
        }
```
```
        else if (np->data < p->data)
```
```
        { 
```
```
            r->next = np;
```
```
            np->prev = r;
```
```
            np->next = p;
```
```
            p->prev = np;
```
```
            if (p->next != NULL)
```
```
            {
```
```
                do
```
```
                {
```
```
                    p = p->next;
```
```
                }
```
```
                while (p->next !=NULL);
```
```
            }
```
```
            tail = p;
```
```
            break;
```
```
         }
```
```
       }
```
```
     }
```
```
   }
```
```
}
```
```
void traverse_tail()
```
```
{
```
```
    node *t = tail;
```
```
    while (t != NULL)
```
```
    {
```
```
        cout<<t->data<<"\t";
```
```
        t = t->prev;
```
```
    }
```
```
    cout<<endl;
```
```
}
```
```
void traverse_head()
```
```
{
```
```
    node *t = head;
```
```
    while (t != NULL)
```
```
    {
```
```
        cout<<t->data<<"\t";
```
```
        t = t->next;
```
```
    }
```
```
    cout<<endl;
```
```
}
```
```
int main()
```
```
{
```
```
    int i = 0, n, x, ch;
```
```
    cout<<"enter the no of nodes\n";
```
```
    cin>>n;
```
```
    while (i < n)
```
```
    {
```

        cout<<"\nenter value of node\n";

```
        cin>>x;
```
```
        create(x);
```
```
        i++;
```
```
    }
```

    cout<<"\nTraversing Doubly Linked List head first\n";

```
    traverse_head();
```

    cout<<"\nTraversing Doubly Linked List tail first\n";

```
    traverse_tail();
```
```
    getch();
```
```
}
```

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.

Subscribe Now: Data Structures in C++ Newsletter | Important Subjects Newsletters

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

« Prev - C++ Program to Implement Sorted Singly Linked List

» Next - C++ Program to Implement Sorted Circularly Singly Linked List

Next Steps: