How many NULL pointers are available in a circular doubly linked list?

Circular Doubly Linked List

Circular doubly linked list is a more complexed type of data structure in which a node contain pointers to its previous node as well as the next node. Circular doubly linked list doesn't contain NULL in any of the node. The last node of the list contains the address of the first node of the list. The first node of the list also contain address of the last node in its previous pointer.

A circular doubly linked list is shown in the following figure.

Due to the fact that a circular doubly linked list contains three parts in its structure therefore, it demands more space per node and more expensive basic operations. However, a circular doubly linked list provides easy manipulation of the pointers and the searching becomes twice as efficient.

Doubly Circular Linked List | Set 1 (Introduction and Insertion)

Prerequisite: Doubly Linked list, Circular Linked List
Circular Doubly Linked List has properties of both doubly linked list and circular linked list in which two consecutive elements are linked or connected by previous and next pointer and the last node points to first node by next pointer and also the first node points to last node by the previous pointer.

Following is representation of a Circular doubly linked list node in C/C++:

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

Insertion in Circular Doubly Linked List

Insertion in Circular Doubly Linked List

• Insertion at the end of list or in an empty list
  • Empty List (start = NULL): A node(Say N) is inserted with data = 5, so previous pointer of N points to N and next pointer of N also points to N. But now start pointer points to the first node the list.

• List initially contains some nodes, start points to first node of the List: A node(Say M) is inserted with data = 7, so previous pointer of M points to last node, next pointer of M points to first node and last node’s next pointer points to this M node and first node’s previous pointer points to this M node.

C++

// Function to insert at the end void insertEnd(struct Node** start, int value) { // If the list is empty, create a single node // circular and doubly list if (*start == NULL) { struct Node* new_node = new 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 */ Node *last = (*start)->prev; // Create Node dynamically struct Node* new_node = new 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; }

Java

// Function to insert at the end static void insertEnd(int value) { // If the list is empty, create a single // node circular and doubly list if (start == null) { Node new_node = new 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 Node last = (start).prev; // Create Node dynamically Node new_node = new 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; } // This code is contributed by rutvik_56

Python3

# Function to insert at the end def insertEnd(value) : global start # If the list is empty, create a # single node circular and doubly list if (start == None) : new_node = Node(0) new_node.data = value new_node.next = new_node.prev = new_node start = new_node return # If list is not empty # Find last node */ last = (start).prev # Create Node dynamically new_node = Node(0) 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 # This code is contributed by shivanisinghss2110

C#

// Function to insert at the end static void insertEnd(int value) { Node new_node; // If the list is empty, create a single node // circular and doubly list if (start == null) { new_node = new 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 */ Node last = (start).prev; // Create Node dynamically new_node = new 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; } // This code is contributed by Pratham76

Javascript

<script> // Function to insert at the end function insertEnd(value) { // If the list is empty, create a single // node circular and doubly list if (start == null) { var new_node = new 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 var last = (start).prev; // Create Node dynamically var new_node = new 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; } // This code contributed by aashish2995 </script>

• Insertion at the beginning of the list: To insert a node at the beginning of the list, create a node(Say T) with data = 5, T next pointer points to first node of the list, T previous pointer points to last node the list, last node’s next pointer points to this T node, first node’s previous pointer also points this T node and at last don’t forget to shift ‘Start’ pointer to this T node.

C++

// 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 = new 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; }

Java

// Function to insert Node at the beginning // of the List, static void insertBegin(int value) { // Pointer points to last Node Node last = (start).prev; Node new_node = new 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; } // this code is contributed by shivanisinghss2110

Python3

# Function to insert Node at the beginning # of the List, def insertBegin( value) : global start # Pointer points to last Node last = (start).prev new_node = Node(0) 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 # This code is contributed by shivanisinghss2110

C#

// Function to insert Node at the beginning // of the List, static void insertBegin(int value) { // Pointer points to last Node Node last = (start).prev; Node new_node = new 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; } // This code is contributed by shivanisinghss2110

Javascript

// Function to insert Node at the beginning // of the List, function insertBegin(value) { // Pointer points to last Node var last = start.prev; var new_node = new 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; } // This code is contributed by shivanisinghss2110

• Insertion in between the nodes of the list: To insert a node in between the list, two data values are required one after which new node will be inserted and another is the data of the new node.

C++

// 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 = new 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; }

Java

