Circular Singly Linked List

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.

The following image shows a circular singly linked list.

Circular linked list are mostly used in task maintenance in operating systems. There are many examples where circular linked list are being used in computer science including browser surfing where a record of pages visited in the past by the user, is maintained in the form of circular linked lists and can be accessed again on clicking the previous button.

Memory Representation of circular linked list:

In the following image, memory representation of a circular linked list containing marks of a student in 4 subjects. However, the image shows a glimpse of how the circular list is being stored in the memory. The start or head of the list is pointing to the element with the index 1 and containing 13 marks in the data part and 4 in the next part. Which means that it is linked with the node that is being stored at 4th index of the list.

However, due to the fact that we are considering circular linked list in the memory therefore the last node of the list contains the address of the first node of the list.

We can also have more than one number of linked list in the memory with the different start pointers pointing to the different start nodes in the list. The last node is identified by its next part which contains the address of the start node of the list. We must be able to identify the last node of any linked list so that we can find out the number of iterations which need to be performed while traversing the list.

Operations on Circular Singly linked list:

Insertion

SN	Operation	Description
1	Insertion at beginning	Adding a node into circular singly linked list at the beginning.
2	Insertion at the end	Adding a node into circular singly linked list at the end.

Deletion & Traversing

SN	Operation	Description
1	Deletion at beginning	Removing the node from circular singly linked list at the beginning.
2	Deletion at the end	Removing the node from circular singly linked list at the end.
3	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.
4	Traversing	Visiting each element of the list at least once in order to perform some specific operation.

Menu-driven program in C implementing all operations

on circular singly linked list

