Introduction to Circular linked listA circular linked list is basically a linear linked list that may be singly or doubly. The only difference is that there is no any NULL value terminating the list. In fact in the list every node points to the next node and last node points to the first node, thus forming a circle. Since it forms a circle with no end to stop hence it is called as circular linked list.
In circular linked list there can be no starting or ending node, whole node can be traversed from any node. In order to traverse the circular linked list only once we need to traverse entire list until the starting node is not traversed again.
A circular linked list can be implemented using both singly linked list and doubly linked list. Here is the logical structure of a circular linked list.
Basic structure of Circular linked list
|Singly circular linked list|
|Doubly circular linked list|
Advantages of a Circular linked list
- Entire list can be traversed from any node.
- Circular lists are the required data structure when we want a list to be accessed in a circle or loop.
- Despite of being singly circular linked list we can easily traverse to its previous node, which is not possible in singly linked list.
Disadvantages of Circular linked list
- Circular list are complex as compared to singly linked lists.
- Reversing of circular list is a complex as compared to singly or doubly lists.
- If not traversed carefully, then we could end up in an infinite loop.
- Like singly and doubly lists circular linked lists also doesn’t supports direct accessing of elements.
Applications/Uses of Circular linked list in real life
- Circular lists are used in applications where the entire list is accessed one-by-one in a loop. Example: Operating systems may use it to switch between various running applications in a circular loop.
- It is also used by Operating system to share time for different users, generally uses Round-Robin time sharing mechanism.
- Multiplayer games uses circular list to swap between players in a loop.
Basic operations on Circular linked list
- Creation of list
- Traversal of list
- Insertion of node
- Deletion of node
- Deletion of first node
- Deletion of node from middle of the list
- Deletion of last node
- Deletion of entire list
- Counting total number of nodes
- Reversing of list