Circular Linked Lists: Operations in C Language
In the last tutorial, we learned about this new data structure, the circular linked
lists. Additionally, we discussed the difference and similarities between a circular
linked list and a linear linked list.
Let me quickly summarize some of the most important points:
1. Unlike singly-linked lists, a circular linked list has no node pointing to
NULL. Hence it has no end. The last element points at the head node.
2. All the operations can still be done by maintaining an extra pointer fixed at
the head node.
3. A circular linked list has a head node, but no starting node.
We even learned traversing through the circular linked list using the do-while
approach. Today, we’ll see one of the operations, insertion in a doubly-linked list
with the help of C language.
Creating the circular linked list:
1. Creating a circular linked list is no different from creating a singly linked
list. One thing we do differently is that instead of having the last element
to point to NULL, we’ll make it point to the head.
struct Node
{
int data;
struct Node *next;
};
int main(){
struct Node *head;
struct Node *second;
struct Node *third;
struct Node *fourth;
// Allocate memory for nodes in the linked list in Heap
head = (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));
// Link first and second nodes
head->data = 4;
head->next = second;
// Link second and third nodes
second->data = 3;
second->next = third;
// Link third and fourth nodes
third->data = 6;
third->next = fourth;
// Terminate the list at the third node
fourth->data = 1;
fourth->next = head;
return 0;
}
Traversing the circular linked list:
1. Create a void function linkedListTraversal and pass the head pointer of the
linked list to the function.
2. In the function, create a pointer ptr pointing to the head.
3. Run a do-while loop until ptr reaches the last node, and ptr-
> next becomes head, i.e. ptr->next = head. And keep
printing the data of each node.
4. So, this is how we traverse through a circular linked list. And
do-while was the key to make it possible.
Traversing the circular linked list:
5. Create a void function linkedListTraversal and pass the head
pointer of the linked list to the function.
6. In the function, create a pointer ptr pointing to the head.
7. Run a do-while loop until ptr reaches the last node, and ptr-
> next becomes head, i.e. ptr->next = head. And keep
printing the data of each node.
8. So, this is how we traverse through a circular linked list. And
do-while was the key to make it possible.
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next;
};
void linkedListTraversal(struct Node *head){
struct Node *ptr = head;
do{
printf("Element is %d\n", ptr->data);
ptr = ptr->next;
}while(ptr!=head);
}
int main(){
struct Node *head;
struct Node *second;
struct Node *third;
struct Node *fourth;
// Allocate memory for nodes in the linked list in Heap
head = (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));
// Link first and second nodes
head->data = 4;
head->next = second;
// Link second and third nodes
second->data = 3;
second->next = third;
// Link third and fourth nodes
third->data = 6;
third->next = fourth;
// Terminate the list at the third node
fourth->data = 1;
fourth->next = head;
linkedListTraversal(head);
return 0;
}