// Function to insert node with value as value1. // The new node is inserted after the node with // with value2 static void insertAfter(int value1, int value2) { Node new_node = new Node(); new_node.data = value1; // Inserting the data // Find node having value2 and next node of it Node temp = start; while (temp.data != value2) temp = temp.next; 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; } // this code is contributed by shivanisinghss2110

Python3

# Function to insert node with value as value1. # The new node is inserted after the node with # with value2 def insertAfter(value1, value2) : global start new_node = Node(0) new_node.data = value1 # Inserting the data # Find node having value2 and # next node of it temp = start while (temp.data != value2) : temp = temp.next 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 # this code is contributed by shivanisinghss2110

C#

// Function to insert node with value as value1. // The new node is inserted after the node with // with value2 static void insertAfter(int value1, int value2) { Node new_node = new Node(); new_node.data = value1; // Inserting the data // Find node having value2 and next node of it Node temp = start; while (temp.data != value2) temp = temp.next; 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; } // this code is contributed by shivanisinghss2110

Javascript

<script> // Function to insert node with value as value1. // The new node is inserted after the node with // with value2 function insertAfter(value1, value2) { var new_node = new Node(); // Inserting the data new_node.data = value1; // Find node having value2 and // next node of it var temp = start; while (temp.data != value2) temp = temp.next; var 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; } // This code is contributed by shivanisinghss2110 </script>

Following is a complete program that uses all of the above methods to create a circular doubly linked list.

C++

// C++ program to illustrate inserting a Node in // a Circular Doubly Linked list in begging, end // and middle #include <bits/stdc++.h> using namespace std; // Structure of a Node struct Node { int data; struct Node *next; struct Node *prev; }; // Function to insert at the end void insertEnd(struct Node** start, int value) { // If the list is empty, create a single node // circular and doubly list if (*start == NULL) { struct Node* new_node = new 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 */ Node *last = (*start)->prev; // Create Node dynamically struct Node* new_node = new 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 = new 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 = new 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"); 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; }

Java

// Java program to illustrate inserting a Node in // a Circular Doubly Linked list in begging, end // and middle import java.util.*; class GFG { static Node start; // Structure of a Node static class Node { int data; Node next; Node prev; }; // Function to insert at the end static void insertEnd(int value) { // If the list is empty, create a single node // circular and doubly list if (start == null) { Node new_node = new 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 */ Node last = (start).prev; // Create Node dynamically Node new_node = new 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, static void insertBegin(int value) { // Pointer points to last Node Node last = (start).prev; Node new_node = new 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 static void insertAfter(int value1, int value2) { Node new_node = new Node(); new_node.data = value1; // Inserting the data // Find node having value2 and next node of it Node temp = start; while (temp.data != value2) temp = temp.next; 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; } 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); } /* Driver code*/ public static void main(String[] args) { /* Start with the empty list */ Node start = null; // Insert 5. So linked list becomes 5.null insertEnd(5); // Insert 4 at the beginning. So linked // list becomes 4.5 insertBegin(4); // Insert 7 at the end. So linked list // becomes 4.5.7 insertEnd(7); // Insert 8 at the end. So linked list // becomes 4.5.7.8 insertEnd(8); // Insert 6, after 5. So linked list // becomes 4.5.6.7.8 insertAfter(6, 5); System.out.printf("Created circular doubly linked list is: "); display(); } } // This code is contributed by Rajput-Ji

Python3

# Python3 program to illustrate inserting # a Node in a Circular Doubly Linked list # in begging, end and middle start = None # Structure of a Node class Node: def __init__(self, data): self.data = data self.next = None self.prev = None # Function to insert at the end def insertEnd(value) : global start # If the list is empty, create a # single node circular and doubly list if (start == None) : new_node = Node(0) new_node.data = value new_node.next = new_node.prev = new_node start = new_node return # If list is not empty # Find last node */ last = (start).prev # Create Node dynamically new_node = Node(0) 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, def insertBegin( value) : global start # Pointer points to last Node last = (start).prev new_node = Node(0) 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 def insertAfter(value1, value2) : global start new_node = Node(0) new_node.data = value1 # Inserting the data # Find node having value2 and # next node of it temp = start while (temp.data != value2) : temp = temp.next 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 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) # Driver Code if __name__ == '__main__': global start # Start with the empty list start = None # Insert 5. So linked list becomes 5.None insertEnd(5) # Insert 4 at the beginning. So linked # list becomes 4.5 insertBegin(4) # Insert 7 at the end. So linked list # becomes 4.5.7 insertEnd(7) # Insert 8 at the end. So linked list # becomes 4.5.7.8 insertEnd(8) # Insert 6, after 5. So linked list # becomes 4.5.6.7.8 insertAfter(6, 5) print ("Created circular doubly linked list is: ") display() # This code is contributed by Arnab kundu

