Circular Doubly Linked List in C++

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.

```
/*
```

 * C++ Program to Implement Circular Doubly Linked List

```
 */
```
```
#include<iostream>
```
```
#include<cstdio>
```
```
#include<cstdlib>
```
```
using namespace std;
```
```
 
```
```
/*
```
```
 * Node Declaration
```
```
 */
```
```
struct node
```
```
{
```
```
    int info;
```
```
    struct node *next;
```
```
    struct node *prev;
```
```
}*start, *last;
```
```
int counter = 0;
```
```
/*
```
```
 * Class Declaration
```
```
 */
```
```
class double_clist
```
```
{
```
```
    public:
```
```
        node *create_node(int);
```
```
        void insert_begin();
```
```
        void insert_last();
```
```
        void insert_pos();
```
```
        void delete_pos();
```
```
        void search();
```
```
        void update();
```
```
        void display();
```
```
        void reverse();
```
```
        void sort();
```
```
        double_clist()
```
```
        {
```
```
            start = NULL;
```
```
            last = NULL;			
```
```
        }
```
```
};
```
```
 
```
```
/*
```
```
 * Main: Contains Menu
```
```
 */
```
```
int main()
```
```
{
```
```
    int choice;
```
```
    double_clist cdl;
```
```
    while (1)
```
```
    {
```

        cout<<"\n-------------------------------"<<endl;

        cout<<"Operations on Doubly Circular linked list"<<endl;

        cout<<"\n-------------------------------"<<endl;

        cout<<"1.Insert at Beginning"<<endl;

```
        cout<<"2.Insert at Last"<<endl;
```

        cout<<"3.Insert at Position"<<endl;

        cout<<"4.Delete at Position"<<endl;

```
        cout<<"5.Update Node"<<endl;
```
```
        cout<<"6.Search Element"<<endl;
```
```
        cout<<"7.Sort"<<endl;
```
```
        cout<<"8.Display List"<<endl;
```
```
        cout<<"9.Reverse List"<<endl;
```
```
        cout<<"10.Exit"<<endl;
```
```
        cout<<"Enter your choice : ";
```
```
        cin>>choice;
```
```
        switch(choice)
```
```
        {
```
```
        case 1:
```
```
            cdl.insert_begin();
```
```
            break;
```
```
        case 2:
```
```
            cdl.insert_last();
```
```
            break;   
```
```
        case 3:
```
```
            cdl.insert_pos();
```
```
            break; 
```
```
        case 4:
```
```
            cdl.delete_pos();
```
```
            break;
```
```
        case 5:
```
```
            cdl.update();
```
```
            break;
```
```
        case 6:
```
```
            cdl.search();
```
```
            break;
```
```
        case 7:
```
```
            cdl.sort();
```
```
            break;
```
```
        case 8:
```
```
            cdl.display();
```
```
            break;
```
```
        case 9:
```
```
            cdl.reverse();
```
```
            break;
```
```
        case 10:
```
```
            exit(1); 
```
```
        default:
```

            cout<<"Wrong choice"<<endl;

```
        }
```
```
    }
```
```
    return 0;
```
```
}
```
```
 
```
```
/*
```

 *MEMORY ALLOCATED FOR NODE DYNAMICALLY

```
 */
```

node* double_clist::create_node(int value)

```
{
```
```
    counter++;  
```
```
    struct node *temp;
```
```
    temp = new(struct node);
```
```
    temp->info = value;
```
```
    temp->next = NULL;
```
```
    temp->prev = NULL;
```
```
    return temp;
```
```
}
```
```
/*
```
```
 *INSERTS ELEMENT AT BEGINNING
```
```
 */
```
```
void double_clist::insert_begin()
```
```
{
```
```
    int value;
```

    cout<<endl<<"Enter the element to be inserted: ";

```
    cin>>value;
```
```
    struct node *temp;
```
```
    temp = create_node(value);
```
```
    if (start == last && start == NULL)
```
```
    {    
```

        cout<<"Element inserted in empty list"<<endl;

```
        start = last = temp;
```

        start->next = last->next = NULL;

        start->prev = last->prev = NULL;

