What is Circular Linked list ? - data structure tutorial

Prerequisites are that you must have basic knowledge of linked lists. If no, then press on the links below to learn about linked lists before reading this post on What is Circular Linked list ? - data structure tutorial.

A circular linked list is a linked list in which the last node points to the first node. A circular linked list can be a singly circular linked list or a doubly circular linked list.

We will be studying the singly circular linked list because the doubly circular linked list is not much used because it is expensive.

What is Circular Linked list ? - data structure tutorial

Advantages of Circular Linked Lists

We can traverse through any node and we can stop whenever the visited node is visited again.

We don't require two pointers for front and rear. We just need to maintain a pointer to the last inserted node and the front can always be obtained as next of the last node (What is Circular Linked list in Data Structures?).

Circular lists are useful in applications to repeatedly go around the list. For example, when multiple applications are running on a PC, it is common for the operating system to put the running applications on a list and then to cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application. It is convenient for the operating system to use a circular list so that when it reaches the end of the list it can cycle around to the front of the list.

Disadvantages of Circular linked list

The circular list is complex as compared to singly-linked lists.

Reversing of the circular list is complex as compared to singly or doubly lists.

Must be traversed carefully, else we could end up in an infinite loop.

Like singly and doubly lists circular linked lists also don’t support direct accessing of elements.

Basic Operations

The following are the important operations of a circular list.

· insert – To insert elements in the linked list.

· delete – To delete elements from a linked list.

· display – To displays the list (What is Circular Linked list in Data Structures?).

Insertion:

1. Insertion at Beginning: To insert a node at the beginning of the linked list.

1.  #include<stdio.h>  
2. #include<stdlib.h>  
3. void beg_insert(int);  
4. struct node  
5. {  
6.     int data;  
7.     struct node *next;  
8. };  
9. struct node *head;  
10. void main ()  
11. {  
12.     int choice,item;  
13.     do   
14.     {  
15.         printf("\nEnter the item which you want to insert?\n");  
16.         scanf("%d",&item);  
17.         beg_insert(item);  
18.         printf("\nPress 0 to insert more ?\n");  
19.         scanf("%d",&choice);  
20.     }while(choice == 0);  
21. }  
22. void beg_insert(int item)    
23. {    
24.         
25.     struct node *ptr = (struct node *)malloc(sizeof(struct node));    
26.     struct node *temp;  
27.     if(ptr == NULL)    
28.     {    
29.         printf("\nOVERFLOW");    
30.     }    
31.     else     
32.     {    
33.         ptr -> data = item;    
34.         if(head == NULL)    
35.         {    
36.             head = ptr;    
37.             ptr -> next = head;    
38.         }    
39.         else     
40.         {       
41.             temp = head;    
42.             while(temp->next != head)    
43.                 temp = temp->next;    
44.             ptr->next = head;     
45.             temp -> next = ptr;     
46.             head = ptr;    
47.         }     
48.     printf("\nNode Inserted\n");  
49.     }    
50.                 
51. }

2. Insertion at End: To insert a node at the end of the linked list.

1. void lastinsert(struct node*ptr, struct node *temp, int item)  
2. {  
3.     ptr = (struct node *)malloc(sizeof(struct node));  
4.     if(ptr == NULL)  
5.     {  
6.         printf("\nOVERFLOW\n");  
7.     }  
8.     else  
9.     {  
10.         ptr->data = item;  
11.         if(head == NULL)  
12.         {  
13.             head = ptr;  
14.             ptr -> next = head;    
15.         }  
16.         else  
17.         {  
18.             temp = head;  
19.             while(temp -> next != head)  
20.             {  
21.                 temp = temp -> next;  
22.             }  
23.             temp -> next = ptr;   
24.             ptr -> next = head;  
25.         }  
26.     }  
27.   
28. }

Deletion:

1. Deletion at Beginning: To delete a node at the beginning of the linked list.

