Linked List is one of the most favorite topics that is asked by the interviewers. Having a thorough knowledge of the linked lists provides a candidate with a significant advantage. There are various variations of the linked lists. One such variation is known as a circular linked list. Here we will learn the process of deletion in the circular linked list. But before delving deep into the topic, let us first discuss what is meant by a circular linked list.
What is Circular Linked List?
A circular linked list is a type of list where every node is linked to form a cycle. This means that the last node points to the first node, forming a complete loop in the list. Unlike a regular linked list, no node points to NULL, indicating the end of the list.
The following image illustrates the difference between a normal linked list and a circular linked list.
Deletion in Circular Linked List
We are given a circular linked list and a node, and our task is to delete the node with a given value X from the given circular linked List i.e, After performing the deletion in circular linked list, the given node should not be present in the Circular Linked List.
Note: We are assuming that the given linked list does not contain duplicate nodes (nodes having the same values).
How To Perform Deletion in Circular Linked List?
Let’s try to understand the problem statement with the help of examples.
Example 1:
Let’s say if the given circular linked list is:
and X = 14.
 So now, according to the problem statement, we need to delete the node with value X from the given circular linked list. also linked list should maintain its property of being circular after the deletion of the node.
 If the node with value X is not present in the given circular linked list, then we will have to simply print the Given node is not present in the list and return the head node.
 If a node with value X is present, we will delete it from the list and return the modified list.
 In this example, the node with value X = 14 is present in the list, so we delete it and return the modified list.
Note: Also, you must make sure that the modified list should be a circular linked list after deletion i.e, all the nodes are still connected forming a cycle.
Example 2:
If the given circular linked list is:
and X = 7.
 So we can see that X = 7 is not present in the given linked list, so we will print Given node is not present in the list.
Now I think from the above examples, the problem is clear. So let’s see how we can approach it.
Before moving to the approach section, try to think about how you can approach this problem.
 If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.
Let’s move to the approach section.
Approach for Deletion In Circular Linked List
Our approach for performing the deletion on circular linked list will be simple and will have the following steps.

The idea is to traverse the given circular linked list and find the position of the node which we have to delete.

To do a traversal of the given circular linked list, we will create a new Node pointer curr, which will start from the head and traverse through each node in the list until it reaches the head again.
 If we reach head again without finding the key (the value of the node which we have to delete) then we will simply print “Given node is not present in the list” and return the original list.
 While traversing, we will also keep track of the previously visited node using a node pointer prev. The use of the prev pointer is that when we find the node we have to delete i.e, (curr == key), we can simply make prev.next point to the next of the curr node (prev.next = curr.next).

Thus, breaking the bond between the prev and curr. But one thing to notice here is that curr.next will still point to the next node in the list. So to break this bond we make curr.next point to NULL.
 In this way, we will successfully delete the node we were asked to delete in the problem.
Now let’s move to the algorithm section.
Algorithm For Deletion In Circular Linked List
The algorithm for deletion in circular linked list for the three different cases is given below.
 The List is empty.
 If the given list is empty, i.e., the head is assigned as NULL, then we will return NULL from the function.
 The given node is not present in the Circular Linked List.
 If we have completely traversed the list and are unable to find the given node to be deleted, we will simply print Given node is not present in the list and return the head node.
 We have found the node.
 So, in this case, we need to keep track of the node and its previous node and can perform the suitable operations from the following:
 If the list has only one node, then we will assign the head as NULL and return the head node.
 If the list has more than or equal to two nodes, we will perform the below operations:
 First, make curr pointer point to the node which we want to delete and prev pointer point to the previous node of curr.
 Now, we will make the prev pointer point to the next of curr pointer and assign the next of curr pointer as NULL.
 Then, if the curr pointer is the head node, we need to update the head node with the next of the head node.
 At last, we return the head representing the new Circular Linked List.
 So, in this case, we need to keep track of the node and its previous node and can perform the suitable operations from the following:
