Everything about Circular Linked List

Last Updated on November 17, 2022 by Prepbytes

In this article, we will discuss the circular linked list in an effective and efficient manner. We will deep dive into a circular linked list with its traversal, operations, and advantages and disadvantages of circular linked list.
We will be also discussing various approaches to determine a circular linked list. So let’s start with the basics.

What is a circular linked list in data structures?

Circular Linked List is a variation of a linked list where all the nodes are connected, forming a circle. This means that there is no NULL at the end. The last node, instead of pointing to NULL, points to the first node.
A singly linked list or a doubly linked list can be converted to a circular linked list.

Representation of circular linked list in data structure

Let us look at how to represent a circular linked list, circular linked list are just similar to a linked list except for the last node. We can connect the last node to the first node to generate a circular linked list.

Node representation of circular linked list:

// Class Node, similar to the linked list
class Node{
    int value;
  // Points to the next node.
    Node next;
}

Example of circular linked list

// Initialize the Nodes.
Node one = new Node(30);
Node two = new Node(50);
Node three = new Node(90);

// Connect nodes
one.next = two;
two.next = three;
three.next = one;

Explanation of above circular linked list:

In the above example, one, two, and three are the nodes with the values of 30, 50, and 90 respectively that are connected in a circular manner.

• Node one stores the address of the next node i.e. node two with a value of 50.
• Node two stores the address of the next node i.e. node three with a value of 90.
• Node three stores the address of the first node i.e. node one with a value of 30.

This represents the circular linked list which forms a circle and there is no NULL in the circular linked list.

Operations on the circular linked list:

We have some operations on the circular linked list which is similar to a linked list:

Insertion

We can insert at 3 different positions of a circular linked list:

• Insertion at the beginning of the list: For insertion at the beginning of the circular linked list, we will store the address of the first node and points to the last node of the list.

• Insertion at the end of the list: For insertion at the end of the circular linked list, we will store the address of the head node to the new node and make the last node a new node.

• Insertion at the given position: For insertion at the given position, we will traverse the circular linked list, and points the next of the new node to the next node.

Deletion

We can delete from 3 different positions of a circular linked list:

• Delete the first node of the list: To delete the first node, transfer the head node to the next node and free the memory of the first node.

• Delete the last node of the list: To delete the last node of a circular list, find the second last node, change the pointer to the next node and free the memory of the last node.

• Delete the node from any position: to delete the node from a given position, you need to traverse the list and store the address of the previous node, and point the next of the current node to the next node.

You can follow the given links for a better understanding of the operations of a circular linked list which we have explained with the proper approach, dry run and implementation.

Types of circular linked list in data structures

Circular Linked lists are following two types:

Circular Singly Linked list:

In a circular singly linked list, the last node of the linked list is connected to the first node of the linked list i.e. the last node of the linked list contains the pointer to the first node of the linked list. We can traverse the circular singly linked list until we reach the same node where we started. There is no beginning and end to the list.

Circular doubly linked list:

In a circular doubly linked list, the properties of both i.e. doubly linked list and circular linked list are present. In other words, two consecutive nodes are linked or connected by the previous and next pointer.

Advantages of Circular Linked List in data structures

• We can traverse the entire list using any node as the starting point. It means that any node can be the starting point. We can just end the traversal when we reach the starting node again.
• Useful for the implementation of a queue. We don’t need to store two-pointers that point to the front and the rear. Instead, we can just maintain a pointer to the last inserted node. By doing this. We can always obtain the front as the next of last.
• Some problems are circular and a circular data structure like a circular linked list is ideal for them.
• Circular doubly linked lists are very useful when implementing the Fibonacci Heap and many other advanced data structures.

Disadvantages of Circular Linked List in data structures

• Finding the end of the list is more complex, as there is no NULL to mark the end.

Helpful Observations of circular linked lists in data structures

• One thing we can observe is that only the linked lists containing a cycle can be circular linked lists. So, if a linked list doesn’t have any cycle, we know that it is not a circular linked list.
• Another observation is that circular linked lists have a cycle, starting at the first node itself.
• So, finally, a linked list with a cycle will be called a circular linked list only if the point at which the cycle starts is the first node.

How to identify a linked list as a circular linked list

To check a linked list is circular or not, for that we need to make the following checks:

• If the linked list contains a cycle or not.
• If it has a cycle, then whether the node at which the cycle starts is the head node or not.

Let’s state this in another way:

• A linked list is called a circular linked list if the next pointer of the last node of the list points back to the first node. If this pointer points to NULL or any other previous nodes (other than the first node), then the linked list won’t be called circular.

Time Complexity of Circular linked list:

Insertion Operation: O(1) or O(N)
Deletion Operation: O(1)

Space Complexity of circular linked list:

Insertion Operation: O(1)
Deletion Operation: O(1)

Why circular linked list?

We can use a circular linked list as follow:

• The NULL pointer is not present in a circular linked list as a circular linked list always points to another node.
• The head node can be pointed to any node.
• Traverse in circular linked list is fast.

Through this article, we learned how to check if a linked list is a circular linked list or not. Problems like these are good for strengthening your concepts on Linked List. If you want to solve more questions on Linked List, which is curated by our expert mentors at PrepBytes.