Circular Linked List

Circular Linked List

AU: Dec.-18, Marks 6

• Definition: The Circular Linked List (CLL) is similar to singly linked list except that the last node's next pointer points to first node.

• The circular linked list is as shown below -

• Various operations that can be performed on circular linked list are,

1. Creation of circular linked list.2. Insertion of a node in circular linked list.

3. Deletion of any node from linked list. 4. Display of circular linked list.

We will see each operation along with some example.

1. Creation of circular linked list

struct node *Create()

{

char ans;

int flag=1;

struct node *head,*New,*temp;

struct node *get_node();

clrscr();

do

{

New = get_node();

printf("\n\n\n\tEnter The Element\n");

scanf("%d", &New->data);

if(flag==1)/*flag for setting the starting node*/

{

head = New;

New->next=head; Creating a single node in linked list

flag=0;/*reset flag*/

}

Else /* find last node in list */

{

temp-head;

while (temp->next!= head)/*finding the last node */

temp-temp->next; /*temp is a last node */

temp->next=New;/* attaching the node*/

New->next-head; /*each time making the list circular*/

}

printf("\n Do you want to enter more nodes?");

ans=getch();

} while(ans =='y' || ans == 'Y');

return head;

}

/* function used while allocating memory for a node*/

struct node *get_node()

{

struct node *New;

New (node *) malloc(sizeof(struct node));

New->next = NULL;

return(New);/*created node is returned to calling function*/

}

Initially we will allocate memory for New node using a function get_node(). There is one variable flag whose purpose is to check whether first node is created or not. That means flag is 1 (set) then first node is not created. Therefore after creation of first node we have to reset the flag (making flag = 0).

Initially,

Here variable head indicates starting node.

Now as flag = 0, we can further create the nodes and attach them as follows.

When we have taken element '20'

If we want to insert 30 then

If we want to insert 40 then

Thus we can create a circular linked list by inserting one no one more element 50. It is as shown :

2. Display of circular linked list

void Display(struct node *head)

{

struct node *temp;

temp = head;

if(temp == NULL)

printf("\n Sorry,The List Is Empty\n");

else

{

do

{

printf("%d\t",temp->data);

temp = temp->next;

} while(temp != head);, The next node of last node is head node

}

getch();

}

3. Insertion of circular linked list

While inserting a node in the linked list, there are 3 cases -

a) Inserting a node as a head node

b) Inserting a node as a last node

c) Inserting a node at intermediate position

The functions for these cases is as given below -

struct node *insert_head(struct node *head)

{

struct node *get_node();

struct node *New,*temp;

New=get_node();

printf("\n Enter The element which you want to insert ");

scanf("%d",&New->data);

if(head == NULL)

head=New;

else

{

temp=head;

while(temp->next!=head)

temp=temp->next;

temp->next=New;

New->next = head;

head=New;

printf("\n The node is inserted!");

}

return head;

}

/*Insertion of node at last position*/

void insert_last(struct node *head)

{

struct node *New,*temp;

New=get_node();

printf("\n Enter The element which you want to insert ");

scanf("%d", &New->data);

if(head == NULL)

head= New;

else

{

temp=head;

while(temp->next!=head)

temp=temp->next;

temp->next=New;

New->next = head;

printf("\n The node is inserted!");

}

}

void insert_after(struct node *head)

{

int key;

struct node *New,*temp;

New= get_node();

printf("\n Enter The element which you want to insert ");

scanf("%d", &New->data);

if(head == NULL)

{

head=New;

}

else

{

printf("\n Enter The element after which you want to insert the node ");

scanf("%d", &key);

temp=head;

do

{

if(temp->data==key)

{

New->next-temp->next;

temp->next=New;

printf("\n The node is inserted"); D-ED-ED-ED

return;

}

else

temp-temp->next;

}while(templ=head);

}

}

Suppose linked list is already created as

If we want to insert a New node as a last node consider a linked list

If we want to insert an element 35 after node 30 then,

4. Deletion of any node

struct node *Delete(struct node *head)

{

int key;

struct node *temp, *temp1;

printf("\n Enter the element which is to be deleted");

scanf("%d", &key);

temp=head;

if(temp->data==key)/*If header node is to be deleted*/inil s botes svari sw seqque

{

temp1=temp->next; If a single node is present in the list and we want to delete it

if(temp1==temp)

{

temp=NULL;

head=temp;

printf("\n The node is deleted");

}

else

{

while(temp->next!=head)

temp-temp->next;/*searching for the last node*/

temp->next=temp1;

head=temp1;/*new head*/

printf("\n The node is deleted");

}

}

else

{

while(temp->next!=head) /* if intermediate node is to be deleted*/

{

if((temp->next)->data==key) The previous node of the node to be deleted is searched. temp1 is the node to be deleted

{

temp1=temp->next;

temp->next-temp1->next;

temp1->next=NULL;

free(temp1);

printf("\n The node is deleted");

}

else

temp-temp->next;

}

}

return head;

}

