Circular Linked List Implementation

In a circular Singly linked list, the last node of the list contains a pointer to the first node of the list. We can have circular singly linked list as well as circular doubly linked list.

We traverse a circular singly linked list until we reach the same node where we started. The circular singly liked list has no beginning and no ending. There is no null value present in the next part of any of the nodes.

As we know that singly linked list and doubly linked list are already present in there in data structure and algorithm then what is the need of circular linked list?

When we want to access the things in a loop repeatedly. Circular Linked List is ideal so that, whenever we reach the last node we can restart operations again by directly reaching the first node from the last node itself.

There are basically two types of circular linked list:

Circular Singly Linked List
Circular Doubly Linked List

Following is a Circular Singly Linked List representation.

Algorithm

Node creation :

Singly circular linked list

struct Node 
{
    int data;
    struct Node *next;
}

Doubly circular linked list

struct node   
{  
    struct node *prev, *next; 
    int data; 
}

Insertion :

Insertion at beginning - Adding a node into circular singly linked list at the beginning.
Insertion at the end - Adding a node into circular singly linked list at the end.

Deletion & Traversal:

Deletion at beginning - Removing the node from circular singly linked list at the beginning.
Deletion at the end - Removing the node from circular singly linked list at the end.
Searching - Compare each element of the node with the given item and return the location at which the item is present in the list otherwise return null.
Traversing - Visiting each element of the list at least once in order to perform some specific operation.

Program using C

//CIRCULAR SINGLY LINKED LIST
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<conio.h>
struct node
{
	int data;
	struct node *next;
};
struct node *start = NULL, *x,*y;
int n = 0;
void ins_at_any_pos();
void del_at_any_pos();
void traverse();
void main()
{
	int ch;
	while(1)
	{
		printf("\nMENU\n1. INSERT\n2. DELETE\n3. DISPLAY\n4. EXIT\nEnter your choice: ");
		scanf("%d",&ch);
		switch(ch)
		{
			case 1: 
				ins_at_any_pos();
				break;
			case 2: 
				del_at_any_pos();
				break;
			case 3: 
				traverse();
				break;
			case 4: exit(0);
			default: printf("Wrong choice\n");
		}
	}
}

void ins_at_any_pos()
{
	struct node *ptr;
	int pos, count = 1;
	printf("Enter the position to be inserted at: ");
	scanf("%d",&pos);
	if(pos != 1 && start==NULL)
	{
		printf("Not a valid position. List is empty.");
		return;
	}
	y=(struct node*)malloc(sizeof(struct node));
	n++;
	printf("\nEnter the data: ");
	scanf("%d",&y->data);
	if(pos==1)
	{
		if(start==NULL)
		{
			y->next =y;
			start = y;
		}
		else
		{
			y->next=start;
			y=start;
			while(x->next!=start)
				x=x->next;
			x->next=y;
			start = y;
		}
	}
	else
	{
		x=start;
		ptr=start;
		count =1;
		while(ptr->next != start && count<pos)
		{
			count++;
			x=ptr;
			ptr=ptr->next;
		}
		if(count==pos)
		{
			x->next=y;
			y->next=ptr;
		}
		else if(pos==count+1)
		{
			ptr->next=y;
			y->next=start;
		}
		else
			printf("Position not found or Invalid position.");
	}
}

void del_at_any_pos()
{
	int c,pos;
	if(start ==NULL)
		printf("List is empty");
	else
	{
		c=1,pos;
		printf("\nEnter the position to be deleted: ");
		scanf("%d",&pos);
		if(pos==1)
		{
			x=start;
			y=start;
			while(x->next != start)
				x= x->next;
			start = y->next;
			x->next=start;
			free(y);
			n--;	
		}
		else
		{
			x=start;
			while(c<pos && x->next != start)
			{
				y=x;
				x=x->next;
				c++;
			}
			if(c==pos)
			{
				y->next=x->next;
				free(x);
				n--;
			}
			else
				printf("Invalid position");
		}
	}	
}

void traverse()
{
	if(start == NULL || n == 0)
		printf("\nList is empty");
	else
	{
		printf("\nThe list is: \n");
		x=start;
		while(x->next != start)
		{
			printf("%d->",x->data);
			x=x->next;
		}
		printf("%d",x->data);
	}
}