Circular Doubly Linked List with C++ Implementation

A Circular Doubly Linked List is the form of a Doubly Linked List and is connected in circular form. The first and last nodes are linked to each other with the previous and next pointers.

• Hence, it is possible to traverse the whole list starting from any node.
• This includes direct access to the last node, unlike others.
• However, there is a possibility of an infinite loop if proper care is not taken.

1. Representation

• Head: The starting point of the linked list
• Node: A node consists of the data element and the pointer to the Previous and Next node
• Element: The actual data
• Prev: Pointer to the previous node
• Next: Pointer to the next node

Applications

• Circular Doubly Linked List is useful for Applications that require loop operations and both forward and backward navigations.
• Music Player to play the songs in a loop with the ability to play the previous songs when asked.

2. Insertion on Circular Doubly Linked List

An element can be inserted into the circular doubly list in any of the following methods.

1. InsertFront – at the beginning of the List
2. InsertBack – at the end of the List
3. InsertAfter – after the specific node

2.1. Insert Front

Let’s insert element 20 in an empty list. The Head of the list initially points to NULL, so create the new node and make it the Head node for the first time.

Consider an example to insert element 10 at the front side. Place the new node before the Head node and make it as Head.

Algorithm

1. Create the new node
2. Check if the list is empty. If true, make the new node as head and point itself to form the one-node circle.
3. Otherwise, connect the new node at the front.
4. Finally, make the new node as Head.

Code

Node* CircularDoublyList::insert_front(int element)
{
    // Step 1. Create the new node
    Node* new_node = new Node();
    new_node->element = element;

    // Step 2. Check if the list is empty. If true, make the new node
    // as head and point itself to form the one node circle.
    if (head == NULL) {
        new_node->prev = new_node;
        new_node->next = new_node;
        head = new_node;
        return new_node;
    }
    
    // Step 3. Connect the new node at front.
    new_node->prev = head->prev;
    new_node->prev->next = new_node;
    new_node->next = head;
    new_node->next->prev = new_node;

    // Step 4. Make the new node as head
    head = new_node;
    
    return new_node;
}

2.2. Insert Back

Insert an element 40 at the backside. Place the new node just after the last node and set up the forward/backward traversal links.

Algorithm

1. Create the new node
2. Check if the list is empty. If true, make the new node as head and point itself to form the one-node circle.
3. Otherwise, link the new node after the last node.

Code

Node* CircularDoublyList::insert_back(int element)
{
    // Step 1. Create the new node
    Node *new_node = new Node();
    new_node->element = element;
    
    // Step 2. Check if the list is empty. If true, make the new node
    // as head and point itself to form the one node circle.
    if (head == NULL) {
        new_node->prev = new_node;
        new_node->next = new_node;
        head = new_node;
        return new_node;
    }
    
    // Step 3. Link the new node after the last node
    new_node->prev = head->prev;
    new_node->prev->next = new_node;
    new_node->next = head;
    new_node->next->prev = new_node;

    return new_node;
}

2.3. Insert After

Insert an element (30) after the node (20). Place the new node next to the specified node and set up the forward/backward traversal links.

Algorithm

1. Create the new node
2. Link the new node after the given node

Code

Node* CircularDoublyList::insert_after(Node* prev, int element)
{
    // Step 1. Create the new node
    Node *new_node = new Node();
    new_node->element = element;

    // Step 2. Link the new node after the given node
    new_node->next = prev->next;
    new_node->next->prev = new_node;
    new_node->prev = prev;
    new_node->prev->next = new_node;

    return new_node;
}

3. Deletion on Circular Doubly Linked List

In a Circular Doubly List, deletion can occur either at the front, at a specific node, or at back.

1. DeleteFront – at the beginning of the List
2. DeleteBack – at the end of the List
3. DeleteNode – the specific node
4. Remove – Search the specific element and remove the node

3.1. Delete Front

The node present at the beginning is disconnected from the list by linking its next node with the last node. Then it will be removed from the list. So, the “Head” points to the next node.

Algorithm

