Introduction To Circular Linked List With Examples
A circular linked list is a linked list where the last node links back to the first node, forming a closed loop. This structure ensures continuous traversal without a defined end, as no node points to NULL
.
Types of Circular Linked Lists with Syntax
There are two types of circular linked list, let’s explain both of these
1. Singly Circular Linked List
In a singly circular linked list, each node contains data and a pointer to the next node. The next
pointer of the last node points to the first node.
The singly circular linked list (with four nodes) in terms of addressing is given in the following diagram
As according to above diagram last node next address is 350 which is the address of first node.
2. Doubly Circular Linked List
In a doubly circular linked list, each node contains data, a next pointer, and a previous pointer. The next
pointer of the last node points to the first node, and the previous
pointer of the first node points to the last node.
The doubly circular linked list (with four nodes) in terms of addressing is given in the following diagram
Key Operations in a Circular Linked List
1. Insertion of a Node
- Singly Circular Linked List:
- Beginning: Update the
next
pointer of the new node to point to the head, and the last node’snext
pointer to the new node. - End: Update the
next
pointer of the last node to point to the new node, and the new node’snext
to the head. - Position: Traverse to the specified position, update the
next
pointer of the previous node to the new node, and the new node’snext
to the next node.
- Beginning: Update the
- Doubly Circular Linked List:
- Beginning: Update the
next
pointer of the new node to the head, theprev
pointer to the last node, and adjust the head and last node links. - End: Update the
next
pointer of the last node to the new node, the new node’snext
to the head, and adjust theprev
links. - Position: Traverse to the position, update the
next
andprev
pointers of adjacent nodes and the new node.
- Beginning: Update the
2. Deletion a Node
- Singly Circular Linked List:
- Beginning: Update the
next
pointer of the last node to the second node and set the head to the second node. - End: Traverse to the second-last node, update its
next
pointer to the head. - Position: Traverse to the node before the target, update its
next
pointer to skip the target node.
- Beginning: Update the
- Doubly Circular Linked List:
- Beginning: Update the
prev
pointer of the head’s next node to the last node, set thenext
pointer of the last node to the new head. - End: Update the
next
pointer of the second-last node to the head, and theprev
pointer of the head to the new last node. - Position: Update the
next
andprev
pointers of adjacent nodes to exclude the target node.
- Beginning: Update the
3. Traversal in List
-
- Singly Circular Linked List: Start from any node and follow the
next
pointers until returning to the starting node. - Doubly Circular Linked List: Start from any node and traverse forward using
next
pointers or backward usingprev
pointers until returning to the starting node.
- Singly Circular Linked List: Start from any node and follow the