Circular Linked List in Data Structure

Takeaways

• Complexity of Circular linked list
  • Time complexity -
    • Insertion/Deletion : O(1)
    • Searching (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:

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:

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:

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-between 2 Nodes.

1. New Node will have its next pointing to the last.next.
2. Last.next will point to this new node.
3. 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:

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 between 2 Nodes.

1. Transverse till we reach the given node(let this node be X).
2. Point the next of NewNode to the Next of X.
3. Point next to X to this new Node.

This can be written programmatically as:

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:

1. 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.

2. 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 to null, removing last from the circular linked list.
   • Point last pointer to X, signifying that X is the new last Node now.

3. 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 as Y.
   • To remove Y, we need to change X.next to point to Y.next.

Let's see how the code for deleting looks like:

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.

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.

Related Topics

• Applications of Linked List