1. Check if the list is empty. If true, return.
2. Otherwise, check if the list has only a single node. If true, delete the node, reset the head to NULL, and return.
3. Otherwise, skip the front node and connect the last node directly with the next node.
4. Store the reference to the front node as the target.
5. Move the head to the next node.
6. Finally, delete the target node.

Code

Node* CircularDoublyList::delete_front()
{
    // Step 1. Check if the list is empty. If true, return.
    if (head == NULL) {
        return NULL;
    }

    // Step 2. Check if the list has single node. If true, delete the node,
    // reset the head to NULL, and return.
    if (head->next == head) {
        delete head;
        head = NULL;
        return NULL;
    }

    // Step 3. Skip the front node and connect the last node directly with next node.
    head->prev->next = head->next;
    head->next->prev = head->prev;

    // Step 4. Store the reference to front node as target
    Node* target = head;

    // Step 5. Move the head to next node
    head = head->next;

    // Step 6. Delete the target node
    delete target;
    return head;
}

3.2. Delete Back

To delete a node from the backside, disconnect the last node from the circle.

Algorithm

1. Check if the list is empty. If true, return.
2. Check if the list has only a single node. If true, delete the node, reset the head to NULL, and return.
3. Skip the last node and connect its previous node with the first node.
4. Delete the target node.

Code

Node* CircularDoublyList::delete_back()
{
    // Step 1. Check if the list is empty. If true, return.
    if (head == NULL) {
        return NULL;
    }
    
    // Step 2. Check if the list has single node. If true, delete the node,
    // reset the head to NULL, and return.
    if (head->next == head) {
        delete head;
        head = NULL;
        return NULL;
    }

    // Step 3. Skip the last node and connect its previous node with first node
    Node* target = head->prev;
    target->prev->next = target->next;
    target->next->prev = target->prev;

    // Step 4. Delete the target node
    delete target;
    return head->prev;
}

3.3. Delete Node

A specific node can be deleted from the linked list by connecting its previous and the next node directly. In case the requested node is Head, then move Head to point to the next node.

Algorithm

1. Check if the list is empty. If true, return.
2. Check if the target node is Head. If true, perform delete_front().
3. Otherwise, disconnect the node by directly linking its previous and next node.
4. Delete the target node

Code

Node* CircularDoublyList::delete_node(Node* target)
{
    // Step 1. Check if the list is empty. If true, return.
    if (head == NULL) {
        return NULL;
    }

    // Step 2. Check if the target node is head. If true,
    // perform delete_front()
    if (target == head) {
        return delete_front();
    }

    // Step 3. Otherwise, disconnect the node by directly linking
    // its previous and next node
    target->prev->next = target->next;
    target->next->prev = target->prev;

    // Step 4. Delete the target node
    Node* next_node = target->next;
    delete target;
    return next_node;
}

3.4. Remove

Remove the node by searching the specific element (30). Traverse the list to search the given element and delete the node. This operation can take O(n) time since the search is involved here.

Algorithm

1. Check if the list is empty. If true, return.
2. Check if the element matches the head node. If true, perform delete_front().
3. Otherwise, iterate the linked list from start to end, and search if the element is found.
4. If found, set the node as the target node and disconnect it by directly linking its previous and next node.
5. Delete the target node

Code

bool CircularDoublyList::remove(int element)
{
    // Step 1. Check if the list is empty and return if true.
    if (head == NULL) {
        return false;
    }

    // Step 2. Check if the element matches the head node. If true,
    // perform delete_front()
    if (element == head->element) {
        delete_front();
        return true;
    }

    // Step 3. Otherwise, iterate the linked list from start to end,
    // and search if the element is found.
    for (Node* node = head->next; node != head; node = node->next) {

        if (node->element == element) {
            // Step 4. If found, set the node as target node and disconnect
            // it by directly linking its previous and next node.
            Node* target = node;
            node->prev->next = node->next;
            node->next->prev = node->prev;

            // Step 5. Delete the target node
            delete target;
            return true;
        }
    }

    return false;
}

4. Search on Circular Doubly Linked List

The list is traversed from start to end to search for an element in the Linked List. Since the list is circular, the end of the list is identified by checking for the Head node.

Algorithm

