Circular Doubly Linked List

1. Circular Doubly Linked List Traversal
2. Circular Doubly Linked List Insertion
3. Circular Doubly Linked List Insertion Illustration
4. Circular Doubly Linked List Traversal & Insertion Implementation
5. 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.

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.

Circular Doubly Linked List Insertion

There are 3 different cases for insertion.

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

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

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.