Circular Linked list using C Language

Linear linked list is a very useful data structure, but it has several shortcomings. With a modification in the linear linked list we can get another type of list, Circular linked list.In linear linked list the next address pointer of the last node points to NULL. If the same pointer is made to point the address of the first node of the list a different type of list will be generated which is known as circular linked list.

Such a list does not have any first or last node. So we have to establish a first node and last node in a circular linked list. One useful technique is to point the first node of the list by the external pointer. With the help of the external pointer we can access the nodes. Suppose p is the pointer which will traverse through the linked list and start is another pointer which is pointing the first node of the list. Since the list is circular we will not know when the complete list is traversed. So after every movement of the pointer p from one node to another test the condition p==start. Or we can use header node in circular linked list to identify the starting point. The header node can be identified by a special value in it’s information part.

The following program illustrates to create circular linked list with an external pointer pointing the first node while the other pointer will traverse through the linked list.

#include< stdio.h >

#include< stdlib.h >

struct list

{

int num;

struct list *next;

};

struct list *node;

void create(struct list *n)

{

char ch;

node=n;

printf("\nEnter value for the first node:-");

scanf("%d",&node->num);

fflush(stdin);

node->next=NULL;

printf("\nWant to create another node(y/n):-");

ch=getche();

fflush(stdin);

while(ch!='n')

{

fflush(stdin);

node->next=(struct list *)stdlib(sizeof(struct list));

node=node->next;

printf("\nEnter value:-");

scanf("%d",&node->num);

printf("\nAny more (y/n)");

ch=getche();

}

node->next=n;

}

void display(struct list *n)

{

node=n;

do

{

printf("%d\n",node->num);

node=node->next;

}while(node!=n);

}

void main()

{

struct list *start=(struct list *)stdlib(sizeof(struct list));

clrscr();

create(start);

printf("\nNow display the value of the circular lists:-\n");

display(start);

getch();

}

Now we will set a header node in a circular linked list.

The following program will create a circular linked list with a header node and new nodes can be inserted at any location or can be deleted from any location.

#include< stdio.h >

#include< stdlib.h >

#include< string.h>

struct list

{

char name[100];

struct list *next;

};

struct list *start;

void insert()

{

int c=1,count;

struct list *p,*node,*new1;

printf("\nin which location you want to insert:");

scanf("%d",&count);

node=start;

p=node->next;

new1=(struct list *)stdlib(sizeof(struct list));

printf("\Enter Name:-");

scanf("%s",&new1->name);

while(p)

{

if(c==count)

break;

node=node->next;

p=p->next;

c++;

}

node->next=new1;

new1->next=p;

}

void del()

{

int c=1,count;

struct list *p,*node;

printf("\nwhich location you want to delete:");

scanf("%d",&count);

node=start;

p=node->next;

while(p->next!=NULL)

{

if(c==count)

break;

node=node->next;

p=p->next;

c++;

}

node->next=p->next;

free(p);

}

void create(struct list *node)

{

char ch;

start=node;

printf("\nEnter value for the header node (****):-");

scanf("%s",&node->name);

fflush(stdin);

node->next=NULL;

printf("\nWant to create another node(y/n):-");

scanf("%c",&ch);

fflush(stdin);

while(ch!='n')

{

fflush(stdin);

node->next=(struct list *)stdlib(sizeof(struct list));

node=node->next;

printf("\Enter Name:-");

scanf("%s",&node->name);

fflush(stdin);

node->next=NULL;

printf("\Any more (y/n)");

scanf("%c",&ch);

}

node->next=start;

/*last node is connected with the header node */

}

void display(struct list *node)

{

int x=0;

node=node->next;

while(x==0)

{

printf("%s\n",node->name);

node=node->next;

if(strcmp(node->name,"****")==0)

x=1;

}

}

void main()

{

struct list *node=(struct list *)malloc(sizeof(struct list));

clrscr();

create(node);

printf("Now display the Names of the circular list:-\n");

display(node);

del();

printf("\nAfter deletion\n");

display(node);

insert();

printf("\nAfter insertion\n");

display(node);

getch();

}