Circular linked list in C

What is a circular linked list in c?

A circular linked list is a linked list in which a pointer is used to point the last node to the first node of the list. A circular linked list is classified into a circular singly linked list and a circular doubly linked list. In the circular linked list, we can initialize the traversing at any node and traverse the list in either the forward or backward direction. Till we reach the same node where we started. Thus a circular linked list has no starting and no end.

Circular singly linked list:

It is a linked list in which a pointer is used to point the last node to the first node of the list. 

Circular doubly linked list:

It is a linked list that contains a pointer that points to the next node as well as the previous node.

Implementation of circular linked list in c program:

#include<stdio.h>
#include<stdlib.h>
 // representation of node in circular linked list
typedef struct Node
 
{
int info;
struct Node *next;
}node;
 // intializing front and rear value to Null
node *front=NULL,*rear=NULL,*temp;
void insert();//declaring function for inserting nodes
void print();// displaying function for inserting nodes
 // main program
int main()
{
int chc;
do
{// menu for cicular linked list by using switch case
printf("\nMenu\n\t 1 to insert the element : ");
printf("\n\t 2 to print the queue : ");
printf("\n\t 3 to exit from main : ");
printf("\nEnter your choice : ");
scanf("%d",&chc);
switch(chc)
{
case 1:
insert();
break;
case 2:
print();
break;
case 3:
return 1;
default:
printf("\nInvalid choice :");
}
}while(1);
 
return 0;
}
 //function definition for insert 
void insert()
{
node *newnode;
newnode=(node*)malloc(sizeof(node));
printf("\nEnter the node value : ");
scanf("%d",&newnode->info);
newnode->next=NULL;
if(rear==NULL)
front=rear=newnode;
else
{
rear->next=newnode;
rear=newnode;
}
rear->next=front;
}
 // function definition for displaying nodes in circular linked list
void print()
{
temp=front;
if(front==NULL)
printf("\nEmpty");
else
{
printf("\n");
for(;temp!=rear;temp=temp->next)
printf("\n%d \t",temp->info,temp,temp->next);
printf("\n%d \t",temp->info,temp,temp->next);
}
}

Output:

Where circular linked list in c  is used?

Circular linked lists are widely used in OS for task maintenance. Let us consider an example, when we are surfing the Internet we can use the back and forward buttons to move the earlier visited previous, and the next pages, respectively.

How is this done? The answer is simple. A circular linked list maintains the sequence of the web pages visited. Traversing this circular linked list either in the front or back direction helps to visit the pages which are already visited.

How it is maintained in the memory?

In order to form a link list, we need a structure called node that has two fields – data and next. The data field will store the information part and the next field will store the address of the node in the sequence.

For example,

START=1

Here, we see that a variable start is used to store the address of the first node. In this example, start=1 so the data is stored at address 1 which is H. The corresponding next stores the address of the next note which is 4. So, we look at address 4, to fetch the next data item.

The second data coming from address 4 is E. Then check the next to go to the next node. After that entry in the next, we get the next address, that is 7, and fetch L as the data.

We repeat this procedure until we reach a position where the next entry contains the address of the first node of the list.

This denotes the end of the linked list. When we traverse the data and the next field in this manner, we will finally see that the linked list here together forms the word ‘HELLO’.

Also, read Using map() and filter() Convert Code to solve problems.