C#

// C# program to illustrate inserting a Node in // a Circular Doubly Linked list in begging, end // and middle using System; using System.Collections.Generic; class GFG { static Node start; // Structure of a Node public class Node { public int data; public Node next; public Node prev; }; // Function to insert at the end static void insertEnd(int value) { Node new_node; // If the list is empty, create a single node // circular and doubly list if (start == null) { new_node = new 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 */ Node last = (start).prev; // Create Node dynamically new_node = new 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, static void insertBegin(int value) { // Pointer points to last Node Node last = (start).prev; Node new_node = new 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 static void insertAfter(int value1, int value2) { Node new_node = new Node(); new_node.data = value1; // Inserting the data // Find node having value2 and next node of it Node temp = start; while (temp.data != value2) temp = temp.next; 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; } static void display() { Node temp = start; Console.Write("\nTraversal in forward direction \n"); while (temp.next != start) { Console.Write("{0} ", temp.data); temp = temp.next; } Console.Write("{0} ", temp.data); Console.Write("\nTraversal in reverse direction \n"); Node last = start.prev; temp = last; while (temp.prev != last) { Console.Write("{0} ", temp.data); temp = temp.prev; } Console.Write("{0} ", temp.data); } /* Driver code*/ public static void Main(String[] args) { /* Start with the empty list */ Node start = null; // Insert 5. So linked list becomes 5.null insertEnd(5); // Insert 4 at the beginning. So linked // list becomes 4.5 insertBegin(4); // Insert 7 at the end. So linked list // becomes 4.5.7 insertEnd(7); // Insert 8 at the end. So linked list // becomes 4.5.7.8 insertEnd(8); // Insert 6, after 5. So linked list // becomes 4.5.6.7.8 insertAfter(6, 5); Console.Write("Created circular doubly linked list is: "); display(); } } // This code is contributed by Rajput-Ji

Javascript

<script> // JavaScript program to illustrate inserting a Node in // a Circular Doubly Linked list in begging, end // and middle var start = null; // Structure of a Node class Node { constructor() { this.data = 0; this.next = null; this.prev = null; } } // Function to insert at the end function insertEnd(value) { var new_node; // If the list is empty, create a single node // circular and doubly list if (start == null) { new_node = new 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 */ var last = start.prev; // Create Node dynamically new_node = new 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, function insertBegin(value) { // Pointer points to last Node var last = start.prev; var new_node = new 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 function insertAfter(value1, value2) { var new_node = new Node(); new_node.data = value1; // Inserting the data // Find node having value2 and next node of it var temp = start; while (temp.data != value2) temp = temp.next; var 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; } function display() { var temp = start; document.write("<br>Traversal in forward direction <br>"); while (temp.next != start) { document.write(temp.data + " "); temp = temp.next; } document.write(temp.data); document.write("<br>Traversal in reverse direction <br>"); var last = start.prev; temp = last; while (temp.prev != last) { document.write(temp.data + " "); temp = temp.prev; } document.write(temp.data); } /* Driver code*/ /* Start with the empty list */ var start = null; // Insert 5. So linked list becomes 5.null insertEnd(5); // Insert 4 at the beginning. So linked // list becomes 4.5 insertBegin(4); // Insert 7 at the end. So linked list // becomes 4.5.7 insertEnd(7); // Insert 8 at the end. So linked list // becomes 4.5.7.8 insertEnd(8); // Insert 6, after 5. So linked list // becomes 4.5.6.7.8 insertAfter(6, 5); document.write("Created circular doubly linked list is: "); display(); </script>

Output:

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

Following are the advantages and disadvantages of a circular doubly linked list:

Advantages:

• List can be traversed from both directions i.e. from head to tail or from tail to head.
• Jumping from head to tail or from tail to head is done in constant time O(1).
• Circular Doubly Linked Lists are used for the implementation of advanced data structures like Fibonacci Heap.

Disadvantages

• It takes slightly extra memory in each node to accommodate the previous pointer.
• Lots of pointers involved while implementing or doing operations on a list. So, pointers should be handled carefully otherwise data of the list may get lost.

