What is a Circular Linked List?
A circular linked list is a sequence of nodes arranged in such a way that each node can be retraced to itself. Here a “node” is a self-referential element with pointers to one or two nodes in its immediate vicinity.
Below is a depiction of a circular linked list with 3 nodes.
Basic Operations in Circular Linked lists
The basic operations on a circular linked list are:
- Deletion and
- Insertion is the process of placing a node at a specified position in the circular linked list.
- Deletion is the process of removing an existing node from the linked list. The node can be identified by the occurrence of its value or by its position.
- Traversal of a circular linked list is the process of displaying the entire linked list’s contents and retracing back to the source node.
Advantage of Circular linked list:
- We can go to any node from any node in the Circular linked list which was not possible in the singly linked list if we reached the last node.
- Easily we can go to head from the last node.
- In a circular list, any node can be starting point means we can traverse each node from any point.
- No requirement for a NULL assignment in the code. The circular list never points to a NULL pointer unless fully deallocated.
Disadvantages of Circular Linked List:
- Circular lists are complex as compared to singly linked lists.
- Reverse of circular list is a complex as compared to singly or doubly lists.
- If not handled carefully, then the code may go in an infinite loop.
- Harder to find the end of the list and loop control.
- Inserting at Start, we have to traverse the complete list to find the last node. (Implementation Perspective)
Space Complexity: O(1)