Circular Linked List in C

Here you will get program for circular linked list in C.

What is Circular Linked List?

A circular linked list is a linked list in which the last node points to the head or front node making the data structure to look like a circle.  A circularly linked list node can be implemented using singly linked or doubly linked list.

The below representation shows how a circular linked list looks like. Unlike the linear linked list, the last node is pointed to the head using a rear pointer.

 
Program for Circular Linked List in C

We basically have 3 nodes head, rear and temp to implement a circular linked list. The rear points to the last node of the list, head points to first node. This helps to maintain a track on where is the front and rear nodes of the circle. Let us see the basic operations such as creation, deletion and displaying of the elements of the circular linked list.

Creation of Node

This is much similar to that of creating a node in singly linked list. It involves creating a new node and assigning data and pointing the current node to the head of the circular linked list. The code is as shown below.

void create()
{
	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;
}

 
Deletion of Node

We conventionally delete the front node from the list in this program. To delete a node, we need to check if the list is empty. If it is not empty then point the rear node to the front->next and rear->next to front. This removes the first node.

void del()
{
	temp=front;
	if(front==NULL)
		printf("\nUnderflow :");
	else
	{
		if(front==rear)
		{
			printf("\n%d",front->info);
			front=rear=NULL;
		}
		else
		{
			printf("\n%d",front->info);
			front=front->next;
			rear->next=front;
		}

	temp->next=NULL;
	free(temp);
	}
}

 
Traversing Circular Linked List

Traversing the circular list starts from front node and iteratively continues until the rear node. The following function is used for this purpose.

void display()
{
	temp=front;
	if(front==NULL)
		printf("\nEmpty");
	else
	{
		printf("\n");
		for(;temp!=rear;temp=temp->next)
			printf("\n%d address=%u next=%u\t",temp->info,temp,temp->next);
			printf("\n%d address=%u next=%u\t",temp->info,temp,temp->next);
	}
}

Complete Program

#include<stdio.h>
#include<stdlib.h>

typedef struct Node

{
	int info;
	struct Node *next;
}node;

node *front=NULL,*rear=NULL,*temp;

void create();
void del();
void display();

int main()
{
	int chc;
	do
	{
 	printf("\nMenu\n\t 1 to create the element : ");
	printf("\n\t 2 to delete the element : ");
	printf("\n\t 3 to display the queue : ");
	printf("\n\t 4 to exit from main : ");
	printf("\nEnter your choice : ");
	scanf("%d",&chc);
	
		switch(chc)
		{
			case 1:
	 		create();
			break;
	 	
		 	case 2:
	 		del();
	 		break;
	 
	 		case 3:
	 		display();
	 		break;
	 
	 		case 4:
	 		return 1;
	 		
			default:
	 			printf("\nInvalid choice :");
	 	}
	}while(1);

	return 0;
}

void create()
{
	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;
}

void del()
{
	temp=front;
	if(front==NULL)
		printf("\nUnderflow :");
	else
	{
		if(front==rear)
		{
			printf("\n%d",front->info);
			front=rear=NULL;
		}
		else
		{
			printf("\n%d",front->info);
			front=front->next;
			rear->next=front;
		}

	temp->next=NULL;
	free(temp);
	}
}

void display()
{
	temp=front;
	if(front==NULL)
		printf("\nEmpty");
	else
	{
		printf("\n");
		for(;temp!=rear;temp=temp->next)
			printf("\n%d address=%u next=%u\t",temp->info,temp,temp->next);
			printf("\n%d address=%u next=%u\t",temp->info,temp,temp->next);
	}
}

Output

The above program results in the following output. You can see that the last node points to the first node address that is the main theme of circular linked list in C.