Circular linked lists applications
In last few posts, we discussed about singly and doubly linked lists. This post is about circular linked list. Singly linked list is a list where each node points to its next node, there is no link from a node to previous, last node points to NULL node. Additional pointer needs to be kept in order to traverse linked list from start. Example of singly linked list given below:
What is circular linked list?
Circular linked list is a singly linked list with an additional thing. In circular linked list, next pointer of last node does not point to NULL. Next of last node of list again points to the head node of list. This in turn means there is no end node in circular linked list. Example of circular linked list is shown below:
How to find what is head node of circular linked list? There are two ways :
1.Keeping an external pointer as in case of singly linked list, which points to head node.
2. Keeping a dummy node, header. This node is separated from regular nodes of list by keeping a SENTINEL value in it. Other way is to have a flag to indicate that it is a head node.
Insertion in circular linked list
Node definition of circular list is same as singly linked list. There are three cases when where we can insert a node in circular linked list.
1. Insert at start of list.
We have an extra pointer which points to head node of the list. When node is added at front of list, that pointer is to be changed. Also, in circular linked list, last node points to head node, hence that link also should be changed.
1. Create a new node. 2. If this if first node, point it's next to itself head->next = head 3. Else, scan list and go to last node while(current != *headRef) 4. Change next node of new node to point to earlier head. newNode->next = *headRef 5. Change head to point to new node. *headRef = newNode 6. Change next pointer of last node to point to new node lastNode->next = newNode
Since head node is changing, function call will be headRef and not head pointer only. Below is code for above algorithm to add a node at start of circular linked list
2. Insert at the middle of circular linked list.
This insertion is same as singly linked list, as there is no change in head or tail of circular list. Just scan to the required position, add new node.
next = prev->next; prev->next = newNode; newNode->next = next;
3. Insert at the end of circular linked list
This case is very similar to above case, only difference will be that next pointer of last node will be head node. No implementation change.
Delete node from circular linked list
To remove a node, care should be taken when removing head or last nodes. When last node is removed, previous to last node should now start pointing to head node. When head node is removed, last node should now be pointing to new head node. Below is code to remove node.
Complexity of insert and removal of nodes in circular linked list is O(n) as we always need to traverse linked list at least once.
Applications of circular linked lists
- Implementation of waiting and context switch queues in operating system. When there are multiple processes running on operating system and there is mechanism to provide limited time slots for each process, waiting process can form a circular linked list. Task at head of list is given CPU time, once time allocated finishes, task is taken out and added to list again at the end and it continues.
- Circular linked list is useful in implementation of queues using lists. Remember in post: Stack and Queue implementation using linked list, we had two pointers, one to point to head and other to point to end of list, because in queue, addition happens at end and removal at head. With circular list, that can be done using only one pointer.
Please share your views and suggestions. We would love to hear what you have to say. Sharing is caring. If you are interested in contributing to website or you have interview experience to share, please contact us.