Suppose we have created a linked list as,  

If we want to delete temp → data i.e. node 10 then,

If we want to delete an intermediate node from a linked list which is given below

The linked list can be -

5. Searching a node from circular linked list

struct node *Search(node *head,int num)

{

struct node *temp;

temp=head;

while(temp->next!=head)

{

if(temp->data == num)

return temp; /*if node is found*/

else

temp=temp -> next

}

return NULL;

}

while searching a node from circular linked list we go on comparing the data field of each node starting from the head node. If the node containing desired data is found we return the address of that node to calling function.

 

Ex. 3.8.1: Implementation of circular linked list

/*********************************************************

Program To Perform The Various Operations On The Circular Linked List

*************************************************************/

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

struct node

{

int data;

struct node *next;

};

void main()

{

char ch;

int num,choice;

struct node *head, *New,*temp;

struct node *Create(void);

void Display(struct node *);

struct node *Insert(node *);

struct node *Delete(struct node *);

struct node *Search(struct node *,int);

head=NULL;

do

{

clrscr();

printf("\n Program For Circular Linked List\n");

printf(" 1.Insertion of any node\n\n");

printf(" 2. Display of Circular List\n\n");

printf(" 3. Insertion of a node in Circular List\n\n");

printf(" 4. Deletion of any node \n\n");

printf(" 5. Searching a Particular Element in The List\n\n");

printf(" 6.Exit");

printf("\n Enter Your Choice"); sino

scanf("%d", &choice);

switch(choice)

{

case 1 :head=Create();

break;

case 2 :Display(head);

break

case 3:head=Insert(head);

break;

case 4:head=Delete (head);

break;

case 5:printf("\n Enter The Element Which Is To Be Searched");

scanf("%d", &num);

temp Search(head,num);

if(temp!= NULL)

printf("\n The node is present");

else

printf("\n The node is not present");

break;

case 6:exit(0);

}

printf("\nDo you want to go to Main Menu?\n");

ch=getch();

} while(ch== 'y' || ch == 'Y');

}

struct node *Create()

{

char ans;

int flag=1;

struct node *head, *New, *temp;

struct node *get_node();

clrscr();

do

{

New = get_node();

printf("\n\n\n\tEnter The Element\n");

scanf("%d",&New->data);

if(flag==1) /*flag for setting the starting node*/

{

head =New;

New->next = head; /*the circular list of a single node*/

flag=0;/*reset flag*/

}

else /* find last node in list */

{

temp=head;

while (temp->next!= head)/*finding the last node*/)

temp=temp->next; /*temp is a last node*/

temp->next=New;

New->next-head; /*each time making the list circular*/

}

printf("\n Do you want to enter more nodes?");

ans=getch();

}while(ans=='y' || ans == 'Y');

return head;

}

struct node *get_node()

{

struct node *New;

New (node *) malloc(sizeof(struct node));

New->next = NULL;

return(New);/*created node is returned to calling function*/

}

void Display(struct node *head)

{

struct node *temp;

temp = head;

if(temp ==NULL)

printf("\n Sorry,The List Is Empty\n");

else

{

do

{

printf("%d\t",temp->data); boa pitiate ori prie rol ge*\_(==gs)

temp = temp->next;

} while(temp != head);/*Circular linked list*/

}

getch();

}

struct node *Insert(node *head)

{

int choice;

struct node *insert_head(node *);

void insert_after(struct node *);

void insert_last(struct node *);

printf("\n 1. Insert a node as a head node");

printf("\n 2. Insert a node as a last node");

printf("\n 3. Insert a node at intermediate position in the linked list");

printf("\n Enter your choice for insertion of node");

scanf("%d", &choice);

switch(choice)

{

case 1: head=insert_head(head);

break;

case 2: insert_last(head);

break;

case 3: insert_after(head);

break;

}

return head;

}

struct node *insert_head(struct node *head)

{

struct node *get_node();

struct node *New,*temp;

New=get_node();

printf("\n Enter The element which you want to insert ");

scanf("%d", &New->data);

if(head= NULL)

head=New;

else

{

temp=head;

while(temp->next!=head)

temp=temp->next;

temp->next=New;

New->next-head;

 head=New;

printf("\n The node is inserted!");

}

return head; }

/*Insertion of node at last position*/

 void insert_last(struct node *head)

{

struct node *New,*temp;

New=get_node();

printf("\n Enter The element which you want to insert ");

scanf("%d",&New->data);

if(head == NULL)

head=New;

else

{

temp=head;

while(temp->next!=head)

temp=temp->next;

temp->next=New;

New->next = head;

printf("\n The node is inserted!");

}

}

void insert_after(struct node *head)

{

int key;

struct node *New,*temp;

 New= get_node();

printf("\n Enter The element which you want to insert ");

scanf("%d",&New->data);

if(head == NULL)

{

head=New;

}

else

{

printf("\n Enter The element after which you want to insert the node");

scanf("%d", &key);

temp=head;

do

 {

if(temp->data==key)

{

New->next-temp->next;

temp->next=New;

printf("\n The node is inserted");

 return;

}

else

temp=temp->next;

}while(temp!=head);

}

}

