Circular Doubly Linked List

A Circular Doubly Linked List (CDLL) is a linked data structure in which each node contains:

• A data field
• A pointer to the next node
• A pointer to the previous node

Unlike a normal doubly linked list, the last node in a circular doubly linked list points back to the first node, and the first node points to the last node. This creates a circular connection in both directions.

A CDLL allows traversal in forward as well as backward directions without reaching a NULL value.

Structure of Circular Doubly Linked List

Each node in a circular doubly linked list contains three components:

• Previous Pointer (prev) – Stores the address of the previous node.
• Data Field – Stores the actual value.
• Next Pointer (next) – Stores the address of the next node.

Example:

 ┌──────────────────────┐
 ↓                      │
[10] ⇄ [20] ⇄ [30] ⇄ [40]
 ↑                      ↓
 └──────────────────────┘

In this structure:

• The next pointer of the last node points to the first node.
• The previous pointer of the first node points to the last node.

Memory Representation

Nodes are stored at different memory locations.

Example:

Address    Prev    Data    Next
1000       4000     10     2000
2000       1000     20     3000
3000       2000     30     4000
4000       3000     40     1000

The circular links make traversal continuous in both directions.

Features of Circular Doubly Linked List

• Traversal is possible in forward and backward directions.
• No node contains NULL pointers.
• The structure forms a complete circular chain.
• Insertions and deletions become flexible.
• Efficient for cyclic navigation systems.

Traversal in Circular Doubly Linked List

Traversal can be performed in two ways.

Forward Traversal

Start from the head node and move using the next pointer.

Example

[10] ⇄ [20] ⇄ [30] ⇄ back to [10]

Traversal order:

10 → 20 → 30

Backward Traversal

Start from the last node and move using the prev pointer.

Traversal order:

30 → 20 → 10

This bidirectional traversal is one of the main advantages of CDLL.

Insertion Operations

1. Insert at Beginning

A new node is added before the current head node.

Steps

1. Create a new node.
2. Connect it with the head and last node.
3. Update the head pointer.
4. Maintain circular links.

Example

Before insertion:

[20] ⇄ [30]

Insert 10

After insertion:

[10] ⇄ [20] ⇄ [30]

2. Insert at End

The new node is inserted after the last node.

Example

Before insertion:

[10] ⇄ [20]

Insert 30

After insertion:

[10] ⇄ [20] ⇄ [30]

3. Insert at Specific Position

A node can also be inserted between two existing nodes.

Example

Before insertion:

[10] ⇄ [30]

Insert 20 at position 2.

After insertion:

[10] ⇄ [20] ⇄ [30]

Deletion Operations

1. Delete from Beginning

The first node is removed and the next node becomes the new head.

Example

Before deletion:

[10] ⇄ [20] ⇄ [30]

After deletion:

[20] ⇄ [30]

2. Delete from End

The last node is removed from the list.

Example

Before deletion:

[10] ⇄ [20] ⇄ [30]

After deletion:

[10] ⇄ [20]

3. Delete from Specific Position

A node at a particular position can be removed.

Example

Before deletion:

[10] ⇄ [20] ⇄ [30]

Delete 20

After deletion:

[10] ⇄ [30]

Searching

Searching means locating a node containing a specific value.

Steps

1. Start from the head node.
2. Compare each node value with the target value.
3. Continue traversal until the starting node is reached again.
4. If matched, return the position.

Example

[10] ⇄ [20] ⇄ [30]

Search 30

Result: Found at position 3

Advantages of Circular Doubly Linked List

1. Bidirectional Traversal

Nodes can be traversed both forward and backward.

2. Continuous Navigation

Traversal can continue repeatedly without interruption.

3. Efficient Insertions and Deletions

Operations become easier because neighboring nodes are directly accessible.

4. Useful in Real-Time Applications

CDLL is commonly used in:

• Music players
• Browser tabs
• Image galleries
• Navigation systems
• Task scheduling systems

Disadvantages of Circular Doubly Linked List

1. Extra Memory Requirement

Each node stores two pointers, increasing memory usage.

2. Complex Implementation

Managing both circular and doubly linked connections requires careful coding.

3. Difficult Debugging

Incorrect pointer updates may create infinite loops.

Applications of Circular Doubly Linked List

Circular doubly linked lists are widely used in:

• Undo and redo functionality
• Circular navigation systems
• CPU scheduling
• Multimedia playlists
• Browser history management
• Game development

Time Complexity

If a tail pointer is maintained, insertion and deletion at the end can also be performed in O(1).

Space Complexity

Each node contains:

• Data field
• Previous pointer
• Next pointer

For n nodes, total space complexity is: O(n)

C Program for Circular Doubly Linked List

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
};

struct Node* head = NULL;

void insertAtEnd(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;

    if(head == NULL) {
        head = newNode;
        newNode->next = head;
        newNode->prev = head;
        return;
    }

    struct Node* last = head->prev;

    last->next = newNode;
    newNode->prev = last;
    newNode->next = head;
    head->prev = newNode;
}

void display() {
    if(head == NULL)
        return;

    struct Node* temp = head;

    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while(temp != head);
}

int main() {
    insertAtEnd(10);
    insertAtEnd(20);
    insertAtEnd(30);

    display();

    return 0;
}

Difference Between Doubly Linked List and Circular Doubly Linked List

Conclusion

A Circular Doubly Linked List is an advanced linked data structure that combines the features of circular and doubly linked lists. It allows continuous traversal in both d