Applications of Circular doubly linked list

• Managing songs playlist in media player applications.
• Managing shopping cart in online shopping.

This article is contributed by Akash Gupta. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to . See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Article Tags :

Linked List

doubly linked list

Practice Tags :

Linked List

Circular Linked List | Set 1 (Introduction and Applications)

We have discussed singly and doubly linked lists in the following posts.

Introduction to Linked List & Insertion
Doubly Linked List Introduction and Insertion

Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list.

Advantages of Circular Linked Lists:
1) Any node can be a starting point. We can traverse the whole list by starting from any point. We just need to stop when the first visited node is visited again.

2) Useful for implementation of queue. Unlike this implementation, we don’t need to maintain two pointers for front and rear if we use circular linked list. We can maintain a pointer to the last inserted node and front can always be obtained as next of last.

3) Circular lists are useful in applications to repeatedly go around the list. For example, when multiple applications are running on a PC, it is common for the operating system to put the running applications on a list and then to cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application. It is convenient for the operating system to use a circular list so that when it reaches the end of the list it can cycle around to the front of the list.

4) Circular Doubly Linked Lists are used for implementation of advanced data structures like Fibonacci Heap.

Next Posts :
Circular Linked List | Set 2 (Traversal)
Circular Singly Linked List | Insertion

Please write comments if you find any bug in above code/algorithm, or find other ways to solve the same problem

Article Tags :

Linked List

circular linked list

Practice Tags :

Linked List

circular linked list

Definition of Circular Doubly Linked List in C

Circular doubly linked list in C or in any programming language is a very useful data structure. Circular double linked list is a type of linked list that consists of node having a pointer pointing to the previous node and the next node points to the previous node in the defined array. Circular doubly linked list is considered as one of the complex data structures in a way it works and plays with lots of pointers and addresses management within the implemented list. It doesn’t contain a null pointer in the defined list.

Syntax:

There is no particular syntax for the Circular doubly linked list but still needs to perform some of the initial steps of the creation of data structure and once created many operations can be performed on that linked list accordingly which is represented below :

#include <stdio.h>
Struct node_1
{
Struct node *prvs;
int some_data;
Struct node *nxt;
}

Follow scenarios:

– Insertion at the beginning
– Insertion at the end
– Removal from the beginning
– Removal from the end

Close the data structure and perform the further operation.

How Circular doubly linked list works in C?

Since Circular doubly linked list is a two-way list where the pointers somehow point to each other and no concept of null is present thus the pointer concept works internally.This is a type of linked list which is considered complex because of the previous node and the next node pointing to the previous node.Thus a fact can be concluded that the last node contains the address of the previous or the first node of the entire list.

The first node present in the list contains address of the last node for the pointer in its previous node.Since a circular double-linked list demands three structures, therefore, it is required to have more space and more expensive operations especially on the basics part of it.Searching in the case of a doubly linked list becomes quite easy and efficient as manipulation with the pointers is easy. But sometimes developers don’t prefer such data structure due to costly basic operation applied on the entire linked list.

Popular Course in this category

C Programming Training (3 Courses, 5 Project)3 Online Courses | 5 Hands-on Projects | 34+ Hours | Verifiable Certificate of Completion | Lifetime Access
4.5 (8,268 ratings)

Course Price

View Course

---

Related Courses

C++ Training (4 Courses, 5 Projects, 4 Quizzes)Java Training (40 Courses, 29 Projects, 4 Quizzes)

Another factor that plays a good role in memory management with respect to the circular double-linked list because it provides proper memory to each element present within the cell. The head as a variable contains the address of the first element of list. This first element is then the starting node of the list, the next node contains the second element, and so on till the last pointer which points back to the first node again proves the fact that the node is the last node that is pointing to the first since it does not contain any null element concept.There are various operations that are performed as part of the circular double linked list like insertion at the beginning, insertion at the end, deletion from the beginning, deletion at the end.

Examples

Let us discuss examples of Circular Doubly Linked List in C.

Example #1

This example represents an implementation of circular double-linked list with the operations of insertion at the beginning, insertion at the last, deletion at the beginning, and deletion at last which further displays the operation.

Code:

