Do you think IIT Guwahati certified course can help you in your career?
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.
A 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.
The diagram below shows this idea pictorially.
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.
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.
There are mainly two types of circular linked lists: Circular singly linked lists and Circular doubly linked lists.
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.
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.
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:
The new node must be linked with the old head node.
The last node in the circular linked list must be linked to the new node.
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:
Link the node after which the new node is to be added and the new node.
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:
The old last node must be linked to the new node.
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:
Create a new node with the data we want to insert
Traverse the list to find the node after which we wish to insert the new node
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:
The last node must be linked with the node after the deleted node.
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
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 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.
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.
85+ registered 