Harshit Jindal Oct 12, 2023

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.

• ##### 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.

• ##### 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 in the Middle of Circular Doubly Linked List

Let `X` be the value of the node after which we want to insert the element.

## 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) {
Node* temp = new Node;
temp->data = value;
temp->next = temp->prev = temp;
return;
}
Node* temp = new Node;
temp->data = value;
temp->prev = tail;
tail->next = temp;
}

void insertBegin(Node** head, int value) {

Node* temp = new Node;
temp->data = value;
temp->prev = tail;

}

void insertAfter(Node** head, int value1, int value2) {
Node* temp = new Node;
temp->data = value1;
while (curr->data != value2) curr = curr->next;
Node* next = curr->next;

curr->next = temp;
temp->prev = curr;
temp->next = next;
next->prev = temp;
}

printf("Forward Traversal:");
printf("%d ", curr->data);
curr = curr->next;
}
printf("%d ", curr->data);

printf("\nBackward Traversal:");
curr = tail;
while (curr->prev != tail) {
printf("%d ", curr->data);
curr = curr->prev;
}
printf("%d ", curr->data);
cout << "\n";
}

int main() {
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 average-case time complexity of traversal is of the order of `O(n)`. The time complexity is of the order of `O(n)`.

• Best Case

The best-case time complexity is `O(n)`. It is the same as average-case time complexity.

• Worst Case

The worst-case time complexity is `O(n)`. It is the same as best-case 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 `n-1` nodes, and hence the time complexity is `O(n)`.

• Best Case

The best-case time complexity is `O(1)` for all `3` cases.

• Worst Case

The worst-case time complexity is `O(1)` for the first two cases but `O(n)` for the third case. It is the same as average-case 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.