Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is a circular linked list in C?
3.
Types of Circular Linked List in C
3.1.
Circular Singly Linked List
3.2.
Circular Doubly Linked List
4.
Creating Circular Linked List in C
5.
Traversing Through a Circular Linked List
6.
Inserting an Element
6.1.
Inserting in the beginning
6.2.
Inserting in the middle
6.3.
Inserting in the end
6.4.
Insertion After a Specific Element
7.
Deleting an Element 
7.1.
Deleting from the beginning
7.2.
Deleting from the Middle
7.3.
Deleting from the End
7.4.
Deleting at a Given Point
7.5.
Searching in a Circular Linked List
8.
Frequently Asked Questions
8.1.
Q. What is a circular linked list?
8.2.
Q. What is a circular doubly linked list in C?
8.3.
Q. What are the two types of circular linked lists?
8.4.
Q. Where is the circular linked list used?
8.5.
Q. What is circular vs normal linked list?
8.6.
Q. How is circular linked list different from stack?
8.7.
Q. What operations can you perform on circular linked lists?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

Circular Linked List in C

Author Geetika Dua
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

Almost all of us have played Chinese Whispers. If you haven’t, it’s a game where a person whispers a message to the next person until the end of the row. This game is popularly played to break the ice between random people in a group. 

linked list is similar to playing Chinese Whispers. The random people there are the data stored in random addresses called nodes here. The link formed between the people by whispering a message in the game is formed by storing the address of the next node (using pointers) in a linked list.  

Circular Linked List

The diagram below shows this idea pictorially.

circular linked list

Here, NULL is stored in the address part of the last node. 

Thus, to formally define a linked list, 

A linked list is a linear Data Structure where randomly stored data are linked with pointers. 

Now that we know what a linked list is, let’s use our previous example to understand a circular linked list. 

We can play Chinese Whispers in a row or a circle. When played in a circle, the last person whispers the message he heard to the first person again. In this way, a link is formed between the last and the first person. 

Similarly, in a circular linked list, instead of storing NULL in the address part of the last node, the address of the first node is saved to make the list circular. 

circular linked list

Thus, to define a circular linked list,

Also read - Merge sort in linked list

What is a circular linked list in C?

A circular linked list is a  type of linked list where the last node points towards the head/first node. Thus, a connection is formed between the last node and the head node. Unlike a standard linked list, there is no NULL at the end of the circular linked list. 

Now that we know what are circular linked lists in C, moving forward, we will discuss the types of circular linked lists.

Let us see that next. 

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Types of Circular Linked List in C

There are mainly two types of circular linked lists: Circular singly linked lists and Circular doubly linked lists.

Circular Singly Linked List

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.

Circular Singly Linked List

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. 

Circular Doubly Linked List

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. 

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

Inserting an Element

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.

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:

process

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.

inserting at 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:

insert at end

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;
    }
}

Deleting an Element 

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.

beginning deletion

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. 

middle deletion

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. 

end deletion

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

Frequently Asked Questions

Q. What is a circular linked list?

A circular linked list is a data structure where randomly stored data are linked with pointers, and the last node is linked to the first node.

Q. What is a circular doubly linked list in C?

A circular doubly linked list in C is a data structure where each node has two pointers, one pointing to the next node and another to the previous node, forming a loop. It allows traversal in both directions.

Q. What are the two types of circular linked lists?

Singly Circular Linked List has nodes with a next pointer, forming a loop. Doubly Circular Linked List adds a previous pointer for bidirectional traversal in a closed loop.

Q. Where is the circular linked list used?

Circular linked lists are used in applications where efficient cyclic data handling is required, such as managing tasks in a round-robin scheduling algorithm, implementing circular buffers, and representing circular data structures like rings or carousels.

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 ListApplication 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. Coding Ninjas Studio 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!

Previous article
Circular Linked List
Next article
Singly Linked List To Circular Linked List
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass