Last Updated on April 19, 2023 by Prepbytes

A circular doubly linked list is a data structure that consists of a collection of nodes, where each node contains a data element and two pointers: one that points to the next node in the list and another that points to the previous node in the list. In a circular doubly linked list, the last node points to the first node, creating a circular structure. Here we are going to study the doubly circular linked list introduction and insertion. A doubly circular linked list is a linked list that has the features of both the lists i.e. Doubly linked list and circular linked list. In a doubly circular linked list, two nodes are connected or linked together by the previous and the next pointers, and the last node of the doubly circular linked list is connected to the first node of the circular doubly linked list. Before learning the circular doubly linked list, let us first look at the Features of a Doubly Linked List.

## Doubly Linked List

A Doubly Linked List is a linear data structure that is represented as a set of nodes and has the following features.

- A node in a doubly linked list is an object which contains a value, a reference to the previous node of the list, and a reference to the next node of the list.
- A doubly linked list consists of two node pointers
**next**and**prev**, which point to the next and previous nodes, respectively. - Unlike the singly linked list, we can traverse in both directions in a doubly-linked list with the help of these next and prev pointers.

## Doubly Circular Linked List

A Doubly Circular Linked List is a type of data structure that has the characteristics of both a Circular Linked List and a Doubly Linked List. It is a list where the final node points to the first node, creating a loop. This means that we can move in both directions when traversing the doubly circular linked list, and the first node points to the last node as its previous node, while the last node points to the first node as its next node. A general circular doubly linked list is shown in the image below.

### Structure of Node in a Doubly Circular Linked List

The node in a circular doubly linked list is defined with the following lines of code.

#include<stdio.h> #include<stdlib.h> struct Node { int data; struct Node *next; struct Node *prev; };

struct node { int data; struct node *next; // Pointer to next node struct node *prev; // Pointer to previous node };

static class Node { int data; Node next; Node prev; };

class Node: def __init__(self, data = None, prev = None, next = None): self.data = data self.prev = prev self.next = next

### Insertion in Doubly Circular Linked List

We have to create a Doubly Circular Linked List by inserting nodes in the list, i.e., by adding nodes at the start or the end of the List, and after performing all the insertion operations, we need to output the created list.

Suppose we are given an empty linked list and some insertion operations to perform on the linked list. Look at the figure below to see how insertions will happen.

The above images provide a clear explanation of how the insertion in a doubly circular linked list is done. Now let’s move further to design the algorithm for Insertion in the doubly circular linked list.

### Algorithm for Insertion in Circular Doubly Linked List

We will follow the given steps for the insertion of nodes in Circular Doubly Linked list.

- Firstly, we will initialize the start node as NULL, and then we can continue to insert the nodes.
- The following cases persist if we want to insert the nodes:
- a)
**If the list is empty**- We will create a
**new_node**with the given value. - Assign the
**prev**and**next**of**new_node**to the new_node itself. - Update
**new_node**as the**start**node.

- We will create a
- b)
**Insert at begin**- We will create a
**new_node**with the given value. - Assign the
**next**of**new_node**as the**start**node. - Assign the
**prev**of**new_node**to the**last**node of the linked list. - Update the
**prev**of the**start**node and**next**of the**last**node as**new_node.** - Update
**new_node**as the**start**node.

- We will create a
- c)
**Insert at the end**- We will create a
**new_node**with the given value. - Assign the
**next**of**new_node**as the**start**node. - Assign the
**prev**of**new_node**to the**last**node of the list. - Update the
**prev**of the**start**node and**next**of the**last**node as**new_node.** - Update
**new_node**as the last node.

- We will create a

- a)
- Using these above insertion operations, our Doubly Circular Linked List will get created.
- Now, finally, once we have inserted all the nodes in the list, we can print the list.

### Dry Run for Insertion in Circular Doubly Linked List

Let’s dry-run the above algorithm for a better understanding of the insertion in the Doubly Circular Linked List.

