Circular Linked List

Types of Circular Linked List

There are mainly two types of circular linked lists: 

1. Circular singly linked lists and 
2. Circular doubly linked lists.

1. Circular Singly Linked List

A circular singly linked list is a unidirectional linked list in which we traverse only in one direction. It consists of the last node that points towards the head node, thus making a circular ring. Therefore, they are mainly used when we need to process the data in a continuous loop.

It is implemented using the singly linked list where each node points towards the next node, and the last node is then connected back to the head node, forming a ring. Unlike standard linked lists, they have no end or beginning.

2. Circular Doubly Linked List

The Circular doubly Linked list consists of nodes that contain pointers pointing towards the previous nodes, along with the next node. Therefore two consecutive nodes are connected by the next and previous pointer, and the last node points towards the head node along with the head node, pointing towards the last node, unlike in a singly circular linked list where only the last node is pointing towards the head node.

A circular doubly linked list is used in implementing  HashSet. Some common applications of circular doubly linked lists include music and video playlists, browser history, dequeue data structure, cache management, and undo/redo functionality. 

Creating Circular Linked List in C

A linked list is created using structures in C, as shown below.

#include <stdio.h>
#include <stdlib.h>
#define null 0

// Structure is used to create the circular linked list
typedef struct CircularLinkedList
{
	int data;
	struct CircularLinkedList *next;
	
}node;

// Function to add the items to the linked list
node *getnode()
{
	node *new;
	int item;
	printf("Enter the data ");
	scanf("%d",&item);
	new=(node*)malloc(sizeof(node));
	new->data = item;
	new->next = null;
	return new;
}

int main()
{
	node *head, *q, *x;
	int i,n,ch;
	printf("Enter the number of nodes ");
	scanf("%d",&n);
	
	for(i=0;i<n;i++)
	{
        	if(i==0)
        	{
            	  head = getnode();
            	  head->next=head;
            	  q=head;
        	}
        	
        	else
        	{
            	  x=getnode();
            	  q->next=x;
            	
            	  //Last element is linked to the first one
            	  x->next=head; 
            	  q=x;
        	}
	}
	return 0;
}

This code does not have any output since we only created the linked list and didn’t print anything. 

Representation of Circular Linked List

Here is an example of a Circular Linked List to show the representation of it:

• C
• C++
• Java
• Python

C

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

void insert(struct Node** head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head;
    newNode->data = data;
    newNode->next = *head;

    if (*head != NULL) {
        while (last->next != *head)
            last = last->next;
        last->next = newNode;
    } else {
        newNode->next = newNode;
    }

    *head = newNode;
}

void display(struct Node* head) {
    struct Node* temp = head;
    if (head != NULL) {
        do {
            printf("%d ", temp->data);
            temp = temp->next;
        } while (temp != head);
    }
}

int main() {
    struct Node* head = NULL;
    insert(&head, 10);
    insert(&head, 20);
    insert(&head, 30);
    display(head);
    return 0;
}

You can also try this code with Online C Compiler

Run Code

C++

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int d) : data(d), next(nullptr) {}
};

class CircularLinkedList {
public:
    Node* head;
    CircularLinkedList() : head(nullptr) {}

    void insert(int data) {
        Node* newNode = new Node(data);
        if (!head) {
            head = newNode;
            newNode->next = head;
        } else {
            Node* temp = head;
            while (temp->next != head)
                temp = temp->next;
            temp->next = newNode;
            newNode->next = head;
        }
    }

    void display() {
        if (head) {
            Node* temp = head;
            do {
                cout << temp->data << " ";
                temp = temp->next;
            } while (temp != head);
        }
    }
};

