# 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 the`head`

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 the`tail`

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`

as`head`

and`temp->prev`

as the`tail`

to insert`temp`

between`head`

and`tail`

. - ##### Set
`tail->next`

and`head->prev`

as a`temp`

to complete insertion. - ##### Set
`head`

as a`temp`

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 point`temp->prev`

and`temp->next`

to itself and set it as`head`

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 to`head`

. - ##### Iterate until we find the node with
`data`

=`X`

. Store its next node as`next`

. - ##### Set
`curr->next`

as`temp`

. - ##### Set
`temp->prev`

as`curr`

and`temp->next`

as`next`

. - ##### Finally, set
`next->prev`

as`temp`

.

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