Circular Linked List

Circular Linked list

Creation of a Circular Linked List:

A circular linked list is similar to that of a singly linked list with the only difference that the last node points the first node of the list, such that a circular path is obtained.  Thus last node of this list instead of pointing to NULL points to the head node as described in the following figure:-

Program to implement a Circular Linked List

/*Circular Linked List*/

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

typedef struct clist
{
int info;
clist *next;
}clist;

clist *create()
{
clist *temp;
temp=(clist *)malloc(sizeof(clist));
if(temp==NULL)
{
printf(“nMemory Allocation Error!”);
exit(1);
}
return temp;
}

clist *makenode(int x)
{
clist *ptr=create();
ptr->info=x;
ptr->next=NULL;
return ptr;
}

clist *insertend(clist *head,int x)
{
clist *temp,*ptr=makenode(x);
if(head==NULL)
{head=ptr;
ptr->next=head;
}
else
{temp=head;
while(temp->next!=head)
temp=temp->next;
ptr->next=head;
temp->next=ptr;
}
return head;
}

void display(clist *head)
{
clist *temp;
if(head==NULL)
{
printf(“nList is empty.”);
return;
}
if(head==head->next)
{
printf(“%d->”,head->info);
return;
}
temp=head;
printf(“%d->”,temp->info);
temp=temp->next;
while(temp!=head)
{
printf(“%d->”,temp->info);
temp=temp->next;
}
printf(“bb “);
}

void main()
{
int choice,x;
clist *head=NULL;
while(1)
{
clrscr();
printf(“ntCircular List – Menu”);
printf(“nnt1. Generate Circular list”);
printf(“nt2. Display List”);
printf(“nt3. Exit”);
printf(“ntEnter your choice?”);
scanf(“%d”,&choice);
switch(choice)
{
case 1:
printf(“nEnter the number?”);
scanf(“%d”,&x);
head=insertend(head,x);
break;
case 2:
display(head);
break;
case 3:
exit(0);
default:
printf(“nInvalid choice.”);
}
getch();
}
}

Traversal in a Circular Linked List:  Traversal involves keeping a temp pointer on the first node of the list and printing its value.  This pointer is then moved while printing the node’s value until this node becomes equal to head node.  The ‘C’ function is given below:

/*traversal of circular linked list*/
void display(clist *head)
{
clist *temp;
if(head==NULL)
{
printf(“nList is empty.”);
return;
}
if(head==head->next)
{
printf(“%d->”,head->info);
return;
}
temp=head;
printf(“%d->”,temp->info);
temp=temp->next;
while(temp!=head)
{
printf(“%d->”,temp->info);
temp=temp->next;
}
printf(“bb “);
}

Searching a node in a given Circular List:

/*search node in a circular linked list*/
void search(clist *head,int val)
{
clist *temp;
int flag=0;
if(head==NULL)
{printf(“nList is empty.”);
return;
}
temp=head;
while(temp->next!=head)
{if(temp->info==val)
{flag=1;
break;
}
temp=temp->next;
}
if(temp->info==val)
flag=1;
if(flag==1)
printf(“nNumber found.”);
else
printf(“nNumber not found.”);
}

Deleting a node from a Circular List:

/*delete a given node*/

/*this code does not assume fixed head*/
/*thus after deletion of a node, the linked
list is displayed from the next node in
circular fashion.
example: 11->12->13->14
deleting 12 displays 13->14->11
thus head node shifts continuously.*/

clist *deletenode(clist *head,int x)
{
clist *temp,*prev;
if(head==NULL)
{printf(“nList is empty.”);
return head;
}
if(head->next==head)
{printf(“nDeletion of first node.”);
temp=head;
head=NULL;
free(temp);
return head;
}
temp=head;
/*position temp at node to delete*/
while((temp->info!=x)&&(temp->next!=head))
temp=temp->next;
if((temp->next==head)&&(temp->info!=x))
{printf(“nGiven node does not exist.”);
return head;
}
/*position prev before temp.
the following loop works fine with circular list*/
for(prev=temp;prev->next!=temp;prev=prev->next);

prev->next=temp->next;
free(temp);
return (prev->next);
/*return prev->next since deletion of first node
removes head and shift head to next node.*/
}

Disposing a Circular Linked List:

/*dispose circular linked list*/
/*
Entire circular list may be disposed off
by counting the number of nodes,n, freeing
memory n times and returning NULL.
*/
clist *dispose(clist *head)
{
clist *temp;
int i,count=1;
for(temp=head;temp->next!=head;temp=temp->next)
count++;

for(i=1;i<=count;i++)
{temp=head;
head=head->next;
free(temp);
}
return NULL;
}