Circular doubly linked list insertion at beginning algorithm

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.

Node Structure and Graphical Representation

Node Structure

Every node in a circular Doubly Linked List has the following structure:

The terms “Prev” and “Next” refer to the node’s previous and next components, respectively. The actual element that is stored in the node is referred to as the ‘Data.’

Graphical Representation

Circular Doubly Linked List is graphically represented as follows:

Adding a New Node in Circular Doubly Linked List

We’ll explore how to add a new node to an already existing circular doubly linked list in this section. We’ll look at two different scenarios and see how each one is handled:

• Insertion at the Beginning

• Insertion at Particular Location

• Insertion atthe End

Insertion at the Beginning

If the current element is to be inserted in front, just make all existing elements the current element’s next element, and the last element to refer to the new node. To insert the new node at the beginning of the circular doubly list, follow the procedure below:

1. Allocate memory for a new node and set the data portion to a new value.

1. Take the PTR variable, which is a pointer to the list’s first node.

1. PTR should now point to the very last node in the list. Between PTR and the START node, add a new node.

1. The new node will now be pointed to by START.

Algorithm

Step 1:

IF AVAIL = NULL

Write OVERFLOW

Go to Step 13

[END OF IF]

Step 2: SET NEW_NODE = AVAIL

Step 3: SET AVAIL = AVAIL -> NEXT

Step 4: SET NEW_NODE -> DATA = VAL

Step 5: SET PTR = START

Step 6: Repeat Step 7 while PTR -> NEXT!= START

Step 7:

SET PTR = PTR -> NEXT

[END OF LOOP]

Step 8: SET PTR -> NEXT = NEW_NODE

Step 9: SET NEW_NODE -> PREV = PTR

Step 10: SET NEW_NODE -> NEXT = START

Step 11: SET START -> PREV = NEW_NODE

Step 12: SET START = NEW_NODE

Step 13: EXIT

Insertion at Particular Location

It’s a little more complicated since we need to make the element at the current index point to the current element and the current element point to the next element, as well as designate it as the predecessor of the next element.

Algorithm

The goal is to count the number of elements in the list as a whole. Check to see if the supplied position is legitimate, if it falls inside the count. If the location is correct:

Step 1: Create a newNode in the memory.

Step 2: Traverse in the list using a temporary pointer (temp) till node just before the given position at which new node is needed to be inserted.

Step 3: Insert the new node by performing below operations:

Assign newNode->next = temp->next

Assign newNode->prev as temp->next

Assign temp->next as newNode

Assgin (temp->next)->prev as newNode->next

Insertion atthe End

Make the final element point to the new element, the new element point to the first element, and the first element point to the last element if the node is to be inserted at the end. To insert the new node at the beginning of circular doubly list, follow the procedure below:

1. Assign memory to the new node and set its data part to a new value.

1. Take the PTR variable, which is a pointer to the list’s first node.

1. PTR should now point to the list’s last node, allowing the new node to be added after it.

Algorithm

Step 1:

IF AVAIL = NULL

Write OVERFLOW

Go to Step 12

[END OF IF]

Step 2: SET NEW_NODE = AVAIL

Step 3: SET AVAIL = AVAIL -> NEXT

Step 4: SET NEW_NODE -> DATA = VAL

Step 5: SET NEW_NODE > NEXT = START

Step 6: SET PTR = START

Step 7: Repeat Step 8 while PTR -> NEXT != START

Step 8:

SET PTR = PTR -> NEXT

[END OF LOOP]

Step 9: SET PTR -> NEXT = NEW_NODE

Step 10: SET NEW_NODE -> PREV = PTR

Step 11: SET START -> PREV = NEW_NODE

Step 12: EXIT

1) Introduction to Circular Doubly Linked List

Circular Doubly Linked List is a linear data structure which consists of nodes. Each node is divided into three parts containing data part,pointer to previous node and pointer to next node.

Unlike Linked List or Doubly Linked List, Circular Doubly Linked List doesn't contain NULL values in any of the nodes rather the head's previous pointer points to last node and last node's next pointer points to head. This is an advantage as NULL is considered as a special case.

Node structure:

Various operations can be performed on Circular Doubly Linked List as discussed below.

Insertion at the beginning

In this operation a new node is inserted at the beginning of CDLL.

The basic idea is to update the head node of Circular Doubly Linked List which is the starting point and the rest of the process remain the same as in inserting in any other position.

Note: As any node in Circular Doubly Linked List can act as the head node, it is important to maintain it but it does not create issues if access to head node is lost provided we have access to any node of the Circular Doubly Linked List.

Let's understand through an illustration.

Given CDLL

Create a new node with value 2

Take a variable ptr and let it point to head initially

Traverse through the list to make ptr point to the last node

Change the pointers as follows

ptr->next=newnode
-Last node's next pointer will point to new node as it'll be new head.
newnode->prev=ptr
-New node's prev pointer will point to ptr as head's previous must be last node.
newnode->next=head
-New node's next pointer will point to current head as current head'll become the second node.
head->prev=newnode
-Current head's prev pointer will point to new node as it'll be the new head now.

head=newnode
-Finally head pointer will point to the new node.

-The modified list

ALGORITHM

STEP-1: Create newnode
STEP-2: SET ptr=head
STEP-3: Repeat STEP-4 while ptr->next!=head
STEP-4:  SET ptr=ptr->next
    [END OF LOOP]
STEP-5: SET ptr->next=newnode
STEP-6: SET newnode->prev=ptr
STEP-7: SET newnode->next=head
STEP-8: SET head->prev=newnode
STEP-9: SET head=newnode
STEP-10: EXIT

CODE SNIPPET