Circular Doubly Linked List in C++

Hello guys in this C++ tutorial we are going to discuss Circular Doubly Linked List.

Circular Doubly Linked List

First of all, let’s talk about linked list. Linked List is a linear data structure in which two adjacent nodes are connected by a pointer from one node to another.

Now, in doubly linked list there are two-pointer from the same node. First to the node after it and Second for the node behind it.

A circular linked list contains all the features and properties of a normal linked list but also have a link from the last element of the list to its first element which creates a cycle.

Operations

1. Insertion at the beginning – Adding a node in circular doubly linked list at the beginning.
2. Insertion at the end – Adding a node in circular doubly linked list at the end.
3. Deletion – Removing a node in circular doubly linked list from a defined position.

Implementation

Insert a node at the beginning: Code and Explanation

void insert_begin()
{
 
    int info;
 
    cout<<"Enter the value to be inserted:";
    cout<<info;
    new = create_node(info);
 
    if (first == last && first == NULL)
    {    
        cout<<"Initially it is empty linked list later insertion is done";
        first = last = new;
        first->next = last->next = NULL;
        first->prev = last->prev = NULL;
    }
    else
    {
        new->next = first;
        first->prev = new;
        first = new;
        first->prev = last;
        last->next = first;
        cout<<"The value is inserted at beginning";
    }
}

In the above code. First, we create an empty node and insert a value into it. If (first==last) i.e. the list is empty then the added node is the first node. Otherwise, we set the next pointer of the node to the first and last nodes next to the new node.

 

Insert a node at the ending: Code and Explanation

void insert_end()
{
 
    int info;    
 
    cout<<"Enter the value that has to be inserted at last:";
    cout<<info;
    new = create_node(info);
 
    if (first == last && first == NULL)
    {
        cout<<"Initially the list is empty and now new node is inserted but at first";
        first = last = new;
        first->next = last->next = NULL;    
        first->prev = last->prev = NULL;
    }
    else
    {
        last->next = new;
        new->prev = last;
        last = new;
        first->prev = last;
        last->next = first;
    }
}

To insert the node at the ending. We again check for the condition if the list is empty. Otherwise, we set the next pointer of last node to the new node and new nodes next as first node.

 

Delete a node: Code and Explanation

void delete()
{    
    int pos, count = 0, i;
    n *temp, *prevnode;
 
    cout<<"Enter the position which u wanted to delete:";
    cin>>pos;
 
    if (first == last && first == NULL)
        cout<<"Empty linked list you cant delete";
 
    else
    {
        if (number < pos)
            cout<<"Node cant be deleted at position as it is exceeding the linkedlist length";
 
        else
        {
            for (ptr = first,i = 1;i <= number;i++)
            {
                prevnode = ptr;
                ptr = ptr->next;
                if (pos == 1)
                {    
                    number--;
                    last->next = prevnode->next;
                    ptr->prev = prevnode->prev;
                    first = ptr;
                    cout<<prevnode->val<< is deleted";
                    delete(prevnode);
                    break;        
                }
                else if (i == pos - 1)
                {    
                    number--;
                    prevnode->next = ptr->next;
                    ptr->next->prev = prevnode;
                    cout<<ptr->val<<" is deleted";
                    delete(ptr);
                    break;
                }
            }
        }
    }
}

 

For deletion, the position of the node is provided. Check if the list is empty if it is then there is no node to be deleted. Else we check if inserted position is even valid or not. Finally, we traverse to the node we want to delete. Then prevnode pointer to point to the node before the required node which is pointed by pointer ptr. Then create a link between ptr->next and prevnode. A link from ptr->next to prevnode. As a result, the links of the list are maintained. Then delete ptr. Thus the node is deleted from the list.

 

Also, read

• Introduction to Single Linked List