struct node *Search(node *head,int num)

{

struct node *temp;

temp=head;

while(temp->next!=head)

 {

if(temp->data == num)

return temp;/*if node is found*/

else

temp-temp->next;

}

return NULL;

}

struct node *Delete(struct node *head)

{

int key;

struct node *temp, *temp1;

printf("\n Enter the element which is to be deleted");

 scanf("%d", &key);

temp=head;

if(temp->data==key)/*If header node is to be deleted*/

{

temp1=temp->next;

if(temp1==temp)

/*if single node is present in circular linked listand we want to delete it*/

{

temp=NULL;

head=temp;

printf("\n The node is deleted");

}

else /*otherwise*/

{

while(temp->next!=head)

temp=temp->next;/*searching for the last node*/

temp->next=temp1;

head=temp1;/*new head*/

printf("\n The node is deleted");

}

}

else

{

while(temp->next!=head) /* if intermediate node is to be deleted*/

{

if((temp->next)->data==key)

{

temp1=temp->next;

temp->next=temp1->next;

temp1->next = NULL;

free(temp1);

printf("\n The node is deleted");

}

else

temp-temp->next;

}

}

return head;

}

Output

Program For Circular Linked List

1. Insertion of any node

2. Display of Circular List

3. Insertion of a node in Circular List o

4. Deletion of any node

5. Searching a Particular Element in The List

6. Exit

Enter Your Choice 1

Enter The Element

10

Do you want to enter more nodes?

Enter The Element

20

Do you want to enter more nodes?

Enter The Element

30

Do you want to enter more nodes?

 Enter The Element

40

Do you want to enter more nodes?

Do you want to go to Main Menu?

Program For Circular Linked List

1. Insertion of any node

2. Display of Circular List

3. Insertion of a node in Circular List

4. Deletion of any node

5. Searching a Particular Element in The List

6. Exit

Enter Your Choice 2

10 20 30 40

 Do you want to go to Main Menu?

Program For Circular Linked List

1.Insertion of any node

2. Display of Circular List

3. Insertion of a node in Circular List

4. Deletion of any node

5. Searching a Particular Element in The List

6.Exit

Enter Your Choice 3

1. Insert a node as a head node

2. Insert a node as a last node

3. Insert a node at intermediate position in the linked list

Enter your choice for insertion of node 3

Enter The element which you want to insert 33

Enter The element after which you want to insert the node 30

The node is inserted

OF

Do you want to go to Main Menu?

Program For Circular Linked List

1. Insertion of any node

2. Display of Circular List

3. Insertion of a node in Circular List

4. Deletion of any node

5. Searching a Particular Element in The List

6. Exit

Enter Your Choice 2

10 20 30 33 40

Program For Circular Linked List

1. Insertion of any node

2. Display of Circular List

3. Insertion of a node in Circular List

4. Deletion of any node

5. Searching a Particular Element in The List

6. Exit

Enter Your Choice 4

Enter the element which is to be deleted 20

The node is deleted

Do you want to go to Main Menu?

Program For Circular Linked Lis

1. Insertion of any node

2. Display of Circular List

3. Insertion of a node in Circular List

4. Deletion of any node

5. Searching a Particular Element in The List

6. Exit

Enter Your Choice 2

10 30 33 40

Do you want to go to Main Menu?

Program For Circular Linked List

1. Insertion of any node

2. Display of Circular List

3. Insertion of a node in Circular Lister Icimonyloq orli gnithsesi

4. Deletion of any node

5. Searching a Particular Element in The List

 6. Exit

Enter Your Choice 5

Enter The Element Which Is To Be Searched 30

The node is present

Do you want to go to Main Menu?

Program For Circular Linked List

1. Insertion of any node

2. Display of Circular List

3. Insertion of a node in Circular List

4. Deletion of any node

5. Searching a Particular Element in The List

6. Exit

Enter Your Choice 5

Enter The Element Which Is To Be Searched 101

The node is not present

Do you want to go to Main Menu?

Program For Circular Linked List

1. Insertion of any node.

2. Display of Circular List

3. Insertion of a node in Circular List

4. Deletion of any node

5. Searching a Particular Element in The List

6. Exit

Enter Your Choice 6

Advantages of Circular Linked List over Singly Linked List

In circular linked list the next pointer of last node points to the head node. Hence we can move from last node to the head node of the list very efficiently. Hence accessing of any node is much faster than singly linked list.

Applications of circular list :

1) The circular list is used to create the linked lists in which the last node points to the first node.

2) In round robin method the circular linked list is used.

3) The circular linked list is used in solving Josephus problem.

4) For representing the polynomial the circular linked list.

Review Question

1. Write a procedure to deleting the last node from a circular linked list. AU: Dec.-18, Marks 6