If you are not familiar with the LinkedList, I would highly recommend having a look at my blog:
Introduction to Linked List
In this tutorial, we will learn circular linked list in-depth by dividing topics in the following manner:
- Definition of circular linked list.
- Types of Circular linked list
Basic Operations on circular linked list
a] Searching/Traversal
b] Insertion
c] DeletionSingly linked list as a circular linked list.
Doubly linked list as a circular linked list.
Applications of circular linked list
Implementation of circular linked list.
Definition of circular linked list
In a circular linked list, elements are stored in random memory locations.
Similar to a singly linked list, each node of a circular linked list [I meant singly circular linked list] contains two fields:
- data stored at that particular address.
- Pointer which contains the address of the next node.
Unlike, singly linked list in which the last node of the contains a pointer to null to represent the termination of a linked list, in circular linked list, last node of linked list will point to the first node of the linked list.
Types of Circular Linked List:
There are two types of Circular linked list. i.e. we can make a circular linked list by modifying the Singly linked list as well as Doubly linked list.
1. Singly circular linked list
The above diagram is an example of a singly linked list in which the last node[Tail] points to NULL to represent the termination of the linked list.
To make it a singly circular linked list, you just need to modify the link of the last node.
Instead of pointing it to NULL, We are going to link it with the first[head] node.
Now, one question which might come into your mind is, how do we get to know termination condition, right?
Because, if we dont apply termination condition our program will run into an infinite loop. Confused?
Well, one thing you might do is, keep a track of head node and whenever we encounter it again, we say that we have traversed our whole linked list and Now it is time to terminate.
You could have taken a temp=head->next and start traversing linked list and check for whether our temp is head or not.
if [temp==head] ===> We have traversed whole linked list.
Well, it was just a brief explanation, we will see it via code in detail, later in this tutorial.
2. Doubly circular linked list
The above diagram is an example of doubly linked list in which the prev of head points to NULL and last node[Tail] points to NULL to represent the termination of linked list.
To make it a Doubly Circular Linked List, you just need to modify the link of the last node.
Instead of pointing next of last node [lastNode->next] to NULL, We are going to link it with first[head] node.
Moreover, the prev of first node [head->prev] will point to the last node.
In this case, keep a track of head node and whenever we encounter it again, we say that we have traversed whole linked list and now it is time to terminate.
You could have taken a temp=head->next and start traversing linked list and check for whether our temp is head or not.
if temp==head -----> We have traversed whole linked list.
Operations on Circular linked list
A. Traversal
Traversal in Circular linked list is similiar to singly or doubly linked list, we just need to take care of termination condition. In this case termination condition would be, If we reach again to our head node.
To perform this task do the following:
Take a temp node and store head ->next into it, now run a loop untill temp!=head and search for given element.
If we reach head ===> [temp==head]: terminate loop.
D. Advantages of Circular linked list
In a circular linked list, there is no requirement for a NULL assignment in the code. The good thing about a circular linked list is that It never points to a NULL pointer unless fully deallocated.
Circular linked lists are always good and advantageous for the end operations since the beginning and the end of circular linked list coincide with each other.
Many algorithms such as the Round Robin scheduling which uses queue can efficiently and easily eliminate processes that are queued in a circular way or fashion without encountering any dangling pointers or NULL-referential
pointers.The biggest advantage with a circular linked list is that It also performs all regular functions of a singly/doubly linked list along with additional features.
E. Disadvantage of circular linked list
Insertion at all positions [first node, last node, and In-between] takes O[n] time while in singly linked list insertion at first node takes O[1] time.
Deletion at all positions [first Node, Last Node, and In-between] takes O[n] time while in singly linked list deletion at first node takes O[1] time.
If we dont apply the termination condition properly, our code might lead to infinite loop.
F. Applications of Circular linked list
If I talk about the real-life application of a circular linked list, It would be none other than our personal computers, which are capable of running multiple applications at a time. Computers process all applications in this manner that all running applications are kept in a queue which is implemented using a circular linked list and the operating system gives a fixed time[could be an example of Round Robin CPU Scheduling Process] slot know as time quantum to all for running processes.
The operating system keeps on iterating over the
circular linked list and keeps executing processes and removing them from waiting for queue until all the applications are executed/completed successfully.We can also take an example multiplayer games in which all the players are kept in a queue which is implemented via a circular linked list and the pointer keeps on moving forward as the chance of a particular player ends.
We can also take an example of the circular linked list which can also be used to create a circular queue.
The problem with a given queue is that we need to keep two pointers one for FRONT and another for REAR in memory all the time to implement a queue.
But with the help of a Circular linked list we can do this task easily and efficiently because, in a circular linked list, only one pointer is required.Circular linked list is also used in token rings scheduling in computer networks.
Circular linked list is used to display units like shop boards that require continuous traversal of data.