1. #include<stdio.h>  
2. #include<stdlib.h>  
3. void create(int);  
4. void beg_delete();  
5. struct node  
6. {  
7.     int data;  
8.     struct node *next;  
9. };  
10. struct node *head;  
11. void main ()  
12. {  
13.     int choice,item;  
14.     do   
15.     {  
16.         printf("1.Append List\n2.Delete Node from beginning\n3.Exit\n4.Enter your choice?");  
17.         scanf("%d",&choice);  
18.         switch(choice)  
19.         {  
20.             case 1:  
21.             printf("\nEnter the item\n");  
22.             scanf("%d",&item);  
23.             create(item);  
24.             break;   
25.             case 2:  
26.             beg_delete();  
27.             break;   
28.             case 3:  
29.             exit(0);  
30.             break;    
31.             default:  
32.             printf("\nPlease Enter valid choice\n");  
33.         }  
34.                   
35.     }while(choice != 3);  
36. }  
37. void create(int item)    
38. {    
39.         
40.     struct node *ptr = (struct node *)malloc(sizeof(struct node));    
41.     struct node *temp;  
42.     if(ptr == NULL)    
43.     {    
44.         printf("\nOVERFLOW");    
45.     }    
46.     else     
47.     {    
48.         ptr -> data = item;    
49.         if(head == NULL)    
50.         {    
51.             head = ptr;    
52.             ptr -> next = head;    
53.         }    
54.         else     
55.         {       
56.             temp = head;    
57.             while(temp->next != head)    
58.                 temp = temp->next;    
59.             ptr->next = head;     
60.             temp -> next = ptr;     
61.             head = ptr;    
62.         }     
63.     printf("\nNode Inserted\n");  
64.     }    
65.                 
66. }   
67. void beg_delete()  
68. {  
69.     struct node *ptr;  
70.     if(head == NULL)  
71.     {  
72.         printf("\nUNDERFLOW\n");      
73.     }  
74.     else if(head->next == head)  
75.     {  
76.         head = NULL;  
77.         free(head);  
78.         printf("\nNode Deleted\n");   
79.     }  
80.       
81.     else  
82.     {     
83.         ptr = head;   
84.         while(ptr -> next != head)  
85.             ptr = ptr -> next;   
86.         ptr->next = head->next;  
87.         free(head);  
88.         head = ptr->next;  
89.         printf("\nNode Deleted\n");   
90.     }  
91. }

2. Deletion at End: To delete a node at the end of the linked list.

1. #include<stdio.h>  
2. #include<stdlib.h>  
3. void create(int);  
4. void last_delete();  
5. struct node  
6. {  
7.     int data;  
8.     struct node *next;  
9. };  
10. struct node *head;  
11. void main ()  
12. {  
13.     int choice,item;  
14.     do   
15.     {  
16.         printf("1.Append List\n2.Delete Node from end\n3.Exit\n4.Enter your choice?");  
17.         scanf("%d",&choice);  
18.         switch(choice)  
19.         {  
20.             case 1:  
21.             printf("\nEnter the item\n");  
22.             scanf("%d",&item);  
23.             create(item);  
24.             break;   
25.             case 2:  
26.             last_delete();  
27.             break;   
28.             case 3:  
29.             exit(0);  
30.             break;    
31.             default:  
32.             printf("\nPlease Enter valid choice\n");  
33.         }  
34.                   
35.     }while(choice != 3);  
36. }  
37. void create(int item)    
38. {    
39.         
40.     struct node *ptr = (struct node *)malloc(sizeof(struct node));    
41.     struct node *temp;  
42.     if(ptr == NULL)    
43.     {    
44.         printf("\nOVERFLOW\n");    
45.     }    
46.     else     
47.     {    
48.         ptr -> data = item;    
49.         if(head == NULL)    
50.         {    
51.             head = ptr;    
52.             ptr -> next = head;    
53.         }    
54.         else     
55.         {       
56.             temp = head;    
57.             while(temp->next != head)    
58.                 temp = temp->next;    
59.             ptr->next = head;     
60.             temp -> next = ptr;     
61.             head = ptr;    
62.         }     
63.     printf("\nNode Inserted\n");  
64.     }    
65.                 
66. }   
67. void last_delete()  
68. {  
69. struct node *ptr, *preptr;    
70.     if(head==NULL)  
71.     {  
72.         printf("\nUNDERFLOW\n");  
73.     }  
74.     else if (head ->next == head)  
75.     {  
76.         head = NULL;  
77.         free(head);  
78.         printf("\nNode Deleted\n");  
79.     }  
80.     else   
81.     {  
82.         ptr = head;  
83.         while(ptr ->next != head)  
84.         {  
85.             preptr=ptr;  
86.             ptr = ptr->next;  
87.         }  
88.         preptr->next = ptr -> next;  
89.         free(ptr);  
90.         printf("\nNode Deleted\n");  
91.     }  
92. }