Circular linked list
is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or a doubly circular linked list.
Before reading this article, you should have some understanding of the following Data Structures topics:
Scope
- This article tells about the working of the
Circular linked list
in Data Structures. - Need of
Circular linked list
. - Different operations of
Circular linked list
. - Implementation of
Circular linked list
. - Application of
Circular linked list
.
Takeaways
- Complexity of Circular linked list
Time complexity
–- Insertion/Deletion : O(1)
- Searching :O(n)
- Access : O(n)
Introduction Circular Linked List
As the name suggests, Circular Linked List is a variation of Linked List Data Structures. I would suggest going through the Linked List concepts before jumping ahead with Circular Linked List. Linked List
In brief, say we have 3
elements,
If we go with Arrays, those will be represented as {1, 2, 3}
Whereas in Linked lists
, each element has a pointer to the next element, so the linked list would be represented as:
It comes with its own advantages and disadvantages over Arrays, and is covered in detail in the Linked List article.
Let’s try to explore what more can be done to enhance the Linked List.
In a Linked List
, it is not very straightforward to circle around the list.
By circle, we mean that once we have reached the last Node in the list, we can get the starting Node from the last Node.
There are many applications in real life(as we will see later) that need to circle the list of elements multiple times. And as we have seen, in Linked List, the last node points to Null
, and therefore to get the starting Node we need to rely on the Head pointer, which points to the starting Node.
Circular linked lists
avoids this overhead of traversing till the Node points to null, and then using a head pointer to circle back from start, but it’s the intrinsic property of Circular Linked lists that provides this property to circle the Linked List, by default.
We will look into Circular Linked Lists in detail below.
What is a Circular Linked List in Data Structures?
As we have seen, the circular linked lists
is a variation over linked lists. In a linked list, the last node points to null, and we utilize this link to point the last Node to the First Node, in circular linked lists. This makes the elements to be connected in a circular manner, and such a list is called a Circular Linked List.
We can traverse a circular linked list
until we reach the same node where we started. The circular linked list has no beginning and no ending and there is no null value present in the next part of any of the nodes. These are some points that differentiate it from the linked list.
We will see in later sections that we don’t even need any head Node in circular linked lists, so keep that in mind, the below image only shows how the elements are connected in Linked List vs circular linked list:
Circular Singly Linked List
The Circular List
we have been discussing so far uses single pointers(i.e. Next pointer) to link 2
Nodes, hence it is usually referred to as Circular Singly Linked List.
With this Data structure, we can transverse only in one direction in a circular manner, as shown below:
Circular Doubly Linked List
As we have seen in the case with Linked Lists
, there are several applications where we need to traverse the list in both directions. To support the additional backward transversal, we have the Doubly Linked List.
The same property can also be used in Circular Singly Linked Lists, where each node has 2
pointers, Next and Back to points to the Next and the previous Node respectively, plus the next of last points to the first Node(and vice versa), forming a Circle. Such a data structure is known as a circular doubly linked list
.
The following image shows what the Circular doubly Linked List looks like:
Representation of Circular Linked List in Data Structures
Please note that to ease the understanding, we will be using the singly circular linked list to represent the working of the circular linked list in Data Structure.
A circular linked list is represented similarly to the Linked List, with one additional care to connect the last node to the first Node.
So a Node in the Circular Linked List
can be represented as:
// Node structure is similar to what we have in Linked Lists.
class Node{
int value;
Node next; // Points to the next node.
}
Now we will create a simple circular linked list with three Nodes to understand how this works.
Say we have the Circular Linked list as:
This can be represented as:
// Initialize the Nodes.
Node one = new Node(1);
Node two = new Node(2);
Node three = new Node(3);
// Connect nodes
one.next = two;
two.next = three;
three.next = one;
In the above code, one, two, and three are the nodes with data items 1, 2, and 3
respectively.
We can see the 3 Nodes are connected in a Circular manner:
For Node One
Next stores the address of Node two.
For Node Two
Next stores the address of Node three
For Node Three
Next points to node one.
Operations on Circular Linked List in Data Structure
We have seen how the Circular Linked List can be represented. To perform other operations on it, we need a pointer to any of the Nodes in the Circular Linked List, from where we can traverse the entire List.
Usually, in linked lists, we maintain the pointer to the first Node, known as the head pointer. Let’s see if the same Node would work the best in the Circular Linked list
.
1. Insertion
We should be able to insert any new Node in the given Circular Linked List.
Let’s see if the head pointer would work with insertions.
If we want to insert a new Node at the beginning of the Circular Linked List, and if we have the Head Pointer maintained, as shown:
Let’s say we want to insert a new Node (say 4
) at the beginning. How can we adjust the Nodes we already have in the list to accommodate this new Node?
Since we maintain the head pointer(to 1
), the next of a new Node (i.e. 4
) can point to Head, and this takes care of including 4 in the list.
But we are missing one thing here. The circular property is not yet adjusted.
Last Node(i.e. 3
) is still pointing to 1
, whereas, with the addition of 4, 3’s
next should point to 4
instead.
How can this be done?
We can transverse the list, reach the last Node in the circular linked list(i.e. To 3
), and make its next point to the new Node(i.e. 4
).
But as you can guess, it is a slow process. Consider the scenario where we have 1000
nodes in the circular linked list, and just to add one Node we are traversing these 1000
Nodes to reach the last Node.
Similarly, when we need to insert a new Node at the end(i.e. After 3
), again we need to traverse the list again from head to reach the last node.
So it seems the head pointer is not the best pointer for circular linked list in Data Structure.
But what if we maintain the pointer to the Last Node instead?
If instead of a start pointer, we take a pointer to the last node, then in both cases there won’t be any need to traverse the whole list.
Since we can reach head by just one jump from last using last.next, the head pointer is not much required. So in Circular Linked lists, the pointer to the last Node can be maintained, instead of the head Node(which is done for linked lists).
So the circular linked list in Data Structure can be visualized as:
- Insertion at the Beginning:
Now as we maintain the pointer to Last Node, we can get the first Node directly using Last.next.
We can insert the Node at the beginning as:
- Get the current First Node(by
last.next
), and the New Node can point to this node as its next. This takes care of adjusting pointers of the New Node. - Point the Last Node to the new Node, thus honoring the circular property.
This can be written programmatically as:
Node last; // Pointer to the last Node of the Circular Linked List.
void insertNodeAtBeginning(int value) {
// Creating a new Node with the value.
Node newNode = new Node(value);
// Adjusting the links
Node oldFirstNode = last.next;
newNode.next = oldFirstNode;
last.next = newNode;
}
As we can see, we need not loop over the list, but we just need to change the pointers of the last Node and the new Node. So it takes constant time operation if we have the pointer to the last Node.
And as we have not used any extra space, the space complexity is constant i.e. O(1)
Space complexity to insert a new Node at the beginning of the circular linked list.
- Insertion at the end:
Let’s see how the New Node can be inserted in-between2
Nodes.
- New Node will have its next pointing to the last.next.
- Last.next will point to this new node.
- Now since we have a new Node at the end, change the last Node pointer to point to this New node.
This can be written programmatically as:
void addAtEnd(int value) {
Node newNode = new Node(value);
// Adjusting the links.
newNode.next = last.next;
last.next = newNode;
last = newNode;
}
As we can see, to insert a new Node at the end of the circular linked list
, we only need to adjust the pointers of the last node, hence it takes constant time to insert a new node at the end of the circular linked list.
As we have not used any extra space, the space complexity is constant i.e. O(1)
space complexity to insert a new Node at the end of the circular linked list.
- Insertion After Another Node:
Let’s see how the New Node can be inserted in between2
Nodes.
- Transverse till we reach the given node(let this node be
X
). - Point the next of NewNode to the Next of
X
. - Point next to
X
to this new Node.
This can be written programmatically as:
void addAfter(int newValue, Node nodeBefore) {
if (nodeBefore == null) {
return;
}
Node newNode;
Node transversalNode = last.next; // Transverse the List from last Node onwards.
do {
if (transversalNode.value == nodeBefore.value) { // We found the node.
newNode = new Node(newValue);
// Adjusting the links
newNode.next = transversalNode.next;
transversalNode.next = newNode;
if (transversalNode == last) {
// If the nodeBefore was LastNode itself, meaning we are inserting this node at the end,
// adjust the last pointer to point to this node now.
last = newNode;
}
}
transversalNode = transversalNode.next;
// Keep transversing until we reach the Node after which the new node has to be inserted.
} while (transversalNode != last.next);
}
As we can see, we need to iterate over the list to reach the Node after which a new Node has to be inserted, which means it takes as much time as many elements are there in the List.
Thus if there are 1000
elements, and if the insert has to be done after the 999th
Node, we would need to iterate over these 999 nodes, hence this insertion has the Time complexity of O(N)
, N being the number of elements in the circular linked list
.
And as we have not used any extra space, the space complexity is constant i.e. O(1)
space complexity to insert a new Node after a given node of the circular linked list.
2. Deletion
To delete a given node from a Circular Linked List
, we can have 3 different scenarios:
- If it’s the only node in the Circular Linked List.
- In this case, the last which was pointing to the only Node can now point to
null
, making the circular linked list empty.
- In this case, the last which was pointing to the only Node can now point to
- If the Node to be deleted is the last node in the
Circular Linked List
:- Iterate the circular linked list to find the Node before the Node to delete. Let it be referred to as
X
. - Point the
X.next
tonull
, removing last from the circular linked list. - Point last pointer to
X
, signifying thatX
is the new last Node now.
- Iterate the circular linked list to find the Node before the Node to delete. Let it be referred to as
- Deleting any other node in the
Circular Linked List
:- Iterate the Circular Linked List to find the Node before the Node to delete. Let it be referred to as
X
.
Let the Node to be deleted be referred to asY
. - To remove
Y
, we need to changeX.next
to point toY.next
.
- Iterate the Circular Linked List to find the Node before the Node to delete. Let it be referred to as
Let’s see how the code for deleting looks like:
Node deleteNode(int valueOfNodeToDelete) {
// if Circular Linked List is empty
if (last == null)
return null;
// If the Circular Linked List contains only a single node
// -- Scenario 1.
if (last.value == valueOfNodeToDelete && last.next == last) {
// If Circular Linked List has only one Node, last.next will point to last,
// as last is itself the starting node in this case.
last = null;
return last;
}
Node temp = last;
// If last is to be deleted -- Scenario 2.
if (last.value == valueOfNodeToDelete) {
// find the node before the last node
while (temp.next != last) {
temp = temp.next;
}
// point temp node to the next of last i.e. first node
temp.next = last.next;
last = temp.next;
}
// travel to the node to be deleted
while (temp.next != last && temp.next.value != valueOfNodeToDelete) {
temp = temp.next;
}
// If node to be deleted was found -- Scenario 3.
if (temp.next.value == valueOfNodeToDelete) {
Node toDelete = temp.next;
temp.next = toDelete.next;
}
return last;
}
As we can observe, we might need to transverse the circular linked list
to delete the node. This is required to find the Previous node, so that its next can be adjusted to remove the culprit node from the circular linked list chain.
So deletion takes O(N)
time complexity, and as it takes no extra space to execute, its space complexity is O(1)
i.e. content space complexity.
3.Display
To display the circular linked list
, we need to transverse from the last Pointer until we reach back to it. As we transverse over the Nodes, we can print their values.
Node last; // pointer to last Node.
void displayList() {
Node temp = last;
if (last != null) {
// Keep printing nodes till we reach the last node again.
do {
System.out.print(temp.value + " ");
temp = temp.next;
} while (temp != last);
}
}
Applications of Circular Linked List
As we have seen, circular linked lists
come in handy when we need to have the circular order maintained between the different Nodes. Unlike linked lists, no Node in circular linked lists points to null.
Circular linked lists find their application in many real live systems where we can easily circle back to the starting Node from the last one. Some of those can be:
- In multiplayer games, each player is represented as a Node in the circular linked list. This way, each player is given a chance to play, as we can easily shuffle back to the first player from the last player quickly, utilizing the circular property.
- Similarly, operation systems utilize this concept for running multiple applications, where all these applications are placed in the circular linked list, and without worrying about reaching to the end of the running applications, it can easily circle back the applications at the start.
Unlock the Power of Efficient Coding! Join Our DSA Certification Course Today and Transform Your Problem-Solving Abilities.
Summary
As we have seen, the circular linked list is a Variation of the linked list, where we maintain the circular order of all the nodes present in it.
There are 2
types of Circular Linked Lists:
Circular Singly Linked List
: where we can only transverse in one direction while maintaining the circular property.Circular Doubly Linked Lists
: where we can transverse in both directions, while also maintaining the circular property.
We also observe how easy it is to insert and delete the Nodes from the circular linked list
, and the algorithm is very much similar to what was done for linked lists. To ease out, we take “last” as the pointer in Circular Linked List, as opposed to the “head” pointer taken in the linked list.
Finally, we saw the applications of circular linked lists, where we leverage the fact that we need not have to worry about reaching the end of the list but can continue processing all the items as they would be lying in a circular manner.