Doubly Circular Linked List Introduction and Insertion

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Doubly Linked List

  • A Doubly Linked List is a linked data structure that is represented as a set of nodes.
  • 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 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 data structure that has properties of both Circular Linked List and Doubly Linked List.
  • It is a list in which the last node of the list points to the start node, creating a loop.
  • As a doubly circular linked list is a combination of a doubly and a circular linked list, we can traverse in both directions, and also the last node of the list connects to the start node as next, and the start node has the last node in the prev pointer.

Structure of 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
#include
#include
 
struct Node
{
    int data;
    struct Node *next;
    struct Node *prev;
};

Problem Statement Understanding

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.


Now I think from the above figure, you got the idea, how insertions will happen in the list. So let's now see the algorithm to do these insertions.

Approach and Algorithm

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

    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.

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




Code Implementation:

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();
    }
}
#include
#include

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;
}
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.

So, in this blog, we have discussed Doubly Circular Linked List Introduction and Insertion. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Leave a Reply

Your email address will not be published. Required fields are marked *