```
    }
```
```
    else
```
```
    {
```
```
        temp->next = start;
```
```
        start->prev = temp;
```
```
        start = temp;
```
```
        start->prev = last;
```
```
        last->next = start;
```
```
        cout<<"Element inserted"<<endl;
```
```
    }
```
```
}
```
```
 
```
```
/*
```
```
 *INSERTS ELEMNET AT LAST
```
```
 */
```
```
void double_clist::insert_last()
```
```
{
```
```
    int value;    
```

    cout<<endl<<"Enter the element to be inserted: ";

```
    cin>>value; 
```
```
    struct node *temp;
```
```
    temp = create_node(value);
```
```
    if (start == last && start == NULL)
```
```
    {
```

        cout<<"Element inserted in empty list"<<endl;

```
        start = last = temp;
```

        start->next = last->next = NULL;

        start->prev = last->prev = NULL;

```
    }
```
```
    else
```
```
    {
```
```
        last->next = temp;
```
```
        temp->prev = last;
```
```
        last = temp;
```
```
        start->prev = last;
```
```
        last->next = start;
```
```
    }
```
```
}
```
```
/*
```
```
 *INSERTS ELEMENT AT POSITION
```
```
 */
```
```
void double_clist::insert_pos()
```
```
{    
```
```
    int value, pos, i;
```

    cout<<endl<<"Enter the element to be inserted: ";

```
    cin>>value;
```

    cout<<endl<<"Enter the postion of element inserted: ";

```
    cin>>pos;
```
```
    struct node *temp, *s, *ptr;
```
```
    temp = create_node(value);
```
```
    if (start == last && start == NULL)
```
```
    {
```
```
        if (pos == 1)
```
```
        {
```
```
            start = last = temp;
```

            start->next = last->next = NULL;

            start->prev = last->prev = NULL;

```
        }
```
```
        else
```
```
        {
```

            cout<<"Position out of range"<<endl;

```
            counter--;
```
```
            return;
```
```
        }
```
```
    }  
```
```
    else
```
```
    {
```
```
        if (counter < pos)
```
```
        {
```

             cout<<"Position out of range"<<endl;

```
             counter--;
```
```
             return;   		
```
```
        }
```
```
        s = start;		
```
```
        for (i = 1;i <= counter;i++)
```
```
        {
```
```
            ptr = s;
```
```
            s = s->next;
```
```
            if (i == pos - 1)
```
```
            {
```
```
                ptr->next = temp;
```
```
                temp->prev = ptr;
```
```
                temp->next = s;
```
```
                s->prev = temp;
```

                cout<<"Element inserted"<<endl;

```
                break;
```
```
            }
```
```
        }
```
```
    }
```
```
}
```
```
/*
```
```
 * Delete Node at Particular Position
```
```
 */
```
```
void double_clist::delete_pos()
```
```
{    
```
```
    int pos, i;
```
```
    node *ptr, *s;
```
```
    if (start == last && start == NULL)
```
```
    {
```

        cout<<"List is empty, nothing to delete"<<endl;

```
        return;
```
```
    }
```

    cout<<endl<<"Enter the postion of element to be deleted: ";

```
    cin>>pos;
```
```
    if (counter < pos)
```
```
    {
```

        cout<<"Position out of range"<<endl;

```
        return;
```
```
    }
```
```
    s = start;
```
```
    if(pos == 1)
```
```
    {
```
```
        counter--;
```
```
        last->next = s->next;
```
```
        s->next->prev = last;
```
```
        start = s->next;
```
```
        free(s);
```
```
        cout<<"Element Deleted"<<endl;
```
```
        return;	   
```
```
    }
```
```
    for (i = 0;i < pos - 1;i++ )
```
```
    {  
```
```
        s = s->next;
```
```
        ptr = s->prev;    	  
```
```
    }    
```
```
    ptr->next = s->next;
```
```
    s->next->prev = ptr;
```
```
    if (pos == counter)
```
```
    {
```
```
        last = ptr; 	   
```
```
    }
```
```
    counter--;
```
```
    free(s);
```
```
    cout<<"Element Deleted"<<endl;
```
```
}
```
```
/*
```
```
 * Update value of a particular node 
```
```
 */
```
```
void double_clist::update()
```
```
{
```
```
    int value, i, pos;
```
```
    if (start == last && start == NULL)
```
```
    {
```

        cout<<"The List is empty, nothing to update"<<endl;