#include<stdio.h>
#include<stdlib.h>
struct nd_0
{
struct nd_0 *prv_1;
struct nd_0 *nxt_1;
int dta;
};
struct nd_0 *head;
void insrtion_begnng();
void insrtion_lst();
void delnt_begnng();
void deln_lst();
void show();
void srch();
void main ()
{
int choce =0;
while(choce != 8)
{
printf("\n*********Main_Menu_for_Display*********\n");
printf("\nChoose_any_one_option_from_list ...\n");
printf("\n----------------------------------------------------\n"); printf("\n1.Insertion_At_start\n2.Insertion_At_last\n3.Delet_at_Beginning\n4.Deletion_frm_end\n5.find\n6.display_val\n7.stop\n");
printf("\nSelect_the_desired_choice?\n");
scanf("\n%d",&choce);
switch(choce)
{
case 1:
insrtion_begnng();
break;
case 2:
insrtion_lst();
break;
case 3:
delnt_begnng();
break;
case 4:
deln_lst();
break;
case 5:
srch();
break;
case 6:
show();
break;
case 7:
exit(0);
break;
default:
printf("Select_entry_of_your_choicce..");
}
}
}
void insrtion_begnng()
{
struct nd_0 *ptr_0,*temp_1;
int item_0;
ptr_0 = (struct nd_0 *)malloc(sizeof(struct nd_0));
if(ptr_0 == NULL)
{
printf("\nList_Overflow");
}
else
{
printf("\nEnter desired_element");
scanf("%d",&item_0);
ptr_0->dta=item_0;
if(head==NULL)
{
head = ptr_0;
ptr_0 -> nxt_1 = head;
ptr_0 -> prv_1 = head;
}
else
{
temp_1 = head;
while(temp_1 -> nxt_1 != head)
{
temp_1 = temp_1 -> nxt_1;
}
temp_1 -> nxt_1 = ptr_0;
ptr_0 -> prv_1 = temp_1;
head -> prv_1 = ptr_0;
ptr_0 -> nxt_1 = head;
head = ptr_0;
}
printf("\nInserted_Node..\n");
}
}
void insrtion_lst()
{
struct nd_0 *ptr_0,*temp_1;
int itm_0;
ptr_0 = (struct nd_0 *) malloc(sizeof(struct nd_0));
if(ptr_0 == NULL)
{
printf("\niList_overflow");
}
else
{
printf("\nEnter desired_val");
scanf("%d",&itm_0);
ptr_0->dta=itm_0;
if(head == NULL)
{
head = ptr_0;
ptr_0 -> nxt_1 = head;
ptr_0 -> prv_1 = head;
}
else
{
temp_1 = head;
while(temp_1->nxt_1 !=head)
{
temp_1 = temp_1->nxt_1;
}
temp_1->nxt_1 = ptr_0;
ptr_0 ->prv_1=temp_1;
head -> prv_1 = ptr_0;
ptr_0 -> nxt_1 = head;
}
}
printf("\nnode_insertd_at_lst\n");
}
void delnt_begnng()
{
struct nd_0 *temp_1;
if(head == NULL)
{
printf("\n List_UNDERFLOW");
}
else if(head->nxt_1 == head)
{
head = NULL;
free(head);
printf("\ndelete_node_at_beginning\n");
}
else
{
temp_1 = head;
while(temp_1 -> nxt_1 != head)
{
temp_1 = temp_1 -> nxt_1;
}
temp_1 -> nxt_1 = head -> nxt_1;
head -> nxt_1 -> prv_1 = temp_1;
free(head);
head = temp_1 -> nxt_1;
}
}
void deln_lst()
{
struct nd_0 *ptr_1;
if(head == NULL)
{
printf("\n List_Underflow");
}
else if(head->nxt_1 == head)
{
head = NULL;
free(head);
printf("\nDeleted_Node\n");
}
else
{
ptr_1 = head;
if(ptr_1->nxt_1 != head)
{
ptr_1 = ptr_1 -> nxt_1;
}
ptr_1 -> prv_1 -> nxt_1 = head;
head -> prv_1 = ptr_1 -> prv_1;
free(ptr_1);
printf("\nDeleted_Node\n");
}
}
void show()
{
struct nd_0 *ptr_0;
ptr_0=head;
if(head == NULL)
{
printf("\nnot_to_print_anything;;");
}
else
{
printf("\n Need_to_print_some_values ... \n");
while(ptr_0 -> nxt_1 != head)
{
printf("%d\n", ptr_0 -> dta);
ptr_0 = ptr_0 -> nxt_1;
}
printf("%d\n", ptr_0 -> dta);
}
}
void srch()
{
struct nd_0 *ptr_0;
int itm,i_0=0,flag=1;
ptr_0 = head;
if(ptr_0 == NULL)
{
printf("\nBlank_all_elements.\n");
}
else
{
printf("\nSearch_for_items?\n");
scanf("%d",&itm);
if(head ->dta == itm)
{
printf("found_location_item %d",i_0+1);
flag=0;
}
else
{
while (ptr_0->nxt_1 != head)
{
if(ptr_0->dta == itm)
{
printf("element_at_location %d ",i_0+1);
flag=0;
break;
}
else
{
flag=1;
}
i_0++;
ptr_0 = ptr_0 -> nxt_1;
}
}
if(flag != 0)
{
printf("Element_Not_found\n");
}
}
}

