DATA STRUCTURES
circular linked list
Circular Linked list:
A circular linked list is a collection of elements in which every element has a link to its next element in the sequence and the last element has a link to the first element. That means circular linked list is similar to the singly linked list except that the last node points to the first node in the list. Hence we can traverse in a circular fashion.
Here the beginning of the list is pointed by start or head pointer and the last node does not contain NULL in next pointer instead it contains the address of the first node in the list.
syntax
struct node
{
int data;
struct node *next;
}
Memory representation:
//here upload image for MR.
Menu driven program for circular linked list:
// circular singly linked list
// all operations
//roll no. and name stored as data
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>
struct node
{
int roll;
char name[20];
struct node *link;
};
struct node *head=NULL;
void insertnode_start(int proll, char name[])
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->roll=proll;
strcpy(temp->name,name);
temp->link=NULL;
if(head==NULL)
{
head=temp;
head->link=head;
}
else
{
temp->link=head;
head=temp;
}
}
void insertnode_end(int proll,char name[])
{
struct node *cur=head;
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->roll=proll;
strcpy(temp->name,name);
temp->link=NULL; //last node points to head ,means starting point
if(head==NULL)
{
head=temp;
head->link=head;
}
else
{
while(cur->link!=head)
{
cur=cur->link;
}
cur->link=temp;
temp->link=head;
}
}
void insertnode_loc(int loc, int proll,char name[])
{
int i;
struct node *cur=head;
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->roll=proll;
strcpy(temp->name,name);
temp->link=NULL;
for(i=1;i<loc;i++)
cur=cur->link;
if(loc<1 || cur==head || cur->link==head)
{
printf("nWrong Location - Insertion not possible n");
return;
}
temp->link=cur->link;
cur->link=temp;
}
void deletenode_start()
{
struct node *cur=head;
if(head==NULL)
{
printf("nLinked is Empty ");
return;
}
head=head->link;
free(cur);
printf("n%d Node Deleted from Start",cur->roll);
}
void deletenode_end()
{
struct node *cur=head;
struct node *prev;
if(head==NULL)
{
printf("nLinked is Empty ");
return;
}
while(cur->link!=head)
{
prev=cur;
cur=cur->link;
}
prev->link=head;
free(cur);
printf("n %d Node Deleted from End",cur->roll);
}
void deletenode_loc(int loc)
{
struct node *cur=head;
struct node *prev;
int i;
if(head==NULL)
{
printf("nLinked is Empty ");
return;
}
for(i=1;i<loc;i++)
{
prev=cur;
cur=cur->link;
}
if(loc<1 || cur==head || cur->link==head)
{
printf("nWrong Location - Deletion not possible n");
return;
}
prev->link=cur->link;
free(cur);
printf("nNode %d Deleted ",loc);
}
void traverse_llist()
{
struct node *cur=head;
if(head==NULL)
printf("Linked List is empty");
else
{
printf("Roll nott Name n");
while(cur->link != head)
{
printf("%dtt%s n",cur->roll,cur->name);
cur=cur->link;
}
}
}
main()
{
int roll;
char name[20];
int l;
int choice;
do
{
printf("nn******** Various Operation on circular singly Linked List Data Structure********n");
printf("****Main Menu*****n");
printf("n Enter 1 : Add Node to circular singly Linked List (Start, End or Location)");
printf("nEnter 2 : Delete a Node to circular singly Linked List (Start, End or Location).");
printf("n Enter 3 : Traverse all Nodes in circular singly Linked List");
printf("n Enter Any other Key to Exit");
printf("nEnter Your Choice: __");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter 1: to insert at start/begning nn");
printf("Enter 2: to insert at end nn");
printf("Enter 3: to insert in between nodes nn");
scanf("%d",&choice);
switch(choice)
{
case 1:
// insert at start
printf("Enter a roll no to addn");
scanf("%d",&roll);
printf("Enter a name to addn");
scanf("%s",&name);
insertnode_start(roll,name);
break;
case 2:
// insert at end
printf("Enter a value to addn");
scanf("%d",&roll);
printf("Enter a name to addn");
scanf("%s",&name);
insertnode_end(roll,name);
break;
case 3:
//insert in between nodes
printf("Enter the location where you want to add itemn");
scanf("%d",&l);
printf("Enter roll no to addn");
scanf("%d",&roll);
printf("Enter a name to addn");
scanf("%s",&name);
insertnode_loc(l,roll,name);
break;
default:
printf("%d:invalid option. try again...n",choice);
}
break;
case 2:
printf("Enter 1: to delete at start/begning nn");
printf("Enter 2: to delete at end nn");
printf("Enter 3: to dele
te in between nodes nn");
scanf("%d",&choice);
switch(choice)
{
case 1:
// delete at start
deletenode_start();
break;
case 2:
// delete at end
deletenode_end();
break;
case 3:
//delete in between nodes
printf("Enter the location where you want to delete itemn");
scanf("%d",&l);
deletenode_loc(l);
break;
default:
printf("%d:invalid option. try again...n",choice);
}
break;
case 3:
traverse_llist();
break;
default:
exit(0);
}
} while(choice);
getch();
}