1. Check if the list is empty. If true, return NULL.
2. Iterate the linked list from start to end, search the element and return if found.
3. Stop the iteration if the end of the list is reached and return NULL.

Code

Node* CircularDoublyList::search(int element)
{
    // Check if the list is empty
    if (head == NULL) {
        return NULL;
    }

    // Iterate the linked list from start to end and search element
    Node* node = head;
    do {
        if (node->element == element) {
            return node; // Found element
        }
        node = node->next;
    } while (node != head);

    return NULL; // Not found
}

5. The Complete Example in C++

/**
 * C++ example to demonstrate the circular doubly linked list
 */
#include <iostream>
using namespace std;

// Linked list node representation
struct Node
{
    int element;
    Node* prev;
    Node* next;
};

/**
 * Circular doubly linked list implementation
 */
class CircularDoublyList
{
    // The first node of the list
    Node* head;

public:
    // Constructor
    CircularDoublyList() : head(NULL) {}

    // Insert an element in front of the list
    // Returns the new node inserted
    Node* insert_front(int element);

    // Insert an element at the end of the list
    // Returns the new node inserted
    Node* insert_back(int element);

    // Insert an element after the given node
    // Returns the new node inserted
    Node* insert_after(Node* prev, int element);
    
    // Delete the first node
    // Returns the next node if available, NULL otherwise.
    Node* delete_front();
    
    // Delete the last node
    // Returns the previous node if available, NULL otherwise.
    Node* delete_back();
    
    // Delete the specific node
    // Returns the next node if available, NULL otherwise.
    Node* delete_node(Node* prev);

    // Search and delete the given element
    // Returns true on success, false otherwise.
    bool remove(int element);
    
    // Search an element from the list
    // Returns the matching node if found, NULL otherwise.
    Node* search(int element);
    
    // Traverse the list and print the elements
    void traverse(const std::string& msg);
};

Node* CircularDoublyList::insert_front(int element)
{
    // Step 1. Create the new node
    Node* new_node = new Node();
    new_node->element = element;

    // Step 2. Check if the list is empty. If true, make the new node
    // as head and point itself to form the one node circle.
    if (head == NULL) {
        new_node->prev = new_node;
        new_node->next = new_node;
        head = new_node;
        return new_node;
    }
    
    // Step 3. Connect the new node at front.
    new_node->prev = head->prev;
    new_node->prev->next = new_node;
    new_node->next = head;
    new_node->next->prev = new_node;

    // Step 4. Make the new node as head
    head = new_node;
    
    return new_node;
}

Node* CircularDoublyList::insert_back(int element)
{
    // Step 1. Create the new node
    Node *new_node = new Node();
    new_node->element = element;
    
    // Step 2. Check if the list is empty. If true, make the new node
    // as head and point itself to form the one node circle.
    if (head == NULL) {
        new_node->prev = new_node;
        new_node->next = new_node;
        head = new_node;
        return new_node;
    }
    
    // Step 3. Link the new node after the last node
    new_node->prev = head->prev;
    new_node->prev->next = new_node;
    new_node->next = head;
    new_node->next->prev = new_node;

    return new_node;
}

Node* CircularDoublyList::insert_after(Node* prev, int element)
{
    // Step 1. Create the new node
    Node *new_node = new Node();
    new_node->element = element;

    // Step 2. Link the new node after the given node
    new_node->next = prev->next;
    new_node->next->prev = new_node;
    new_node->prev = prev;
    new_node->prev->next = new_node;

    return new_node;
}

Node* CircularDoublyList::delete_front()
{
    // Step 1. Check if the list is empty. If true, return.
    if (head == NULL) {
        return NULL;
    }

    // Step 2. Check if the list has single node. If true, delete the node,
    // reset the head to NULL, and return.
    if (head->next == head) {
        delete head;
        head = NULL;
        return NULL;
    }

    // Step 3. Skip the front node and connect the last node directly with next node.
    head->prev->next = head->next;
    head->next->prev = head->prev;
    
    // Step 4. Store the reference to front node as target
    Node* target = head;

    // Step 5. Move the head to next node
    head = head->next;
    
    // Step 6. Delete the target node
    delete target;
    return head;
}