Output:

Conclusion

Circular Doubly linked list is a type of linked list and is part of data structure which has lot of advantages when it comes to memory management. It supports complex pointer concepts with ease. Lot of manipulations and operations can be performed on this data structure containing elements in a row.

Recommended Articles

This is a guide to Circular Doubly Linked List in C. Here we discuss the definition, syntax, and parameters, How Circular doubly linked list works in C? examples with code implementation. You may also have a look at the following articles to learn more –

1. C# LinkedList
2. Linked List in C
3. LinkedList in Java
4. Reverse Linked List in Java

Which of the following is false about the circular linked list?

9. Which of the following is false about a circular linked list? Explanation: Time complexity of inserting a new node at the head of the list is O(n) because you have to traverse through the list to find the tail node.

Which of the following points is are not true about linked list data structure when it is compared with Array?

6. Which of the following points is/are not true about Linked List data structure when it is compared with an array? ... This will take more time than arrays as arrays provide random access to its elements.

Doubly Linked In C++

As in the singly linked list, the doubly linked list also has a head and a tail. The previous pointer of the head is set to NULL as this is the first node. The next pointer of the tail node is set to NULL as this is the last node.

A basic layout of the doubly linked list is shown in the below diagram.

In the above figure, we see that each node has two pointers, one pointing to the previous node and the other pointing to the next node. Only the first node (head) has its previous node set to null and the last node (tail) has its next pointer set to null.

As the doubly linked list contains two pointers i.e. previous and next, we can traverse it into the directions forward and backward. This is the main advantage of doubly linked list over the singly linked list.

Declaration

In C-style declaration, a node of the doubly linked list is represented as follows:

Apart from the above declaration, we can also represent a node in the doubly linked list as a class in C++. A doubly linked list is represented as a class when we use STL in C++. We can implement a doubly linked list using a class in Java as well.

Basic Operations

Following are some of the operations that we can perform on a doubly linked list.

Insertion

Insertion operation of the doubly linked list inserts a new node in the linked list. Depending on the position where the new node is to be inserted, we can have the following insert operations.

• Insertion at front – Inserts a new node as the first node.
• Insertion at the end – Inserts a new node at the end as the last node.
• Insertion before a node – Given a node, inserts a new node before this node.
• Insertion after a node – Given a node, inserts a new node after this node.

Deletion

Deletion operation deletes a node from a given position in the doubly linked list.

• Deletion of the first node – Deletes the first node in the list
• Deletion of the last node – Deletes the last node in the list.
• Deletion of a node given the data – Given the data, the operation matches the data with the node data in the linked list and deletes that node.

Traversal

Traversal is a technique of visiting each node in the linked list. In a doubly linked list, we have two types of traversals as we have two pointers with different directions in the doubly linked list.

• Forward traversal – Traversal is done using the next pointer which is in the forward direction.
• Backward traversal – Traversal is done using the previous pointer which is the backward direction.

Reverse

This operation reverses the nodes in the doubly linked list so that the first node becomes the last node while the last node becomes the first node.

Search

Search operation in the doubly linked list is used to search for a particular node in the linked list. For this purpose, we need to traverse the list until a matching data is found.

Insertion

Insert a node at the front

Insertion of a new node at the front of the list is shown above. As seen, the previous new node N is set to null. Head points to the new node. The next pointer of N now points to N1 and previous of N1 that was earlier pointing to Null now points to N.

Insert node at the end

Inserting node at the end of the doubly linked list is achieved by pointing the next pointer of new node N to null. The previous pointer of N is pointed to N5. The ‘Next’ pointer of N5 is pointed to N.

Insert node before/after given node

