Circular Doubly Linked List: Structure, Logic & Implementation

What exactly is a Circular Doubly Linked List?

• 

  Mr. Pradyumn Singh / 13 days
• 20
• 15 min read

A Circular Doubly Linked List is a specific kind of linked list where each node has three key parts:

- Data Field: This is where the actual data is stored.

- Next Pointer: This points to the next node in the list.

- Previous Pointer: This points to the previous node in the list.

In a CDLL, the next pointer of the last node loops back to the first node, while the previous pointer of the first node connects back to the last node, creating a circular chain. This unique bidirectional and circular setup allows you to traverse the list in both directions without running into any null references.

Structure of a Node in CDLL

In C programming, a node in a CDLL can be defined as:

C program code :

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

Operations on a Circular Doubly Linked List

1. Insertion

a. At the Beginning:

To add a node at the start:

- First, allocate some memory for the new node.

- If the list is empty, make sure the new node points to itself for both next and prev.

- If the list isn’t empty, adjust the pointers for the new node, head, and tail accordingly.

b. At the End:

To add a node at the end:

- Start by allocating memory for the new node.

- If the list is empty, again, point the new node's next and prev to itself.

- If the list has nodes, adjust the pointers for the new node, tail, and head as needed.

c. At a Specific Position:

To insert a node at a specific position:

- Traverse the list until you reach the desired spot.

- Adjust the pointers of the surrounding nodes to include the new node.

2. Deletion

a. From the Beginning:

To remove the first node:

- If the list is empty, just return.

- If there’s only one node, free it and set the head to NULL.

- If there are multiple nodes, adjust the pointers of the head and tail, then free the old head.

b. From the End:

To remove the last node:

- If the list is empty, return.

- If there’s only one node, free it and set the head to NULL.

- If there are more nodes, adjust the pointers of the tail and head, then free the old tail.

c. From a Specific Position:

To delete a node from a specific position:

- Traverse to the desired position.

- Adjust the pointers of the surrounding nodes to exclude the node you want to remove.

- Finally, free the target node.

3. Traversal

You can traverse the list in both directions:

a. Forward Traversal:

- Start from the head and follow the next pointers until you loop back to the head.

b. Backward Traversal:

- Start from the tail and follow the previous pointers until you return to the tail.

4. Searching

To find a specific value in the list:

- Start at the beginning and move through each node.

- Check if the data in each node matches the target value.

- If you find it, return the position; if not, keep going until you loop back to the start.

5. Reversing the List

To flip the list around:

- Go through the list, swapping the next and previous pointers for each node.

- Make sure to update the head pointer to point to the last node you processed.

Advantages of Circular Doubly Linked List

- Bidirectional Traversal: You can move through the list in both directions—forward and backward.

- Circular Nature: There are no null references, allowing for endless traversal of the list.

- Efficient Insertions/Deletions: You can easily insert and delete nodes at both ends.

- Useful in Applications: Perfect for scenarios like music playlists, undo-redo features, and circular buffers.

Disadvantages of Circular Doubly Linked List

- Increased Memory Usage: Each node needs extra memory for two pointers.

- Complex Implementation: It's trickier to implement and manage than singly linked lists.

- Risk of Infinite Loops: If not handled properly, you might end up with infinite loops during traversal.

Applications of Circular Doubly Linked Lists

- Music Players: They’re perfect for managing playlists, allowing songs to play in a continuous loop.

- Undo-Redo Functionality: These lists are great for implementing undo and redo features in software applications, making it easy to revert changes.

- Memory Management: They help in managing free memory blocks within operating systems efficiently.

- Navigation Systems: Circular doubly linked lists can also be used in navigation systems, enabling movement both forward and backward seamlessly.

Implementation Example in C

C program example :

#include 
#include 
 
struct Node {
	int data;
	struct Node* next;
	struct Node* prev;
};
 
struct Node* head = NULL;
 
// Function to create a new node
struct Node* createNode(int data) {
	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = newNode->prev = newNode;
	return newNode;
}
 
// Function to insert at the end
void insertEnd(int data) {
	struct Node* newNode = createNode(data);
	if (head == NULL) {
    	head = newNode;
    	return;
	}
	struct Node* tail = head->prev;
 
    tail->next = newNode;
    newNode->prev = tail;
    newNode->next = head;
    head->prev = newNode;
}
 
// Function to display the list
void display() {
	if (head == NULL) {
        printf("List is empty.\n");
    	return;
	}
	struct Node* temp = head;
	do {
        printf("%d ", temp->data);
    	temp = temp->next;
	} while (temp != head);
    printf("\n");
}
 
int main() {
    insertEnd(10);
    insertEnd(20);
    insertEnd(30);
	display();
	return 0;
}

Output :

10 20 30

Memory Allocation in Circular Doubly Linked List

One key feature of circular doubly linked lists is how they handle dynamic memory allocation. Unlike arrays, which require a fixed size to be set ahead of time, the nodes in a CDLL are created on the fly using functions like malloc() in C. This flexibility allows the list to expand or contract as needed while the program runs. However, it also means that you need to be vigilant about memory management to prevent problems like memory leaks or segmentation faults. It's crucial to use free() properly and manage dangling pointers when you're deleting nodes or completely destroying the list.

Time Complexity Analysis

When it comes to evaluating the efficiency of any data structure, time complexity is a key factor. For a circular doubly linked list:

- Insertion at the beginning or end: O(1), thanks to direct access to the head and tail nodes.

- Deletion at the beginning or end: O(1), for the same reason of immediate access.

- Traversal/Search: O(n), since you may need to check each node one by one in the worst-case scenario.

- Insertion/Deletion at a specific position: O(n), as this requires you to traverse to that position first.

This makes CDLLs more efficient than arrays for operations like inserting and deleting at the ends, but they can be a bit slower than indexed structures like arrays when it comes to direct access.

Conclusion

The Circular Doubly Linked List is a versatile data structure that brings both flexibility and efficiency to a variety of applications. Its unique ability to traverse in both directions, combined with its circular design, makes it perfect for situations that require ongoing navigation.

If you're eager to enhance your grasp of data structures and algorithms, signing up for a thorough course can really help. The Data Structures Course in Noida, offered by Uncodemy, dives deep into these topics, providing practical examples and hands-on experience to help you master the concepts.

FAQs

Q1: What’s the main difference between a singly linked list and a circular doubly linked list?

A: A singly linked list only allows you to move in one direction and has null references at the ends. On the other hand, a circular doubly linked list lets you traverse in both directions and connects the last node back to the first, creating a loop.

Q2: When is it best to use a circular doubly linked list instead of other types?

A: CDLLs are perfect for applications that need continuous traversal, like music playlists, or when you frequently need to insert or delete items from both ends.

Q3: Are there any downsides to using a circular doubly linked list?

A: Absolutely, they require more memory because of the extra pointers and can be trickier to implement compared to singly linked lists.

Q4: How does a circular doubly linked list deal with empty lists?

A: In an empty CDLL, the head pointer is set to NULL. It’s important to always check for this condition during operations to prevent errors.

Q5: Can circular doubly linked lists be utilized in real-time systems?

A: Yes, their efficient traversal and modification capabilities make them a great fit for real-time applications.