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:
- Allocate memory for a new node and set the data portion to a new value.
- Take the PTR variable, which is a pointer to the list’s first node.
- PTR should now point to the very last node in the list. Between PTR and the START node, add a new node.
- 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:
- Assign memory to the new node and set its data part to a new value.
- Take the PTR variable, which is a pointer to the list’s first node.
- 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:
- Take the PTR variable, which refers to the list’s first node.
- Move PTR to the end of the list, so it now points to the final node.
- 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:
- Take the PTR variable, which refers to the list’s first node.
- Move PTR to the end of the list, so it now points to the final node.
- 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