As shown in the above diagram, when we have to add a node before or after a particular node, we change the previous and next pointers of the before and after nodes so as to appropriately point to the new node. Also, the new node pointers are appropriately pointed to the existing nodes.

The following C++ program demonstrates all the above methods to insert nodes in the doubly linked list.

Output:

Doublylinkedlistisasfollows:

10<==>20<==>30<==>40<==>50<==>NULL

The above program constructs a doubly linked list by inserting the nodes using three insertion methods i.e. inserting the node at the front, inserting the node at the end and inserting the node after the given node.

Next, we demonstrate the same operation as a Java implementation.

Output:

Doublylinkedlistcreatedisasfollows:

10<==>20<==>30<==>40<==>50<==>null

Deletion

A node can be deleted from a doubly linked list from any position like from the front, end or any other given position or given data.

When deleting a node from the doubly linked list, we first reposition the pointer pointing to that particular node so that the previous and after nodes do not have any connection to the node to be deleted. We can then easily delete the node.

Consider the following doubly linked list with three nodes A, B, C. Let us consider that we need to delete the node B.

As shown in the above series of the diagram, we have demonstrated the deletion of node B from the given linked list. The sequence of operation remains the same even if the node is first or last. The only care that should be taken is that if in case the first node is deleted, the second node’s previous pointer will be set to null.

Similarly, when the last node is deleted, the next pointer of the previous node will be set to null. If in between nodes are deleted, then the sequence will be as above.

We leave the program to delete a node from a doubly linked list. Note that the implementation will be on the lines of the insertion implementation.

Reverse Doubly Linked List

Reversing a doubly linked list is an important operation. In this, we simply swap the previous and next pointers of all the nodes and also swap the head and tail pointers.

Given below is a doubly linked list:

Following C++ implementation shows the Reverse Doubly Linked List.

Output:

Originaldoublylinkedlist:

1<==>2<==>3<==>4<==>5

Reversedoublylinkedlist:

5<==>4<==>3<==>2<==>1

Here we swap the left and right pointers and move them towards each other till they meet or cross each other. Then the first and last nodes are swapped.

The next program is the Java implementation for reversing a doubly linked list. In this program also we make use of swapping of the left and right nodes as we did in our previous program.

Output:

Originaldoublylinkedlist:

1<==>2<==>3<==>4<==>5

Reverseddoublylinkedlist:

5<==>4<==>3<==>2<==>1

Advantages/Disadvantages Over Singly Linked List

Let us discuss some of the advantages and disadvantages of doubly linked list over the singly linked list.

Advantages:

• The doubly linked list can be traversed in forward as well as backward directions, unlike singly linked list which can be traversed in the forward direction only.
• Delete operation in a doubly-linked list is more efficient when compared to singly list when a given node is given. In a singly linked list, as we need a previous node to delete the given node, sometimes we need to traverse the list to find the previous node. This hits the performance.
• Insertion operation can be done easily in a doubly linked list when compared to the singly linked list.

Disadvantages:

• As the doubly linked list contains one more extra pointer i.e. previous, the memory space taken up by the doubly linked list is larger when compared to the singly linked list.
• Since two pointers are present i.e. previous and next, all the operations performed on the doubly linked list have to take care of these pointers and maintain them thereby resulting in a performance bottleneck.

Applications Of Doubly Linked List

A doubly linked list can be applied in various real-life scenarios and applications as discussed below.

• A Deck of cards in a game is a classic example of a doubly linked list. Given that each card in a deck has the previous card and next card arranged sequentially, this deck of cards can be easily represented using a doubly linked list.
• Browser history/cache – The browser cache has a collection of URLs and can be navigated using the forward and back buttons is another good example that can be represented as a doubly linked list.
• Most recently used (MRU) also can be represented as a doubly linked list.
• Other data structures like Stacks, hash table, the binary tree can also be constructed or programmed using a doubly linked list.

Conclusion

A doubly linked list is a variation of the singly linked list. It differs from the singly linked list in that where each node contains an extra pointer to the previous node along with the next pointer.

This presence of an extra pointer facilitates insert, delete operations on the doubly linked list but at the same time requires extra memory to store these extra pointers.

As discussed already, the doubly linked list has various uses in real-time scenarios like browser cache, MRUs, etc. We can also represent other data structures like trees, hash tables, etc. using a doubly-linked list.

In our next tutorial, we will learn more about the Circular Linked List.

=> Read Through The Popular C++ Training Series Here.