Circular Doubly Linked List
 Circular Doubly Linked List Traversal
 Circular Doubly Linked List Insertion
 Circular Doubly Linked List Insertion Illustration
 Circular Doubly Linked List Traversal & Insertion Implementation
 Circular Doubly Linked List Traversal & Insertion Algorithm Complexity
A Circular Doubly Linked List is a combination of both the circular linked list and doubly linked list. Its two nodes are connected by both the previous and next pointer. The last node’s next pointer points to the first node and the first node’s previous pointer points to the last node. It can be traversed from both directions and jumping from tail to head or from head to tail. It is also used for the implementation of advanced data structures like Fibonacci Heap.
Circular Doubly Linked List Traversal
We can traverse circular doubly linked list simply by keeping check of the condition that the next node in the iteration is not head
and move temp
from temp>next
or temp>prev
depending on forward / backward iteration.
Forward Direction
Let the head
be the first node of the linked list.

Initialize
curr
pointing to thehead
node of the linked list. 
While
curr
does not reach the end of the list i.e.curr>next
!=head
, do the following: print the data stored inside the current node.
curr=curr>next
;
Similarly, we can do the backward traversal by starting from the tail
and changing curr
to curr>prev
.
Reverse Direction
Let the tail
i.e. head>prev
be the last node of the linked list.

Initialize
curr
pointing to thetail
node of the linked list. 
While
curr
does not reach the start of the list i.e.curr>prev
!=tail
, do the following: print the data stored inside the current node.
curr=curr>prev
Circular Doubly Linked List Insertion
There are 3
different cases for insertion.
Insert an Element at the Beginning of Circular Doubly Linked List

Create a node
temp
with the given data. 
Set
temp>next
ashead
andtemp>prev
as thetail
to inserttemp
betweenhead
andtail
. 
Set
tail>next
andhead>prev
as atemp
to complete insertion. 
Set
head
as atemp
to move the head to the newly inserted element.
Insert an Element at the End of the Circular Doubly Linked List

Create a node
temp
with the given data. 
If the list is empty, create a node
temp
with given data and pointtemp>prev
andtemp>next
to itself and set it ashead
and return. 
Perform the steps used to insert at the beginning, excluding the last step.
Insert an Element in the Middle of Circular Doubly Linked List
Let X
be the value of the node after which we want to insert the element.

Create a node
temp
with the given data. 
Initialize pointer
curr
pointing tohead
. 
Iterate until we find the node with
data
=X
. Store its next node asnext
. 
Set
curr>next
astemp
. 
Set
temp>prev
ascurr
andtemp>next
asnext
. 
Finally, set
next>prev
astemp
.
Circular Doubly Linked List Insertion Illustration
Insert an Element at the Beginning of Circular Doubly Linked List
Insert an Element at the End of the Circular Doubly Linked List
Insert an Element in the Middle of Circular Doubly Linked List
Circular Doubly Linked List Traversal & Insertion Implementation
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
Node* prev;
};
void insertEnd(Node** head, int value) {
if (*head == NULL) {
Node* temp = new Node;
temp>data = value;
temp>next = temp>prev = temp;
*head = temp;
return;
}
Node* tail = (*head)>prev;
Node* temp = new Node;
temp>data = value;
temp>next = *head;
(*head)>prev = temp;
temp>prev = tail;
tail>next = temp;
}
void insertBegin(Node** head, int value) {
Node* tail = (*head)>prev;
Node* temp = new Node;
temp>data = value;
temp>next = *head;
temp>prev = tail;
tail>next = (*head)>prev = temp;
*head = temp;
}
void insertAfter(Node** head, int value1, int value2) {
Node* temp = new Node;
temp>data = value1;
Node* curr = *head;
while (curr>data != value2) curr = curr>next;
Node* next = curr>next;
curr>next = temp;
temp>prev = curr;
temp>next = next;
next>prev = temp;
}
void printList(Node* head) {
Node* curr = head;
printf("Forward Traversal:");
while (curr>next != head) {
printf("%d ", curr>data);
curr = curr>next;
}
printf("%d ", curr>data);
printf("\nBackward Traversal:");
Node* tail = head>prev;
curr = tail;
while (curr>prev != tail) {
printf("%d ", curr>data);
curr = curr>prev;
}
printf("%d ", curr>data);
cout << "\n";
}
int main() {
Node* head = NULL;
insertEnd(&head, 2);
insertBegin(&head, 1);
insertEnd(&head, 4);
printList(head);
insertEnd(&head, 5);
insertAfter(&head, 3, 2);
printList(head);
return 0;
}
Circular Doubly Linked List Traversal & Insertion Algorithm Complexity
Traversal
Time Complexity
 Average Case
To traverse the complete doubly linked list, we have to visit every node. If it has n
nodes, the averagecase time complexity of traversal is of the order of O(n)
. The time complexity is of the order of O(n)
.
 Best Case
The bestcase time complexity is O(n)
. It is the same as averagecase time complexity.
 Worst Case
The worstcase time complexity is O(n)
. It is the same as bestcase time complexity.
Space Complexity
The traversal algorithm’s space complexity is O(1)
as no extra space other than curr
pointer is required.
Insertion
Time Complexity
 Average Case
The insertion of an element for insertion at tail
and head
requires a maximum of 4
link changes and hence the time complexity is O(1)
. But for insertion in between, we might have to travel n1
nodes, and hence the time complexity is O(n)
.
 Best Case
The bestcase time complexity is O(1)
for all 3
cases.
 Worst Case
The worstcase time complexity is O(1)
for the first two cases but O(n)
for the third case. It is the same as averagecase time complexity.
Space Complexity
The insertion algorithm’s space complexity is O(1)
for all 3
types of insertion.
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn