Table of Contents
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.
Thus, to define 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
Till now, we have only seen what a circular linked list is theoretically. So you may be wondering how we create a circular linked list?
Let us see that next.
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;
x->next=head; //Last element is linked to the first one
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)
{
if(h==null) //Checking if the linked list is empty
{
printf(“Empty Circular Linked List”);
}
else
{
node *q;
q=h;
while(q->next!=h) //Traversing through the linked list
{
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)
{
if(h==null) //Checking if the linked list is empty
{
printf(“Empty Circular Linked List”);
}
else
{
node *q;
q=h;
while(q->next!=h) //Traversing through the linked list
{
printf(“%d -> ”,q->data); //Printing the elements
q=q->next;
}
printf(“%d”,q->data);//Printing the first element again to show the circular nature
}
}
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;
temp=getnode(); //New node
temp->next=h; //New node is linked to the head node
last=link(h);
last->next=temp; //Last node is linked to the new node
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);
while(1) //Finds the node after which a new node is to be added
{
if(q->data==num)
{
break;
}
else
{
q = q->next;
}
}
new_node = getnode(); //New node
temp = q->next;
q->next = new_node; //The link between the node after which the new node is added and the new node is formed
new_node->next = temp; //New node is linked with the rest of the linked list
}
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;
temp=getnode(); //New node
q=h;
while(q->next!=h)
{
q=q->next; //Traversing to the end to add the new node
}
q->next=temp; //Old last node is linked to the new node
temp->next=h; //New node is linked to the head node
}
Output:
1 -> 2 -> 3-> 4 -> 1
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);
h=h->next; //Head is updated
free(temp); //Node is deleted
last->next=h; //Last node is linked with the new head node
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)
{
if(q->data==num) //Element after which we want to delete a node is searched
{
break;
}
else
{
q = q->next;
}
}
temp1 = q->next; //Node to be deleted
temp2 = temp1->next; //Rest of the linked list
q->next = temp2; //The node after which a node is deleted is linked with the rest of the linked list
free(temp1); //Node is deleted
}
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;
while(1) //Traversing to the end of the linked list
{
temp=q->next;
if(temp->next!=h)
{
q=q->next;
}
else
{
break;
}
}
q->next=h; //The penultimate element is linked with the head node
free(temp); //The last node is deleted
}
Output:
1 -> 2 -> 3 -> 1
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)
{
if(h==null) //Checking if the linked list is empty
{
printf(“Empty Circular Linked List”);
}
else
{
int temp = 0, num;
node *q;
q=h;
printf(“Enter the element to be searched”);
scanf(“%d”,&num);
while(q->next!=h) //Traversing through the linked list
{
if(q->data==num) //Checking for element
{
printf(“Element found”);
temp = 1;
break;
}
q=q->next;
}
if(temp==0)
{
printf(“Element not found”);
}
}
}
Output:
Element found
Frequently Asked Questions
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.
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
A circular linked list can be used as follows:
1. As a stack
2. As a queue
3. In Fibonacci heap
4. In operating systems to share time for different users
5. Multiplayer games to swap between players in a loop
6. In the concept of the “undo” function
The advantages of circular linked lists are:
1. Any element can be used as the head node
2. Implementing a queue is easier using circular linked lists
3. Used in advanced data structures like a Fibonacci heap
A linked list is circular if the address part of the last node contains the address of the head node instead of NULL, that is if the last node is linked with the head node.
The only difference between a linked list and a circular linked list is that the last node is linked to the first one. Therefore, we can easily make out that to use a singly and doubly-linked list as a circular linked list, we will link the last node with the head node instead of with NULL.
Key Takeaways
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 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. CodeStudio 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!
By: Neelakshi Lahiri