Dry Run for Deletion In Circular Linked List
The dry run for performing the deletion in circular linked list is given below for a better understanding.
Code Implementation of Deletion in Circular Linked List
The code for the deletion in circular linked list in C, C++, and Python are given below.
#include#include /* structure for a node */ struct Node { int data; struct Node* next; }; /* Function to insert a node at the beginning of a Circular linked list */ void push(struct Node** head_ref, int data) { struct Node* ptr1 = (struct Node*)malloc(sizeof(struct Node)); ptr1>data = data; ptr1>next = *head_ref; if (*head_ref != NULL) { struct Node* temp = *head_ref; while (temp>next != *head_ref) temp = temp>next; temp>next = ptr1; } else ptr1>next = ptr1; /*For the first node */ *head_ref = ptr1; } /* Function to print nodes in a given circular linked list */ void printList(struct Node* head) { struct Node* temp = head; if (head != NULL) { do { printf("%d ", temp>data); temp = temp>next; } while (temp != head); } printf("\n"); } /* Function to delete a given node from the list */ void deleteNode(struct Node* head, int key) { if (head == NULL) return; // Find the required node struct Node *curr = head, *prev; while (curr>data != key) { if (curr>next == head) { printf("\nGiven node is not found" " in the list!!!"); break; } prev = curr; curr = curr>next; } // Check if node is only node if (curr>next == head) { head = NULL; free(curr); return; } // If more than one node, check if // it is first node if (curr == head) { prev = head; while (prev>next != head) prev = prev>next; head = curr>next; prev>next = head; free(curr); } // check if node is last node else if (curr>next == head && curr == head) { prev>next = head; free(curr); } else { prev>next = curr>next; free(curr); } } /* Driver code */ int main() { /* Initialize lists as empty */ struct Node* head = NULL; /* Created linked list will be 2>5>7>8>10 */ push(&head, 2); push(&head, 5); push(&head, 7); push(&head, 8); push(&head, 10); printf("List Before Deletion: "); printList(head); deleteNode(head, 7); printf("List After Deletion: "); printList(head); return 0; }
#include <bits/stdc++.h> using namespace std; /* structure for a node */ class Node { public: int data; Node* next; }; /* Function to insert a node at the beginning of a Circular linked list */ void push(Node** head_ref, int data) { // Create a new node and make head as next // of it. Node* ptr1 = new Node(); ptr1>data = data; ptr1>next = *head_ref; /* If linked list is not NULL then set the next of last node */ if (*head_ref != NULL) { // Find the node before head and update // next of it. Node* temp = *head_ref; while (temp>next != *head_ref) temp = temp>next; temp>next = ptr1; } else ptr1>next = ptr1; /*For the first node */ *head_ref = ptr1; } /* Function to print nodes in a given circular linked list */ void printList(Node* head) { Node* temp = head; if (head != NULL) { do { cout << temp>data << " "; temp = temp>next; } while (temp != head); } cout << endl; } /* Function to delete a given node from the list */ void deleteNode(Node** head, int key) { // If linked list is empty if (*head == NULL) return; // If the list contains only a single node if((*head)>data==key && (*head)>next==*head) { free(*head); *head=NULL; return; } Node *last=*head,*d; // If head is to be deleted if((*head)>data==key) { // Find the last node of the list while(last>next!=*head) last=last>next; // Point last node to the next of head i.e. // the second node of the list last>next=(*head)>next; free(*head); *head=last>next; return; } // Either the node to be deleted is not found // or the end of list is not reached while(last>next!=*head&&last>next>data!=key) { last=last>next; } // If node to be deleted was found if(last>next>data==key) { d=last>next; last>next=d>next; free(d); } else cout<<"no such keyfound"; } /* Driver code */ int main() { /* Initialize lists as empty */ Node* head = NULL; /* Created linked list will be 2>5>7>8>10 */ push(&head, 2); push(&head, 5); push(&head, 7); push(&head, 8); push(&head, 10); cout << "List Before Deletion: "; printList(head); deleteNode(&head, 7); cout << "List After Deletion: "; printList(head); return 0; }
class Node: def __init__(self, next = None, data = None): self.next = next self.data = data # This function is used to insert a new node at the beginning of the circular linked list. def push(head_ref, data): ptr1 = Node() ptr1.data = data ptr1.next = head_ref if (head_ref != None) : temp = head_ref while (temp.next != head_ref): temp = temp.next temp.next = ptr1 else: ptr1.next = ptr1 head_ref = ptr1 return head_ref # This is the main function which will delete the node which have value equal to key def deleteNode( head, key) : if (head == None): return if((head).data == key and (head).next == head): head = None last = head d = None if((head).data == key) : while(last.next != head): last = last.next last.next = (head).next head = last.next while(last.next != head and last.next.data != key) : last = last.next if(last.next.data == key) : d = last.next last.next = d.next else: print("no such keyfound") return head # Once we have successfully deleted the specified node, this function will be used to print the modified list. def printList( head): temp = head if (head != None) : while(True) : print( temp.data, end = " ") temp = temp.next if (temp == head): break print() head = None head = push(head, 5) head = push(head, 8) head = push(head, 3) head = push(head, 4) head = push(head, 7) head = push(head, 6) head = push(head, 9) print("List Before Deletion: ") printList(head) head = deleteNode(head, 7) print( "List After Deletion: ") printList(head)
Output
List Before Deletion: 9 6 7 4 3 8 5
List After Deletion: 9 6 4 3 8 5
Time Complexity of Deletion in Circular Linked List: O(n), where n is the number of nodes in the circular linked list. Traversing the list takes a linear amount of time. Hence, the time complexity is O(n).
Space Complexity of Deletion in Circular Linked List: O(1), since we are not using any extra space for the deletion in circular linked list.
Conclusion
In this article, we provided a detailed explanation of how to perform deletion in circular linked list. As Linked List is a crucial topic for placements and interviews, understanding the deletion in circular linked list enhances one’s knowledge about data structures and their benefits. This is a basic problem and is good for strengthening your concepts in LinkedList and if you want to practice more such problems, you can check out Prepbytes (Linked List).
Frequently Asked Questions(FAQs)
Here are some frequently asked questions on deletion in circular linked list.
Ques 1. How is a Circular Linked List different from a regular Linked List?
Ans. A Circular Linked List is different from a regular Linked List in that the last node points to the first node to form a cycle, whereas in a regular Linked List, the last node points to NULL to indicate the end of the list.
Ques 2. What is the advantage of using a Circular Linked List?
Ans. The advantage of using a Circular Linked List is that it allows for efficient traversal of the list since there is no need to check for NULL when traversing the list.
Ques 3. Can a Circular Linked List have a NULL value as a node?
Ans. No, a Circular Linked List cannot have a NULL value as a node since the last node points to the first node to form a cycle.
Ques 4. What is the worstcase time complexity of searching for a node in a Circular Linked List?
Ans. The worstcase time complexity of searching for a node in a Circular Linked List is O(N).