int main() {
    CircularLinkedList list;
    list.insert(10);
    list.insert(20);
    list.insert(30);
    list.display();
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

class Node {
    int data;
    Node next;
    Node(int d) {
        data = d;
        next = null;
    }
}

class CircularLinkedList {
    Node head;

    public void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            newNode.next = head;
        } else {
            Node temp = head;
            while (temp.next != head)
                temp = temp.next;
            temp.next = newNode;
            newNode.next = head;
        }
    }

    public void display() {
        if (head != null) {
            Node temp = head;
            do {
                System.out.print(temp.data + " ");
                temp = temp.next;
            } while (temp != head);
        }
    }

    public static void main(String[] args) {
        CircularLinkedList list = new CircularLinkedList();
        list.insert(10);
        list.insert(20);
        list.insert(30);
        list.display();
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def insert(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head
        else:
            temp = self.head
            while temp.next != self.head:
                temp = temp.next
            temp.next = new_node
            new_node.next = self.head

    def display(self):
        if self.head:
            temp = self.head
            while True:
                print(temp.data, end=" ")
                temp = temp.next
                if temp == self.head:
                    break


cll = CircularLinkedList()
cll.insert(10)
cll.insert(20)
cll.insert(30)
cll.display()

You can also try this code with Online Python Compiler

Run Code

Traversing Through a Circular Linked List

Now that we know how to create a circular linked list, we must know how to traverse it. 

Here suppose, the first element entered by the user is considered to be the head. So, the method to traverse the circular linked list will be:

// Method to traverse through a circular linked list
void *traverse(node*h)
{
    // Checking if the linked list is empty
    if(h==null)   
     {
          printf(“Empty Circular Linked List”);
     }
     else
     {
          node *q;
          q=h;
          
          // Traversing through the linked list
          while(q->next!=h)  
          { 
              q=q->next;
          }
    }
}

We saw two code snippets but none of them is printing anything. So how will we be sure whether what we wrote is working or not?

By printing the linked list, of course! 

We just learned how to traverse through a circular linked list. To print the linked list, all we need to do is add a print statement to that. 

I’m pretty sure you’ve already figured out how to do it, but in case you haven’t, it is as follows:

// Method to print the elements in a circular linked list
void *print(node*h)
{   
    // Checking if the linked list is empty
    if(h==null)   
     {
          printf(“Empty Circular Linked List”);
     }
     else
     {
          node *q;
          q=h;
          
          // Traversing through the linked list
          while(q->next!=h)   
          { 
              // Printing the elements
              printf(“%d -> ”,q->data);   
              q=q->next;
          }
          
          // Printing the first element again to show the circular nature
          printf(“%d”,q->data);  
    }
}

Output:

1 -> 2-> 3 -> 1

Operations on Circular Singly linked list

There are two Operations on Circular Singly linked list:

1. Insertion
2. Deletion

1. Insertion

After initialising a circular linked list with some elements, we may want to add more elements, in the beginning, middle or end. This may sound easy, but with linked lists, we must make the necessary links. Otherwise, we’ll lose the randomly stored data.

A node can be added in four ways:

• Insertion at the beginning
• Insertion at the end 
• Insertion in between the nodes
• ​​Insertion After a Specific Element

Inserting in the beginning

To insert an element at the beginning of a circular linked list, we must keep three things in mind:

1. The new node must be linked with the old head node.
    
2. The last node in the circular linked list must be linked to the new node.
    
3. The head node must be reassigned with the new node.
    

The basic process of inserting an element, in the beginning, is as shown below:

The function given below adds a new node to the beginning of the circular linked list.

// Method to traverse through the linked list and return the last element
node *traverse(node*h)
{
    node *q;
    q=h;
    while(q->next!=h)
    {
          q=q->next;
    }
    return q;
}


// Method to add a new node at the beginning
node *add_b(node *h)
{
    // Checks if linked list is empty
    if(h==null)
    {
          h=getnode();
          h->next=h;
          return h;
    }
    else
    {
          node *temp,
          *last;
          
          // New node
          temp=getnode(); 
          
          // New node is linked to the head node
          temp->next=h;    
          last=link(h);
          
          // Last node is linked to the new node
          last->next=temp;
          return temp;
    }
}

Output:

4 -> 1 -> 2-> 3 -> 4

Inserting in the middle

While inserting a new node in the middle, two links have to be made carefully:

1. Link the node after which the new node is to be added and the new node.
2. Link the new node to the rest of the linked list.
    

Let us see the illustration for adding a new node in the middle.

The function for the same is as follows:

// Method to add a new node in the middle
void add_m(node *h)
{

int num;
node *q, *new_node, *temp;
q = h;
printf("Enter the node after which you want to add the new node ");
scanf("%d",&num);

// Finds the node after which a new node is to be added
while(1)   
{
    if(q->data==num)
    {
        break;
    }
    else
    {
        q = q->next;
    }
}

// New node
new_node = getnode();  
temp = q->next;  

// The link between the node after which the new node is added and the new node is formed   
q->next = new_node;   

// New node is linked with the rest of the linked list
new_node->next = temp;  

}

Output:

1 -> 2 -> 4-> 3 -> 1

Inserting in the end

To insert an element at the end of a circular linked list, there are two essential things:

1. The old last node must be linked to the new node.
2. The new node must be linked with the head node.
    

The process of adding a new node to the end can be done as follows:

The function for the same is as follows:

// Function to add a new node to the end
void add_e(node *h)
{
    node *temp,
    *q;
    
    // New node
    temp=getnode(); 
     
    q=h;
    
    while(q->next!=h)
    {
          // Traversing to the end to add the new node
          q=q->next;   
    }
    
    // Old last node is linked to the new node
    q->next=temp;
    
    // New node is linked to the head node    
    temp->next=h;     
}

Output:

1 -> 2 -> 3-> 4 -> 1

Insertion After a Specific Element

To insert a new node after a specific element in a doubly linked list, we need to perform the following steps:

1. Create a new node with the data we want to insert
2. Traverse the list to find the node after which we wish to insert the new node
3. Adjust the pointers to insert the new node after the specified element

The function for the same is as follows:

// Function to insert a new node after a specific element
void insertAfter(struct Node* prevNode, int newData) {
    if (prevNode == NULL) {
        printf("The previous node cannot be NULL.\n");
        return;
    }

    // Create a new node
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;

    // Adjust the pointers
    newNode->prev = prevNode;
    newNode->next = prevNode->next;
    prevNode->next = newNode;

    if (newNode->next != NULL) {
        newNode->next->prev = newNode;
    }
}

2. Deletion

Like inserting, we can delete the elements from the beginning, middle and end of the circular linked list. 

Deleting from the beginning

As in inserting, we must be careful with the links between the nodes while deleting nodes. To delete from the beginning, we must:

1. The last node must be linked with the node after the deleted node.
2. The head node must be reassigned properly.
    

We can understand this better with the following illustration.

Let us now see the method for it.

// Method to delete a node from the beginning
node *delete_b(node *h)
{
    node *temp, *last;
    temp=h;
    last=link(h);
    
    // Head is updated
    h=h->next;
    
    // Node is deleted         
    free(temp);  
    
    // Last node is linked with the new head node   
    last->next=h;  
    return h;
}

Output:

2 -> 4 -> 3 -> 2

Deleting from the Middle

To delete a node from the middle of the circular linked list, we have to link the node, after which we want to delete a node with the rest of the linked list. 

This probably sounds confusing, doesn’t it?

Don’t worry. The following diagram will clear our confusion. 

Now we can try writing the method for it on our own, but it’s given below for help. 

// Method to delete the middle element
void delete_m(node *h)
{

int num;
node *q, *temp1, *temp2;
printf("Enter the number after which you want to delete a node ");
scanf("%d",&num);

while(1)
{
    // Element after which we want to delete a node is searched
    if(q->data==num)  
    {
        break;
    }
    else
    {
        q = q->next;
    }
}

// Node to be deleted
temp1 = q->next; 

// Rest of the linked list 
temp2 = temp1->next;   

// The node after which a node is deleted is linked with the rest of the linked list
q->next = temp2;  

// Node is deleted
free(temp1);   

}

Output:

1 -> 2 -> 3 -> 1

Deleting from the End

While deleting an element from the end, the second to last element in the circular linked list must be linked with the head node, as shown below. 

Now let’s try writing the method for it. You may refer to the solution given below, but not before trying it ourselves first. 

// Method to delete a node from the end
void delete_e(node *h)
{
    node *q, *temp;
    q=h;
    
    // Traversing to the end of the linked list
    while(1)   
    {
          temp=q->next;
          if(temp->next!=h)
          {
              q=q->next;
          }
        else
          {
              break;
          }
    }
    
    // The penultimate element is linked with the head node
    q->next=h; 
    
    // The last node is deleted   
    free(temp);   
}

Output:

1 -> 2 -> 3 -> 1

Deleting at a Given Point

To delete a node at a specific position in a circular linked list, first, we need to handle the head node case, then traverse to the desired position, update pointers, and free the node's memory to maintain the circular structure.

Now let’s try writing the method for it. You may refer to the solution given below, but not before trying it yourself first.

// Function to delete a node at a given position in a circular linked list.
void deleteNodeAtPosition(struct Node** head, int position) {
   if (*head == NULL) {
       printf("List is empty, cannot delete.\n");
       return;
   }
   struct Node* current = *head;
   struct Node* prev = NULL;
   int count = 0;
   // Handle the special case of deleting the head node.
   if (position == 1) {
       while (current->next != *head) {
           current = current->next;
       }
       if (current->next == *head) {
           struct Node* temp = *head;
           current->next = (*head)->next;
           *head = (*head)->next;
           free(temp);
           return;
       }
   }
   // Traverse to the desired position.
   do {
       count++;
       prev = current;
       current = current->next;
       if (count == position - 1) {
           break;
       }
   } while (current != *head);
   // Check if the given position is valid.
   if (current == *head && count != position - 1) {
       printf("Invalid position. Node not found.\n");
       return;
   }
   // Delete the node at the given position.
   prev->next = current->next;
   free(current);
}

Searching in a Circular Linked List

Searching for an element in a circular is very easy too!

Here, all we have to do is traverse through the linked list and check if the number we’re looking for matches with the data in the node. The method is given below for us to check our code.

// Method to search for an element in a circular linked list
void *search(node*h)
{
     // Checking if the linked list is empty
    if(h==null)  
     {
          printf(“Empty Circular Linked List”);
     }
     else
     {
          int temp = 0, num;
          node *q;
          q=h;
          printf(“Enter the element to be searched”);
          scanf(“%d”,&num);
          
          // Traversing through the linked list
          while(q->next!=h)  
          {
               // Checking for element
               if(q->data==num)   
               {
                    printf(“Element found”);
                    temp = 1;
                    break;
               }
              q=q->next;
          }
          
          if(temp==0)
          {
               printf(“Element not found”);
          }
     }
}

Output:

Element found

Advantages of Circular Linked Lists

• Efficient Traversal: A circular linked list allows for continuous traversal from any node to any other node without needing to return to the head or start point. This is particularly useful for applications that require cyclic iteration.
• Ease of Insertion and Deletion: Insertion and deletion operations are easier and more efficient, especially at the beginning and end of the list, compared to a singly linked list, as you don’t need to handle the special case of the last node pointing to null.
• Memory Utilization: Circular linked lists use memory efficiently as they do not require a separate end node or extra storage for null pointers, reducing overhead.
• Flexible Size: Like other linked lists, circular linked lists can grow and shrink dynamically, allowing for flexible memory management compared to fixed-size arrays.
• Simplicity in Implementation: Algorithms that rely on circular structures (e.g., round-robin scheduling) are simpler to implement using circular linked lists compared to arrays or other data structures.

Disadvantages of Circular Linked Lists

• Complexity in Implementation: Implementing circular linked lists can be more complex compared to singly linked lists, especially when it comes to handling edge cases like detecting the end of the list during traversal.
• Difficult Debugging: Debugging issues in circular linked lists can be more challenging because there is no clear end to the list, which can lead to infinite loops if not handled properly.
• More Memory Usage per Node: Each node in a circular linked list needs to store a pointer to the next node, which can lead to higher memory usage compared to arrays, especially when storing small data elements.
• No Direct Access: Similar to other linked lists, circular linked lists do not allow direct access to elements by index, which can lead to inefficient search operations as each element must be accessed sequentially.

Applications of Circular Linked Lists

• Round-Robin Scheduling: Circular linked lists are used in operating systems to manage processes in a round-robin fashion, ensuring each process gets an equal share of CPU time.
• Buffer Management: Circular linked lists can be used to implement circular buffers or ring buffers, which are used in scenarios where data is continuously overwritten, like in streaming data applications.
• Data Structures in Networking: They are used in token ring networks where each node in the network is connected in a circular fashion and tokens are passed around to control access.
• Multiplayer Games: In multiplayer board games, a circular linked list can manage the turn order, cycling through players seamlessly.
• Audio/Video Streaming: Circular linked lists can manage streaming data buffers, ensuring a continuous flow of data without interruptions.
• Continuous Data Processing: Applications requiring continuous or cyclic data processing, such as simulations or real-time systems, can benefit from the cyclic nature of circular linked lists.

Why Circular Linked List?

• Efficient Traversal: Circular linked lists provide efficient traversal from any node to any other node in the list, facilitating operations like rotation or circular navigation.
• Looping Behavior: Circular linked lists naturally exhibit looping behavior, which can be advantageous in certain applications like simulation or modeling.
• Tail Pointer Elimination: Circular linked lists eliminate the need for a separate tail pointer, simplifying certain operations and potentially saving memory.

Frequently Asked Questions

What is the time complexity of circular singly linked list?

The time complexity of basic operations in a circular singly linked list is O(n) for searching, insertion, and deletion when the position is unknown. If the position is known, insertion and deletion are O(1). Accessing an element is also O(n).

Q. What is circular vs normal linked list?

A normal linked list is a linked list that consists of nodes, where each node points towards the next node i.e. each node consists of the address of the next node and the last node points towards NULL. But in a circular linked list, the last node, instead of pointing towards the NULL, points towards the first/head node.

Q. How is circular linked list different from stack?

A circular linked list is a  type of linked list where the last node points towards the last node. Thus, a connection is formed between the last node and the head node. While stack is a data structure that follows the LIFO (Last-In-First-Out) principle, such that the element that is inserted last is to be deleted (popped-out) first.

Q. What operations can you perform on circular linked lists?

Operations performed on a circular linked list are: 1. Traversal, 2. Insertion (at the beginning, middle and end), 3. Deletion (at the beginning, middle and end), 4. Printing, 5. Searching

Conclusion

In this article, we learned about circular linked lists. We first learned what it is, theoretically. Then we wrote the methods for different operations like traversing, insertion, deletion, printing, and searching. 

With this, we have an overall knowledge of circular linked lists, but that’s not enough. Questions like the application of circular linked lists, Advantages Of Linked List, Application of Linked List,  Linked List in Java and many others are commonly asked in interviews. So, we should be well prepared to answer them.

Also, circular linked lists come in handy while solving coding problems too. 

To familiarise ourselves with that, we must practice. Cod360 is a platform that provides both practice coding questions and commonly asked interview questions. The more we’ll practice, the better our chances are of getting into a dream company of ours.

Happy Learning!