1. #include<stdio.h>  
2. #include<stdlib.h>  
3. struct node   
4. {  
5.     int data;  
6.     struct node *next;   
7. };  
8. struct node *head;  
9.   
10. void beginsert ();   
11. void lastinsert ();  
12. void randominsert();  
13. void begin_delete();  
14. void last_delete();  
15. void random_delete();  
16. void display();  
17. void search();  
18. void main ()  
19. {  
20.     int choice =0;  
21.     while(choice != 7)   
22.     {  
23.         printf("\n*********Main Menu*********\n");  
24.         printf("\nChoose one option from the following list ...\n");  
25.         printf("\n===============================================\n");  
26.         printf("\n1.Insert in begining\n2.Insert at last\n3.Delete from Beginning\n4.Delete from last\n5.Search for an element\n6.Show\n7.Exit\n");  
27.         printf("\nEnter your choice?\n");         
28.         scanf("\n%d",&choice);  
29.         switch(choice)  
30.         {  
31.             case 1:  
32.             beginsert();      
33.             break;  
34.             case 2:  
35.             lastinsert();         
36.             break;  
37.             case 3:  
38.             begin_delete();       
39.             break;  
40.             case 4:  
41.             last_delete();        
42.             break;  
43.             case 5:  
44.             search();         
45.             break;  
46.             case 6:  
47.             display();        
48.             break;  
49.             case 7:  
50.             exit(0);  
51.             break;  
52.             default:  
53.             printf("Please enter valid choice..");  
54.         }  
55.     }  
56. }  
57. void beginsert()  
58. {  
59.     struct node *ptr,*temp;   
60.     int item;   
61.     ptr = (struct node *)malloc(sizeof(struct node));  
62.     if(ptr == NULL)  
63.     {  
64.         printf("\nOVERFLOW");  
65.     }  
66.     else   
67.     {  
68.         printf("\nEnter the node data?");  
69.         scanf("%d",&item);  
70.         ptr -> data = item;  
71.         if(head == NULL)  
72.         {  
73.             head = ptr;  
74.             ptr -> next = head;  
75.         }  
76.         else   
77.         {     
78.             temp = head;  
79.             while(temp->next != head)  
80.                 temp = temp->next;  
81.             ptr->next = head;   
82.             temp -> next = ptr;   
83.             head = ptr;  
84.         }   
85.         printf("\nnode inserted\n");  
86.     }  
87.               
88. }  
89. void lastinsert()  
90. {  
91.     struct node *ptr,*temp;   
92.     int item;  
93.     ptr = (struct node *)malloc(sizeof(struct node));  
94.     if(ptr == NULL)  
95.     {  
96.         printf("\nOVERFLOW\n");  
97.     }  
98.     else  
99.     {  
100.         printf("\nEnter Data?");  
101.         scanf("%d",&item);  
102.         ptr->data = item;  
103.         if(head == NULL)  
104.         {  
105.             head = ptr;  
106.             ptr -> next = head;    
107.         }  
108.         else  
109.         {  
110.             temp = head;  
111.             while(temp -> next != head)  
112.             {  
113.                 temp = temp -> next;  
114.             }  
115.             temp -> next = ptr;   
116.             ptr -> next = head;  
117.         }  
118.           
119.         printf("\nnode inserted\n");  
120.     }  
121.   
122. }  
123.   
124. void begin_delete()  
125. {  
126.     struct node *ptr;   
127.     if(head == NULL)  
128.     {  
129.         printf("\nUNDERFLOW");    
130.     }  
131.     else if(head->next == head)  
132.     {  
133.         head = NULL;  
134.         free(head);  
135.         printf("\nnode deleted\n");  
136.     }  
137.       
138.     else  
139.     {   ptr = head;   
140.         while(ptr -> next != head)  
141.             ptr = ptr -> next;   
142.         ptr->next = head->next;  
143.         free(head);  
144.         head = ptr->next;  
145.         printf("\nnode deleted\n");  
146.   
147.     }  
148. }  
149. void last_delete()  
150. {  
151.     struct node *ptr, *preptr;  
152.     if(head==NULL)  
153.     {  
154.         printf("\nUNDERFLOW");  
155.     }  
156.     else if (head ->next == head)  
157.     {  
158.         head = NULL;  
159.         free(head);  
160.         printf("\nnode deleted\n");  
161.   
162.     }  
163.     else   
164.     {  
165.         ptr = head;  
166.         while(ptr ->next != head)  
167.         {  
168.             preptr=ptr;  
169.             ptr = ptr->next;  
170.         }  
171.         preptr->next = ptr -> next;  
172.         free(ptr);  
173.         printf("\nnode deleted\n");  
174.   
175.     }  
176. }  
177.   
178. void search()  
179. {  
180.     struct node *ptr;  
181.     int item,i=0,flag=1;  
182.     ptr = head;   
183.     if(ptr == NULL)  
184.     {  
185.         printf("\nEmpty List\n");  
186.     }  
187.     else  
188.     {   
189.         printf("\nEnter item which you want to search?\n");   
190.         scanf("%d",&item);  
191.         if(head ->data == item)  
192.         {  
193.         printf("item found at location %d",i+1);  
194.         flag=0;  
195.         }  
196.         else   
197.         {  
198.         while (ptr->next != head)  
199.         {  
200.             if(ptr->data == item)  
201.             {  
202.                 printf("item found at location %d ",i+1);  
203.                 flag=0;  
204.                 break;  
205.             }   
206.             else  
207.             {  
208.                 flag=1;  
209.             }  
210.             i++;  
211.             ptr = ptr -> next;  
212.         }  
213.         }  
214.         if(flag != 0)  
215.         {  
216.             printf("Item not found\n");  
217.         }  
218.     }     
219.           
220. }  
221.   
222. void display()  
223. {  
224.     struct node *ptr;  
225.     ptr=head;  
226.     if(head == NULL)  
227.     {  
228.         printf("\nnothing to print");  
229.     }     
230.     else  
231.     {  
232.         printf("\n printing values ... \n");  
233.           
234.         while(ptr -> next != head)  
235.         {  
236.           
237.             printf("%d\n", ptr -> data);  
238.             ptr = ptr -> next;  
239.         }  
240.         printf("%d\n", ptr -> data);  
241.     }  
242.               
243. }  

Output:

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?
1

Enter the node data?10

node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?
2

Enter Data?20

node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?
2

Enter Data?30

node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?
3

node deleted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?
4

node deleted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?
5

Enter item which you want to search?
20
item found at location 1
*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?
6

 printing values ... 
20

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?
7