A Circular linked list in C programming performs a reverse traversal with less memory usage than a doubly linked list. We require extra memory for the previous pointer in a doubly linked list.
When we compare the circular linked list with both singly linked list and doubly linked list, we don't find null in any of the nodes; instead, the last node's address stores the address of the first node. So basically, the tail node reconnects to the head node, making it a circular linked list.
What Is a Circular Linked List in C?
A Circular singly linked list is a collection of data called nodes, where the last node links to the first node. The traversal of a circular singly linked list is until we reach the same node we started in a list.
Now we know what a circular linked list is, let’s look at the memory representation with the help of a diagram.
Memory Representation of a Circular Linked List
Let's consider the below-given diagram and understand the memory representation of a circular linked list.
So first, Let's consider four elements to insert into the list. For which creat four nodes, where each node consists of a data and address part stored at some random address. In the singly linked list, the last node next pointer points to Null. But When we compare a circular singly linked list with the singly linked list, we don't find a null.
In a circular singly linked list, the last node's next pointer holds the address of the first node. In other words, we can say that “The Tail node's address is pointing toward the Head node of the linked list.”
Every node in a linked list connects with the other through a pointer that points to the address of the next node, and the arrows in this diagram represent that.
For Example:
Let our elements to insert be 10, 20, 30, 40.
- As you can notice from the above diagram, The last node's next pointer is pointing to the address of the first node, address1.
- The next part of the first node holds the address of the next node, address2.
- Similarly, the second node has the address of the third node, address 3.
- Following, the third node holds the address of its next node. And the last node contains the address of the first node. In this way, they have linked together.
- A reverse traversal is possible with less memory usage in a circular linked list than in a doubly linked list.
- The traversal is until we reach the same node we started from the list.
Moving ahead, Let’s look at the general syntax of circular singly linked list in c.
Syntax of Circular Linked List
struct node
{
int data;
struct node* next;
};
Let's look at the simple, circular linked list program.
#include <stdio.h>
#include <stdlib.h>
void display();
struct Node {
int data;
struct Node* next;
};
int main()
{
struct Node* last;
struct Node* first;
struct Node* second;
struct Node* third;
struct Node* fourth;
first = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));
fourth = (struct Node*)malloc(sizeof(struct Node));
first->data = 10;
second->data = 20;
third->data = 30;
fourth->data = 40;
first->next = second;
second->next = third;
third->next = fourth;
fourth->next = first;
last = fourth;
display(last);
return 0;
}
void display(struct Node* last_node) {
struct Node* ptr;
if (last_node == NULL) {
printf("The list is empty");
return;
}
ptr = last_node->next;
do {
printf("%d ", ptr->data);
ptr = ptr->next;
} while (ptr != last_node->next);
}
Output:
Now, you will go through the operations performed on a circular linked list.
Operations on Circular Linked List
- Insertion operation
- Deletion operation
- Traversal operation
Insertion Operation
Operation |
Description |
|
Insertion at beginning |
Inserts the element at the beginning of the linked list |
|
Insertion at end |
Insert the element at the end of the list |
|
Insertion after certain node |
Insert element after specific element |
Let's understand it practically.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* insertToEmptylist(struct Node* head, int data) {
if (head != NULL)
return head;
struct Node* new = (struct Node*)malloc(sizeof(struct Node));
new->data = data;
head = new;
head->next = head;
return head;
}
struct Node* insertAtbegin(struct Node* head, int data) {
if (head == NULL)
return insertToEmptylist(head, data);
struct Node* new = (struct Node*)malloc(sizeof(struct Node));
new->data = data;
new->next = head->next;
head->next = new;
return head;
}
struct Node* insertAtend(struct Node* last, int data) {
if (last == NULL)
return insertToEmptylist(last, data);
struct Node* new = (struct Node*)malloc(sizeof(struct Node));
new->data = data;
new->next = last->next;
last->next = new;
last = new;
return last;
}
struct Node* insertionAfternode(struct Node* last, int data, int ele) {
if (last == NULL)
return NULL;
struct Node *new, *ptr;
ptr = last->next;
do {
if (ptr->data == ele) {
new = (struct Node*)malloc(sizeof(struct Node));
new->data = data;
new->next = ptr->next;
ptr->next = new;
if (ptr == last) last = new;
return last;
}
ptr = ptr->next;
} while (ptr != last->next);
printf("\nThe node is not present in the linked list");
return last;
}
void display(struct Node* head) {
struct Node* ptr;
if (head == NULL) {
printf("The list is empty");
return;
}
ptr = head->next;
do {
printf("%d ", ptr->data);
ptr = ptr->next;
} while (ptr != head->next);
}
int main() {
struct Node* head = NULL;
head=insertToEmptylist(head, 30);
head=insertAtend(head, 40);
head=insertAtbegin(head, 10);
head=insertionAfternode(head, 20, 10);
printf("Linked list elements are: \n");
display(head);
return 0;
}
Output:
Deletion Operation
Operation |
Description |
|
Deletion at beginning |
delete the element from the beginning of the linked list |
|
Deletion at end |
delete the element from the end of the list |
|
Deletion after specific node |
delete element after specific element |
Program to perform deletion operation on Circular Linked List.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* insertToEmptylist(struct Node* head, int data)
{
if (head != NULL)
return head;
struct Node* new = (struct Node*)malloc(sizeof(struct Node));
new->data = data;
head = new;
head->next = head;
return head;
}
struct Node* insertAtbegin(struct Node* head, int data)
{
if (head == NULL)
return insertToEmptylist(head, data);
struct Node* new = (struct Node*)malloc(sizeof(struct Node));
new->data = data;
new->next = head->next;
head->next = new;
return head;
}
struct Node* insertAtend(struct Node* last, int data)
{
if (last == NULL)
return insertToEmptylist(last, data);
struct Node* new = (struct Node*)malloc(sizeof(struct Node));
new->data = data;
new->next = last->next;
last->next = new;
last = new;
return last;
}
struct Node* insertionAfternode(struct Node* last, int data, int ele)
{
if (last == NULL)
return NULL;
struct Node *new, *ptr;
ptr = last->next;
do {
if (ptr->data == ele)
{
new = (struct Node*)malloc(sizeof(struct Node));
new->data = data;
new->next = ptr->next;
ptr->next = new;
if (ptr == last) last = new;
return last;
}
ptr = ptr->next;
} while (ptr != last->next);
printf("\nThe node is not present in the linked list");
return last;
}
void deleteNode(struct Node** last, int key_node)
{
if (*last == NULL)
return;
if ((*last)->data == key_node && (*last)->next == *last)
{
free(*last);
*last = NULL;
return;
}
struct Node *temp = *last, *dele_node;
if ((*last)->data == key_node)
{
while (temp->next != *last)
temp = temp->next;
temp->next = (*last)->next;
free(*last);
*last = temp->next;
}
while (temp->next != *last && temp->next->data != key_node)
{
temp = temp->next;
}
if (temp->next->data == key_node)
{
dele_node = temp->next;
temp->next = dele_node->next;
free(dele_node);
}
}
void display(struct Node* head)
{
struct Node* ptr;
if (head == NULL)
{
printf("The list is empty");
return;
}
ptr = head->next;
do {
printf("%d ", ptr->data);
ptr = ptr->next;
} while (ptr != head->next);
}
int main()
{
struct Node* head = NULL;
head=insertToEmptylist(head, 30);
head=insertAtend(head, 40);
head=insertAtbegin(head, 10);
head=insertionAfternode(head, 20, 10);
printf("Linked list elements: \n");
display(head);
printf("\n after deletion, the Linked list elements are: ");
deleteNode(&head, 40);
printf("\n");
display(head);
return 0;
}
Output:
Traversal Operation
Operation |
Description |
|
Traversal |
Visiting every node in a list at least once |
In a circular linked list traversal operation, we visit every node at least once to display all the data elements or perform operations.
Function to perform traversal operation on circular singly linked list
void traversal (struct Node* head) {
struct Node* ptr;
if (head == NULL) {
printf("The list is empty");
return;
}
ptr = head->next;
do {
printf("%d ", ptr->data);
ptr = ptr->next;
} while (ptr != head->next);
}
Therefore, we have reached the end of this tutorial on Circular Linked List In C.
If you're eager to gain the skills required to work in a challenging, rewarding, and dynamic IT role - we've got your back! Discover the endless opportunities through this innovative Post Graduate Program in Full Stack Web Development course designed by our partners at Caltech CTME. Enroll today!
Next Steps
"Circular Doubly Linked List In C" can be your next topic. So far, you have learned the Circular Linked List In C. The following fundamentals will be the data structures and the varieties in data structures used for different purposes.
If you are interested in software development, you can explore Simplilearn's Courses that will give you the work-ready software development training you need to succeed today. Are you looking for a comprehensive training program in the most in-demand software development skills, tools, and languages? Our Post Graduate Program in Full Stack Web Development should be the right thing for your career. Explore the course and enroll soon.
Please let us know in the comment section below if you have questions regarding the "Circular Linked List In C" tutorial. Our experts will get back to you at the earliest.