Node* CircularDoublyList::delete_back()
{
    // Step 1. Check if the list is empty. If true, return.
    if (head == NULL) {
        return NULL;
    }

    // Step 2. Check if the list has single node. If true, delete the node,
    // reset the head to NULL, and return.
    if (head->next == head) {
        delete head;
        head = NULL;
        return NULL;
    }

    // Step 3. Skip the last node and connect its previous node with first node
    Node* target = head->prev;
    target->prev->next = target->next;
    target->next->prev = target->prev;
    
    // Step 4. Delete the target node
    delete target;
    return head->prev;
}

Node* CircularDoublyList::delete_node(Node* target)
{
    // Step 1. Check if the list is empty. If true, return.
    if (head == NULL) {
        return NULL;
    }

    // Step 2. Check if the target node is head. If true,
    // perform delete_front()
    if (target == head) {
        return delete_front();
    }

    // Step 3. Otherwise, disconnect the node by directly linking
    // its previous and next node
    target->prev->next = target->next;
    target->next->prev = target->prev;
    
    // Step 4. Delete the target node
    Node* next_node = target->next;
    delete target;
    return next_node;
}

bool CircularDoublyList::remove(int element)
{
    // Step 1. Check if the list is empty and return if true.
    if (head == NULL) {
        return false;
    }

    // Step 2. Check if the element matches the head node. If true,
    // perform delete_front()
    if (element == head->element) {
        delete_front();
        return true;
    }
    
    // Step 3. Otherwise, iterate the linked list from start to end,
    // and search if the element is found.
    for (Node* node = head->next; node != head; node = node->next) {
        
        if (node->element == element) {
            // Step 4. If found, set the node as target node and disconnect
            // it by directly linking its previous and next node.
            Node* target = node;
            node->prev->next = node->next;
            node->next->prev = node->prev;
            
            // Step 5. Delete the target node
            delete target;
            return true;
        }
    }
    
    return false;
}

Node* CircularDoublyList::search(int element)
{
    // Check if the list is empty
    if (head == NULL) {
        return NULL;
    }

    // Iterate the linked list from start to end and search element
    Node* node = head;
    do {
        if (node->element == element) {
            return node; // Found element
        }
        node = node->next;
    } while (node != head);

    return NULL; // Not found
}

// Traverse and print the linked list
void CircularDoublyList::traverse(const std::string& msg)
{
    cout << msg << endl;
    if (head == NULL ) {
        cout << "NULL" << endl << endl;
        return;
    }
    
    // Iterate the linked list from start to end
    Node* node = head;
    do {
        cout << " --> " << node->element ;
        node = node->next;
    } while (node != head);
    cout << " --> " << endl << endl;
}

int main()
{
    // Create a linked list
    CircularDoublyList list;
    list.traverse("initial list");

    // Insert elements
    Node* node_20 = list.insert_front(20);
    list.traverse("insert_front(20)");

    list.insert_front(10);
    list.traverse("insert_front(10)");

    list.insert_back(40);
    list.traverse("insert_back(40)");

    list.insert_after(node_20, 30);
    list.traverse("insert_after(node_20, 30)");

    // Search an element
    node_20 = list.search(20);
    cout << "search(20) matches node " << node_20->element << endl << endl;

    // Delete elements
    list.delete_front();
    list.traverse("delete_front()");
    
    list.delete_back();
    list.traverse("delete_back()");
    
    list.delete_node(node_20);
    list.traverse("delete_node(node_20)");
    
    list.remove(30);
    list.traverse("remove(30)");
}

Output

initial list
NULL

insert_front(20)
 --> 20 --> 

insert_front(10)
 --> 10 --> 20 --> 

insert_back(40)
 --> 10 --> 20 --> 40 --> 

insert_after(node_20, 30)
 --> 10 --> 20 --> 30 --> 40 --> 

search(20) matches node 20

delete_front()
 --> 20 --> 30 --> 40 --> 

delete_back()
 --> 20 --> 30 --> 

delete_node(node_20)
 --> 30 --> 

remove(30)
NULL