### Code Implementation of Insertion in Doubly Circular Linked List

The code for the insertion in Circular Doubly Linked List in C, Java, and Python is given below.

#include<stdio.h> #include<stdlib.h> struct Node { int data; struct Node *next; struct Node *prev; }; // Function to insert at the end void insertEnd(struct Node** start, int value) { if (*start == NULL) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = value; new_node->next = new_node->prev = new_node; *start = new_node; return; } // If list is not empty /* Find last node */ struct Node *last = (*start)->prev; // Create Node dynamically struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = value; // Start is going to be next of new_node new_node->next = *start; // Make new node previous of start (*start)->prev = new_node; // Make last previous of new node new_node->prev = last; // Make new node next of old last last->next = new_node; } // Function to insert Node at the beginning // of the List, void insertBegin(struct Node** start, int value) { // Pointer points to last Node struct Node *last = (*start)->prev; struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = value; // Inserting the data // setting up previous and next of new node new_node->next = *start; new_node->prev = last; // Update next and previous pointers of start // and last. last->next = (*start)->prev = new_node; // Update start pointer *start = new_node; } // Function to insert node with value as value1. // The new node is inserted after the node with // with value2 void insertAfter(struct Node** start, int value1, int value2) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = value1; // Inserting the data // Find node having value2 and next node of it struct Node *temp = *start; while (temp->data != value2) temp = temp->next; struct Node *next = temp->next; // insert new_node between temp and next. temp->next = new_node; new_node->prev = temp; new_node->next = next; next->prev = new_node; } void display(struct Node* start) { struct Node *temp = start; printf("\nTraversal in forward direction \n"); while (temp->next != start) { printf("%d ", temp->data); temp = temp->next; } printf("%d ", temp->data); printf("\nTraversal in reverse direction \n"); struct Node *last = start->prev; temp = last; while (temp->prev != last) { printf("%d ", temp->data); temp = temp->prev; } printf("%d ", temp->data); } /* Driver program to test above functions*/ int main() { /* Start with the empty list */ struct Node* start = NULL; // Insert 5. So linked list becomes 5->NULL insertEnd(&start, 5); // Insert 4 at the beginning. So linked // list becomes 4->5 insertBegin(&start, 4); // Insert 7 at the end. So linked list // becomes 4->5->7 insertEnd(&start, 7); // Insert 8 at the end. So linked list // becomes 4->5->7->8 insertEnd(&start, 8); // Insert 6, after 5. So linked list // becomes 4->5->6->7->8 insertAfter(&start, 6, 5); printf("Created circular doubly linked list is: "); display(start); return 0; }

class Prepbytes { static Node start; static class Node { int data; Node next; Node prev; }; static void insertEnd(int value) { if (start == null) { Node new_node = new Node(); new_node.data = value; new_node.next = new_node.prev = new_node; start = new_node; return; } Node last = (start).prev; Node new_node = new Node(); new_node.data = value; new_node.next = start; (start).prev = new_node; new_node.prev = last; last.next = new_node; } static void insertBegin(int value) { if (start == null) { Node new_node = new Node(); new_node.data = value; new_node.next = new_node.prev = new_node; start = new_node; return; } Node last = (start).prev; Node new_node = new Node(); new_node.data = value; new_node.next = start; new_node.prev = last; last.next = (start).prev = new_node; start = new_node; } static void display() { Node temp = start; System.out.printf("\nTraversal in forward direction \n"); while (temp.next != start) { System.out.printf("%d ", temp.data); temp = temp.next; } System.out.printf("%d ", temp.data); System.out.printf("\nTraversal in reverse direction \n"); Node last = start.prev; temp = last; while (temp.prev != last) { System.out.printf("%d ", temp.data); temp = temp.prev; } System.out.printf("%d ", temp.data); } public static void main(String[] args) { Node start = null; insertEnd(7); insertBegin(3); insertBegin(4); insertEnd(6); insertEnd(9); insertBegin(8); insertBegin(5); System.out.printf("Created circular doubly linked list is: "); display(); } }

