In this article, you will learn about the implementation of Circular Linked List in C Programming.
What is Circular Linked List?
In a single linked list, all Node points to its next Node in the sequence and the last Node points NULL. But in a circular linked list, every Node points to its next Node in the series, but the previous Node points to the first Node in the list.
A circular linked list is a series of elements in which every piece has a link to its next element in the series, and the last element has a link to the first element.
That means the circular linked list is same to the single linked list excluding that the last Node shows to the first Node in the list.
Example –
Operations –
In a circular linked list, we can perform below operations…
Before we do actual operations, first, we need to set up an empty list. Primarily, perform the following steps before implementing existing functions.
Step 1 – comprise all the header files used in the program.
Step 2 – Declare all the user-defined functions.
Step 3 – determine a Node structure with 2 members’ data and next.
Step 4 – explain a Node pointer ‘head’ and set it to NULL.
Step 5 – Implement the primary method by displaying the operations menu and making suitable function calls in the immediate process to perform the user-selected operation.
Insertion in Circular Linked List –
In circular linked list, the insertion operation can be done in following 3 ways –
- Firstly, by inserting At Beginning of the list.
- Secondly, by inserting At End of the list.
- Finally, by inserting At Specific location in the list
Inserting at Beginning of the list
We can use the below steps to insert a new node at The circular linked list starts here…
Step 1: Create a newNode with the given value as the first step.
Step 2: Verify that the list is empty [head == NULL].
Step 3: Set head = newNode and newNode->next = head if it’s empty.
Step 4: Define a Node pointer ‘temp’ and initialize it with ‘head’ if it is not empty.
Step 5: Continue to move the ‘temp’ to the next Node until it reaches the last Node [‘temp-> next == head’].
keep ‘newNode next =head’, ‘head = newNode’, and ‘temp next = head’ in step 6.
Inserting at the End of the list
We can use the below steps to insert a new node at the End of the circular linked list…
Step 1 – Create a newNode with the given value.
Step 2 – verify whether list is Empty [head == NULL].
Step 3 – If it’s Empty then, set head = newNode and newNode → next = head.
Step 4 – If it’s Not Empty then, define a node pointer temp and initialize with head.
Step 5 – Keep moving the temp to its next Node till it comes to the last Node in the list [til temp → next == head].
Step 6 – keep temp → next = newNode and newNode → next = head.
Inserting at specific location in the list
We can use the following steps to insert a new node after a node in the circular linked list at a specific location in the list [after a node].
Step 1: Create a newNode with the given value as the first step.
Step 2: Verify that the list is empty [head == NULL].
Step 3 – If it’s empty, set newNode-> next = head and newNode-> head.
Step 4 – If it’s not empty, create a temp node pointer and initialise it with head.
Step 5 – Continue moving the temp to its next Node until it reaches the Node where we wish to place the newNode [until temp1 ->data equals location, where location is the node value].
Step 6 – Check whether the temperature has reached the final Node or not at regular intervals. If the function reaches the last Node, the message ‘Given Node is not there in the list!!! Insertion not possible!!!’ will be displayed, and the function will be terminated. If not, move the temperature to the next Node.
Step 7 – Check whether the temperature has reached the exact Node where we want to insert the newNode.the last Node [temp → next == head].
Step 8 – If suppose temp is last node then set temp → next = newNode and newNode → next = head.
Step 9 – If temp is’nt last node then set newNode → next = temp → next and temp → next = newNode.
Also Read – BFS algorithm explained in C Programming
Deletion in Circular Linked List –
In circular linked list, the deletion operation can be done in the following 3 ways:
- Firstly, by deleting from Beginning of the list
- Secondly, by deleting from End of the list
- Finally, by deleting a Specific Node
Deleting from Beginning of the list
We can use the following steps to delete a node from the Beginning of the circular linked list…
Step 1 – verify whether list is Empty [head == NULL]
Step 2 – If it’s Empty then, display ‘List is Empty!!! Deletion is ‘nt possible’ and terminate the function.
Step 3 – If it’s Not Empty then, define two Node pointers ‘temp1’ and ‘temp2’ and initialize both ‘temp1’ and ‘temp2’ with head.
Step 4 – verify whether list is having only one Node [temp1 → next == head]
Step 5 – If it’s TRUE then set head = NULL and delete temp1 [Setting Empty list conditions]
Step 6 – If it’s FALSE, go to the temp1 until it reaches to the last Node. [until temp1 → next == head ]
Step 7 – later set head = temp2 → next, temp1 → next = head and pop temp2.
Deleting from End of the list
We can use the below steps to delete a node from the End of the circular linked list…
Step 1 – verify whether list is Empty [head == NULL]
Step 2 – If it’s Empty then, display ‘List is Empty!!! Deletion is not possible’ and stop the function.
Step 3 – If it’s Not Empty then, define 2 Node pointers ‘temp1’ and ‘temp2’ and initialize ‘temp1’ with head.
Step 4 – verify whether list has only one Node [temp1 → next == head]
Step 5 – If it is TRUE. Then, set head = NULL and delete temp1. And stop from the function. [Setting Empty list condition]
Step 6 – If it’s FALSE. Then, set ‘temp2 = temp1 ‘ and go to temp1 to its next Node. loop the same until temp1 comes to the last Node in the list. [til temp1 → next == head]
Step 7 – keep temp2 → next = head and pop temp1.
Deleting a Specific Node from the list
We can use the below steps to delete a specific node from the circular linked list…
Step 1 – verify whether list is Empty [head == NULL]
Step 2 – If it’s Empty then, display ‘List is Empty!!! Deletion is not possible’ and stop the function.
Step 3 – If it’s Not Empty then, define 2 Node pointers ‘temp1’ and ‘temp2’ and initialize ‘temp1’ with head.
Step 4 – Keep going to the temp1 until it reaches to the exact Node to be deleted or to the last Node. And every time set ‘temp2 = temp1’ before going to the ‘temp1’ to its next Node.
Step 5 – If it’s reached to the last Node then display ‘Given Node is not found in the list! Deletion not possible!!!’. And stop the function.
Step 6 – Thus, if it’s reached to the exact Node which we wish to delete, then verify whether list is having only one Node [temp1 → next == head]
Step 7 – In case if the list has only 1 Node and that is the Node to be deleted later set head = NULL and pop temp1 [free[temp1]].
Step 8 – In case, the list consists multiple nodes then verify if temp1 is the first Node in the list [temp1 == head].
Step 9:
If the temp1 is the first Node later set temp2 = head and keep going to temp2 to its next Node till temp2 reaches to the last Node. so set head = head → next, temp2 → next = head and delete temp1.
Step 10 – Thus, if temp1 is not the first Node then check whether it is the last Node in the given list [temp1 → next == head].
Step 1 1– If the temp1 is last node so set temp2 → next = head and pop temp1 [free[temp1]].
Step 12 – If temp1 is’nt first node and not last node so set temp2 → next = temp1 → next and pop temp1 [free[temp1]].
Also Read – DFS algorithm explained in C Programming
Displaying a Circular Linked List in C Programming
We can use the below steps to display the elements of a circular linked list…
Step 1 – verify whether list is Empty [head == NULL]
Step 2 – If it’s Empty, then display ‘List is Empty!!!’ and stop the function.
Step 3 – If it’s Not Empty then, define a Node pointer ‘temp’ and initialize with head.
Step 4 – continue displaying temp → data with an arrow [—>] till temp reaches to the last Node
Step 5 – lastly display temp → data with an arrow pointing to head → data.
#include #include void insertAtBeginning[int]; void insertAtEnd[int]; void insertAtAfter[int,int]; void deleteBeginning[]; void deleteEnd[]; void deleteposition[int]; void display[]; struct Node { int data; struct Node *next; }*head = NULL; void main[] { int choice1, choice2, value, location; while[1] { printf["\n********** MENU ************\n"]; printf["1. Insert/push \n2. Delete\n3. Display\n4. Exit\ngive your choice: "]; scanf["%d",&choice1]; switch[] { case 1: printf["Enter value to be inserted: "]; scanf["%d",&value]; while[1] { printf["\nchoose from the given Inserting options\n"]; printf["1. At Beginning\n2. At End\n3. After a Node\n4. Cancel\nEnter your choice: "]; scanf["%d",&choice2]; switch[choice2] { case 1: insertAtBeginning[value]; break; case 2: insertAtEnd[value]; break; case 3: printf["Enter the location after which you wish to insert: "]; scanf["%d",&location]; insertAfter[value,location]; break; case 4: goto EndSwitch; default: printf["\nPlease choose correct Inserting option!!!\n"]; } } case 2: while[1] { printf["\nSelect from the given Deleting options\n"]; printf["1. At Beginning\n2. At End\n3. Specific Node\n4. Cancel\nEnter your choice: "]; scanf["%d",&choice2]; switch[choice2] { case 1: deleteBeginning[]; break; case 2: deleteEnd[]; break; case 3: printf["Enter the Node value that to be deleted: "]; scanf["%d",&location]; deleteSpecific[location]; break; case 4: goto EndSwitch; default: printf["\nPlease choose correct Deleting option!!!\n"]; } } EndSwitch: break; case 3: display[]; break; case 4: exit[0]; default: printf["\nPlease select correct option!!!"]; } } } void insertAtBeginning[int value] { struct Node *newNode; newNode = [struct Node*]malloc[sizeof[struct Node]]; newNode -> data = value; if[head == NULL] { head = newNode; newNode -> next = head; } else { struct Node *temp = head; while[temp -> next != head] temp = temp -> next; newNode -> next = head; head = newNode; temp -> next = head; } printf["\nInsertion success!!!"]; } void insertAtEnd[int value] { struct Node *newNode; newNode = [struct Node*]malloc[sizeof[struct Node]]; newNode -> data = value; if[head == NULL] { head = newNode; newNode -> next = head; } else { struct Node *temp = head; while[temp -> next != head] temp = temp -> next; temp -> next = newNode; newNode -> next = head; } printf["\nInsertion success!!!"]; } void insertAfter[int value, int location] { struct Node *newNode; newNode = [struct Node*]malloc[sizeof[struct Node]]; newNode -> data = value; if[head == NULL] { head = newNode; newNode -> next = head; } else { struct Node *temp = head; while[temp -> data != location] { if[temp -> next == head] { printf[" node is not found in the list!!!"]; goto EndFunction; } else { temp = temp -> next; } } newNode -> next = temp -> next; temp -> next = newNode; printf["\nInsertion success!!!"]; } EndFunction: } void deleteBeginning[] { if[head == NULL] printf["underflow!!! Deletion not possible!!!"]; else { struct Node *temp = head; if[temp -> next == head] { head = NULL; free[temp]; } else{ head = head -> next; free[temp]; } printf["\nDeletion successful!!!"]; } } void deleteEnd[] { if[head == NULL] printf["List is Empty!!! Deletion not possible!!!"]; else { struct Node *temp1 = head, temp2; if[temp1 -> next == head] { head = NULL; free[temp1]; } else { while[temp1 -> next != head]{ temp2 = temp1; temp1 = temp1 -> next; } temp2 -> next = head; free[temp1]; } printf["\n Pop successful!!!"]; } } void deleteSpecific[int delValue] { if[head == NULL] printf["List is Empty!!! Deletion not possible!!!"]; else { struct Node *temp1 = head, temp2; while[temp1 -> data != delValue] { if[temp1 -> next == head] { printf["\nGiven node is'nt found in the list!!!"]; goto FuctionEnd; } else { temp2 = temp1; temp1 = temp1 -> next; } } if[temp1 -> next == head]{ head = NULL; free[temp1]; } else{ if[temp1 == head] { temp2 = head; while[temp2 -> next != head] temp2 = temp2 -> next; head = head -> next; temp2 -> next = head; free[temp1]; } else { if[temp1 -> next == head] { temp2 -> next = head; } else { temp2 -> next = temp1 -> next; } free[temp1]; } } printf["\nDeletion success!!!"]; } FuctionEnd: } void display[] { if[head == NULL] printf["\nunderflow!!!"]; else { struct Node *temp = head; printf["\nthe elements of the list are: \n"]; while[temp -> next ! = head] { printf["%d ---> ",temp -> data]; } printf["%d ---> %d", temp -> data, head -> data]; } }
Truecaller Search Optimization using Trie
OUTPUT:
I hope that this article on the implementation of Circular Linked List in C Programming has been insightful for you! Happy Learning!