```
        return; 
```
```
    }
```

    cout<<endl<<"Enter the postion of node to be updated: ";

```
    cin>>pos;
```
```
    cout<<"Enter the new value: ";
```
```
    cin>>value;
```
```
    struct node *s;
```
```
    if (counter < pos)
```
```
    {
```

        cout<<"Position out of range"<<endl;

```
        return;
```
```
    }
```
```
    s = start;  
```
```
    if (pos == 1)
```
```
    {
```
```
       s->info = value;
```
```
       cout<<"Node Updated"<<endl;
```
```
       return;   
```
```
    }
```
```
    for (i=0;i < pos - 1;i++)
```
```
    {
```
```
        s = s->next; 		 
```
```
    }
```
```
    s->info = value;
```
```
    cout<<"Node Updated"<<endl;
```
```
}
```
```
/*
```
```
 * Search Element in the list
```
```
 */
```
```
void double_clist::search()
```
```
{
```
```
    int pos = 0, value, i;
```
```
    bool flag = false;
```
```
    struct node *s;
```
```
    if (start == last && start == NULL)
```
```
    {
```

        cout<<"The List is empty, nothing to search"<<endl;

```
        return;
```
```
    }
```

    cout<<endl<<"Enter the value to be searched: ";

```
    cin>>value;
```
```
    s = start;
```
```
    for (i = 0;i < counter;i++)
```
```
    {
```
```
        pos++;
```
```
        if (s->info == value)
```
```
        {
```

            cout<<"Element "<<value<<" found at position: "<<pos<<endl;

```
            flag = true;
```
```
        }    
```
```
        s = s->next;
```
```
    }
```
```
    if (!flag)
```

        cout<<"Element not found in the list"<<endl;

```
}
```
```
/*
```
```
 * Sorting Doubly Circular Link List
```
```
 */
```
```
void double_clist::sort()
```
```
{
```
```
    struct node *temp, *s;
```
```
    int value, i;
```
```
    if (start == last && start == NULL)
```
```
    {
```

        cout<<"The List is empty, nothing to sort"<<endl;

```
        return;
```
```
    }
```
```
    s = start;
```
```
    for (i = 0;i < counter;i++)
```
```
    {
```
```
        temp = s->next;
```
```
        while (temp != start)
```
```
        {
```
```
            if (s->info > temp->info)
```
```
            {
```
```
                value = s->info;
```
```
                s->info = temp->info;
```
```
                temp->info = value;
```
```
            }
```
```
            temp = temp->next;
```
```
        }
```
```
        s = s->next;
```
```
    }
```
```
}
```
```
/*
```
```
 * Display Elements of the List 
```
```
 */
```
```
void double_clist::display()
```
```
{
```
```
    int i;
```
```
    struct node *s;
```
```
    if (start == last && start == NULL)
```
```
    {
```

        cout<<"The List is empty, nothing to display"<<endl;

```
        return;
```
```
    }
```
```
    s = start;
```
```
    for (i = 0;i < counter-1;i++)
```
```
    {	
```
```
        cout<<s->info<<"<->";
```
```
        s = s->next; 
```
```
    }
```
```
    cout<<s->info<<endl;
```
```
}
```
```
/*
```

 * Reverse Doubly Circular Linked List

```
 */
```
```
void double_clist::reverse()
```
```
{
```
```
    if (start == last && start == NULL)
```
```
    {
```

        cout<<"The List is empty, nothing to reverse"<<endl;

```
        return;
```
```
    }
```
```
    struct node *p1, *p2;
```
```
    p1 = start;
```
```
    p2 = p1->next;
```
```
    p1->next = NULL;
```
```
    p1->prev = p2;
```
```
    while (p2 != start)
```
```
    {
```
```
        p2->prev = p2->next;
```
```
        p2->next = p1;
```
```
        p1 = p2;
```
```
        p2 = p2->prev;
```
```
    }
```
```
    last = start;
```
```
    start = p1;
```
```
    cout<<"List Reversed"<<endl; 	 
```
```
}
```

$ 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.

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

« Prev - Circular Single Linked List in C++

» Next - C++ Program to Implement Triply Linked List

Related Posts:

Practice Design & Analysis of Algorithms MCQ
Apply for Computer Science Internship
Practice Programming MCQs
Check Programming Books
Check Data Structure Books

Recommended Articles: