4 mins read
Last updated: 21 Feb 2025
6490 views
A circular doubly linked list is a type of linked list where each node is connected to both its previous and next nodes, and the last node links back to the first node. This structure allows for efficient bidirectional traversal and looping through the list. In this guide, we will learn the basics, operations, and applications of circular doubly linked lists.
A circular doubly linked list is a special kind of list used in DSA to store data. In this list, each piece of data is stored in a node. Every node is connected to two other nodes: one before it and one after it. This makes it easy to move forwards and backwards through the list.
What's unique about a circular doubly linked list is that the last node connects back to the first node, forming a circle. So, if you start at any node and keep moving forwards or backwards, you will eventually come back to the starting node.
This circular connection makes it different from regular linked lists, where the last node simply points to nothing (or "null").
Imagine a circular doubly linked list like a Ferris wheel. Each node is like a seat on the Ferris wheel. You can move to the seat next to you (forward) or the seat behind you (backward). And when you reach the last seat, instead of stopping, you move to the first seat again, just like how the Ferris wheel goes round and round.
This structure is useful in many computer applications where you need to cycle through data repeatedly, such as in task scheduling or managing playlists in a media player.
A circular doubly linked list is made up of nodes, where each node has three main components: data, a next pointer, and a previous pointer.
Data: This is the actual information or value stored in the node.
Next Pointer: This pointer points to the next node in the list.
Previous Pointer: This pointer points to the previous node in the list.
In a circular doubly linked list, the next pointer of the last node points to the first node, creating a circular loop.
Similarly, the previous pointer of the first node points to the last node, allowing bidirectional traversal in a circular manner.
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class CircularDoublyLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
new_node.next = new_node
new_node.prev = new_node
else:
tail = self.head.prev
tail.next = new_node
new_node.prev = tail
new_node.next = self.head
self.head.prev = new_node
def display(self):
if not self.head:
return
temp = self.head
while True:
print(temp.data, end=' ')
temp = temp.next
if temp == self.head:
break
print()
# Example Usage
cdll = CircularDoublyLinkedList()
cdll.append(1)
cdll.append(2)
cdll.append(3)
cdll.display() # Output: 1 2 3 #include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
struct Node* head = NULL;
void append(int data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
if (!head) {
head = new_node;
new_node->next = new_node;
new_node->prev = new_node;
} else {
struct Node* tail = head->prev;
tail->next = new_node;
new_node->prev = tail;
new_node->next = head;
head->prev = new_node;
}
}
void display() {
if (!head) return;
struct Node* temp = head;
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
// Example Usage
int main() {
append(1);
append(2);
append(3);
display(); // Output: 1 2 3
return 0;
}#include <iostream>
struct Node {
int data;
Node* next;
Node* prev;
};
class CircularDoublyLinkedList {
private:
Node* head;
public:
CircularDoublyLinkedList() : head(nullptr) {}
void append(int data) {
Node* new_node = new Node{data, nullptr, nullptr};
if (!head) {
head = new_node;
new_node->next = new_node;
new_node->prev = new_node;
} else {
Node* tail = head->prev;
tail->next = new_node;
new_node->prev = tail;
new_node->next = head;
head->prev = new_node;
}
}
void display() {
if (!head) return;
Node* temp = head;
do {
std::cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
std::cout << std::endl;
}
};
// Example Usage
int main() {
CircularDoublyLinkedList cdll;
cdll.append(1);
cdll.append(2);
cdll.append(3);
cdll.display(); // Output: 1 2 3
return 0;
}class Node {
int data;
Node next;
Node prev;
public Node(int data) {
this.data = data;
}
}
class CircularDoublyLinkedList {
private Node head = null;
public void append(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
newNode.next = newNode;
newNode.prev = newNode;
} else {
Node tail = head.prev;
tail.next = newNode;
newNode.prev = tail;
newNode.next = head;
head.prev = newNode;
}
}
public void display() {
if (head == null) return;
Node temp = head;
do {
System.out.print(temp.data + " ");
temp = temp.next;
} while (temp != head);
System.out.println();
}
public static void main(String[] args) {
CircularDoublyLinkedList cdll = new CircularDoublyLinkedList();
cdll.append(1);
cdll.append(2);
cdll.append(3);
cdll.display(); // Output: 1 2 3
}
}Inserting at the Beginning:
Create a new node.
Adjust the next pointer of the new node to point to the head.
Adjust the previous pointer of the head to point to the new node.
Set the new node as the new head.
Update the previous pointer of the new head to point to the last node, and the next pointer of the last node to point to the new head.
Inserting at the End:
Create a new node.
Adjust the previous pointer of the new node to point to the last node.
Adjust the next pointer of the last node to point to the new node.
Set the next pointer of the new node to point to the head.
Update the previous pointer of the head to point to the new node.
Inserting at a Given Position:
Traverse the list to find the position.
Adjust the pointers of the new node and the nodes at the position to insert the new node.
Deleting from the Beginning:
Adjust the next pointer of the last node to point to the second node.
Set the second node as the new head.
Adjust the previous pointer of the new head to point to the last node.
Deleting from the End:
Adjust the next pointer of the second-to-last node to point to the head.
Adjust the previous pointer of the head to point to the second-to-last node.
Deleting a Specific Node:
Traverse the list to find the node.
Adjust the pointers of the previous and next nodes to bypass the node to be deleted.
Forward Traversal:
Start from the head and move forward using the next pointer.
Continue until you reach the head again.
Backward Traversal:
Start from the head and move backward using the previous pointer.
Continue until you reach the head again.
Traverse the list using either the next or previous pointers.
Compare each node's data with the target value until the value is found or the list is fully traversed.
This operation involves reversing the direction of traversal by swapping the next and previous pointers of each node in the list. After reversing, the head node's next pointer will point to what was previously its previous node, and vice versa.
Splitting a circular doubly linked list divides it into two separate circular doubly linked lists. This is done by finding the middle of the list and then adjusting the next and previous pointers to break the list into two parts.
Merging involves combining two circular doubly linked lists into a single circular doubly linked list. This requires connecting the last node of the first list to the head of the second list, and vice versa.
Sorting a circular doubly linked list arranges the nodes in a specific order, usually ascending or descending. This can be done using various sorting algorithms like bubble sort, insertion sort, or merge sort, applied to the circular doubly linked structure.
This operation involves traversing the list and removing nodes that have duplicate data values, ensuring that each value appears only once in the list.
This operation counts the number of nodes in the circular doubly linked list by traversing from the head node until it loops back to the head.
Task Scheduling: Efficiently manages tasks in operating systems, allowing for easy rotation through tasks.
Music or Video Playlists: Implements repeat functionality in media players, enabling seamless looping through tracks or videos.
Real-Time Systems: Used in systems requiring constant rotation through a set of tasks or processes.
Buffer Management: Manages buffers in scenarios where data needs to be processed in a circular manner, such as in network routers.
Undo/Redo Functionality: Supports undo and redo operations in text editors or applications by maintaining a circular list of actions.
Game Development: Implements game elements that cycle continuously, such as rotating game characters or objects.
Cache Implementation: Implements circular buffers in cache systems to manage recently used data efficiently.
Data Stream Processing: Manages streams of data that need to be processed in a cyclical manner.
Simulation Systems: Used in simulations where entities need to be processed repeatedly in a circular manner.
Token Passing in Networks: Implements token-passing protocols in network communication for efficient data transfer.
Allows movement in both forward and backward directions, enhancing flexibility in data manipulation.
Naturally supports circular or repetitive tasks due to its circular structure.
Enables efficient insertion and deletion of nodes at both ends or in the middle without needing to traverse the entire list.
Maintains O(1) time complexity for insertions and deletions, making it suitable for real-time applications.
Eliminates null pointers for the next and previous nodes, reducing the chance of errors related to null references.
Requires extra memory for storing two pointers (next and previous) for each node.
More complex to implement and manage compared to singly linked lists or simple arrays.
Circular nature can make debugging and troubleshooting more challenging, as errors can propagate indefinitely.
Lacks a clear end or tail node, which can complicate operations that need to identify the end of the list.
Slight performance overhead due to the need to maintain two pointers and ensure the circular links are correctly updated.
Each node contains data, a pointer to the next node, and a pointer to the previous node.
Create a new node, adjust its pointers to point to the head and the last node, and update the head and the previous node's pointers to include the new node.
Adjust the pointers of the second-to-last node to point to the head and update the head's previous pointer to the new last node.
Yes, you can traverse the list and compare each node's data with the target value until you find the element or return to the head.
An empty list is represented by a head pointer set to null. Insertion operations need to handle this case by properly initializing the head.
Circular Linked List in Data Structure (Types, Examples, Operations, More)
Hash Tables in Data Structure (With Implementation & Examples)