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.

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

Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

Related Article - Data Structure

  • Linked List
  • Linked List Reversal
  • Related Article - Circular Doubly Linked List

  • Binary Search Tree Iterative Insert
  • Binary Search Tree Inorder Succesor