start = None class Node: def __init__(self, data): self.data = data self.next = None self.prev = None def insertEnd(value) : global start if (start == None) : new_node = Node(0) new_node.data = value new_node.next = new_node.prev = new_node start = new_node return last = (start).prev new_node = Node(0) new_node.data = value new_node.next = start (start).prev = new_node new_node.prev = last last.next = new_node def insertBegin( value) : global start if start == None: new_node = Node(0) new_node.data = value new_node.next = new_node.prev = new_node start = new_node return last = (start).prev new_node = Node(0) new_node.data = value new_node.next = start new_node.prev = last last.next = (start).prev = new_node start = new_node def display() : global start temp = start print ("Traversal in forward direction:") while (temp.next != start) : print (temp.data, end = " ") temp = temp.next print (temp.data) print ("Traversal in reverse direction:") last = start.prev temp = last while (temp.prev != last) : print (temp.data, end = " ") temp = temp.prev print (temp.data) if __name__ == '__main__': start = None insertEnd(7) insertBegin(3) insertBegin(4) insertEnd(6) insertEnd(9) insertBegin(8) insertBegin(5) print ("Created circular doubly linked list is: ") display()

**Output**

```
Created circular doubly linked list is:
Traversal in forward direction
5 8 4 3 7 6 9
Traversal in reverse direction
9 6 7 3 4 8 5
```

**Time Complexity:** O(1) for insertion as insertion is a constant operation.

**Space Complexity:** O(n), space is required to create n nodes.

## Advantages of Circular Doubly Linked List

Advantages of Doubly Circular Linked List are given below:

- Circular Doubly Linked List allows traversal in both forward and backward directions.
- Since it is circular, it allows easy insertion and deletion of nodes at the beginning and end of the list in O(1) time.

## Disadvantages of Circular Doubly Linked List

Some of the Disadvantages of Doubly Circular Linked List are listed below.

- The implementation of a Circular Doubly Linked List is more complex than a simple linked list, so it requires more time and effort to implement.
- Doubly Circular Linked List requires more space than a simple linked list because each node needs to store two pointers instead of one.

## Applications of Circular Doubly Linked List

Doubly Circular Linked Lists have various applications in daily life. Some of these are mentioned below:

- Doubly Circular Linked List is commonly used in music players to maintain a playlist, where the songs can be played in both forward and backward directions.
- A Doubly Circular Linked List can be used to implement browser history, where we can move forward and backward through our browsing history.

**Conclusion**

In conclusion, we conclude that a circular doubly linked list is a data structure where each node contains a data element and two pointers. In this blog, we have discussed the Doubly Circular Linked List Introduction and Doubly circular linked list Insertion. We have also discussed teh advantages, disadvantages and applications of the Doubly Circular Linked List. We hope you will understand the doubly circular linked list clearly.

## Frequently Asked Questions (FAQs)

Some FAQs related to the Doubly Circular Linked List are given below.

**Ques 1. What is the difference between a doubly linked list and a doubly circular linked list?**

**Ans.** In the doubly linked list, every node holds the address of the previous node as well as the next node whereas, in the doubly circular linked list, every node holds the address of the previous node as well as the next node and the first node holds the pointer of the last node, which makes the doubly linked list as a doubly circular linked list.

**Ques 2. What is a circular linked list?**

**Ans.** In a circular linked list, all the nodes are connected together and form a ring. The last node and the first node are connected together which forms a ring and In the circular linked list, there is no NULL pointer at the end of the list.

**Ques 3. What is the time complexity of searching for a node in a doubly circular linked list?**

**Ans.** The time complexity of searching for a node in a doubly circular linked list is O(n) in the worst case, where n is the number of nodes in the list.