# Circular Doubly Linked List in Data Structure A circular doubly linked list, also known as a circular two-way linked list, is a more advanced form of a linked list that includes a pointer to both the next and previous node in the sequence. The distinction between a doubly linked and a circular doubly linked list is the same as the distinction between a single linked and a circular linked list. The previous field of the first node and the next field of the last node in the circular doubly linked list do not contain NULL. Rather, the address of the first node in the list, i.e., START, is stored in the next field of the final node. Similarly, the address of the last node is stored in the previous field of the first field. A circular doubly linked list contains both the successor and predecessor pointers arranged in a circular pattern. The major benefit of utilizing a circular doubly linked list is that it doubles the efficiency of search operations. The disadvantage of this linked list is that it requires additional memory to hold previous and next node references.

## 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 at the 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 at the 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

## Deletion of a Node from a Doubly Linked Circular List

In this part, we’ll look at how to remove a node from a circular doubly linked list that already exists. We’ll look at two scenarios and see how each one is handled:

• Deletion of the First Node
• Deletion from Specified location
• Deletion of the Last Node

### Deletion of the First Node If the element is to be removed from the beginning, just make the head point to the current element’s next element and the last element to point to the new head. To delete the first node of the circular doubly list, follow the procedure below:

1. Take the PTR variable, which refers to the list’s first node.
1. Move PTR to the end of the list, so it now points to the final node.
1. Make START point to the list’s second node. The initial node’s space must be freed.

#### Algorithm

Step 1:

IF START = NULL

Write UNDERFLOW

Go to Step 8

[END OF IF]

Step 2: SET PTR = START

Step 3: Repeat Step 4 while PTR -> NEXT != START

Step 4:

SET PTR = PTR -> NEXT

[END OF LOOP]

Step 5: SET PTR -> NEXT = START -> NEXT

Step 6: SET START -> NEXT -> PREV = PTR

Step 7: FREE START

Step 8: SET START = PTR -> NEXT

### Deletion from Specified location It is a little more complex process, we need to make the previous element of the element at the current index to point to the next element of the current element. The algorithm below must be followed to remove the node after the specified location:

Step 1:

IF HEAD = NULL

Write UNDERFLOW

Go to Step 9

[END OF IF]

Step 2: SET TEMP = HEAD

Step 3: Repeat Step 4 while TEMP -> DATA != ITEM

Step 4:

SET TEMP = TEMP -> NEXT

[END OF LOOP]

Step 5: SET PTR = TEMP -> NEXT

Step 6: SET TEMP -> NEXT = PTR -> NEXT

Step 7: SET PTR -> NEXT -> PREV = TEMP

Step 8: FREE PTR

Step 9: EXIT

### Deletion of the Last Node If the node from the tail is to be deleted, the second last node must be made to refer to the head. To delete the last node of the circular doubly list, follow the procedure below:

1. Take the PTR variable, which refers to the list’s first node.
1. Move PTR to the end of the list, so it now points to the final node.
1. Release the PTR from its current location.

#### Algorithm

Step 1:

IF START = NULL

Write UNDERFLOW

Go to Step 8

[END OF IF]

Step 2: SET PTR = START

Step 3: Repeat Step 4 while PTR -> NEXT != START

Step 4:

SET PTR = PTR -> NEXT

[END OF LOOP]

Step 5: SET PTR -> PREV -> NEXT = START

Step 6: SET START -> PREV = PTR -> PREV

Step 7: FREE PTR

Step 8: EXIT