Introduction
The Circular Linked List is one of the most important data structures to grasp when preparing for Coding Interviews.
A circular linked list is one in which all nodes are connected in a circle, with the last node pointing back to the head node to complete the cycle's loop. No nodes are pointing to the NULL, indicating that no end node exists.
We'll look at how to remove a specified node from a Circular Linked List in this article.
Problem Statement
We are given a circular linked list and a node, and our task is to delete the node with the given value X from the given Circular Linked List, i.e., the given node must not be present in the Circular Linked List after the deletion operation is completed. If no such key exists, the list will remain unaltered.
Also read - Merge sort in linked list
Sample Example
Example 1
Input : 1->3->7->5->9->4->(head node)
data = 3
Output :1->7->5->9->4->(head node)
Example 2
Input : 1->3->5->7->9->4->(head node)
data = 7
Output : 1->3->5->9->4->(head node)
Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm
Approach
We are performing deletion operations in the following cases:
- When the list is empty.
- When the list is not empty.
Algorithm
For the deletion operation, the following scenarios may persist:
-
The List is currently empty.
If the Circular list is empty, that is, the head is set to NULL, and the function will return NULL.
-
The node in question does not exist in the Circular Linked List.
We will simply print that the Specified node that is not present in the list and returns the head node if we have scanned the list entirely and are unable to locate the given node to be deleted.
-
We've located the node
So, in this scenario, we'll need to maintain track of the node and its predecessor, and we'll be able to do the following operations:
-
If the list only includes one node, the head will be set to NULL and the head node will be returned.
If there are more than two nodes in the list, we will do the following operations.
-
To begin, set the curr pointer to the node we want to delete, and the prev refers to curr's preceding node.
-
We'll now set the prev pointer to the next of the curr pointer and set the next of the curr pointer to NULL.
-
Then, if the curr pointer is the head node, the head node must be updated with the next head node.
- Finally, the head representing the new Circular Linked List is returned.

Implementation
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
/* Insert a node at the start of a circular linked list with this function. */
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 initial node */
*head_ref = ptr1;
}
/*Nodes in a circular linked list are printed using this function. */
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");
}
/*Deletes a specified node from the list. */
void deleteNode(struct Node* head, int key)
{
if (head == NULL)
return;
// Locate the necessary node.
struct Node *curr = head, *prev;
while (curr->data != key)
{
if (curr->next == head)
{
printf("\nGiven node is not found"
" in here!!!");
break;
}
prev = curr;
curr = curr->next;
}
// Check to see if the node is the only one.
if (curr->next == head)
{
head = NULL;
free(curr);
return;
}
// If there are more than one node, see if it's the first one.
if (curr == head)
{
prev = head;
while (prev->next != head)
prev = prev->next;
head = curr->next;
prev->next = head;
free(curr);
}
// if this one is last node
else if (curr->next == head && curr == head)
{
prev->next = head;
free(curr);
}
else
{
prev->next = curr->next;
free(curr);
}
}
/* Driver code for the main */
int main()
{
/* Initi lists as empty */
struct Node* head = NULL;
/* Created linked list will be */
push(&head, 9);
push(&head, 3);
push(&head, 7);
push(&head, 5);
push(&head, 6);
printf("Before Deletion: ");
printList(head);
deleteNode(head, 7);
printf("After Deletion: ");
printList(head);
return 0;
}
Output
Before Deletion: 6 5 7 3 9
After Deletion: 6 5 3 9
Complexities
- Time complexity: O(N), where n is the size of the circular linked list. The time it takes to traverse the list is linear. As a result, the complexity of time is O. (n).
- Auxiliary Space: O(1), The memory we consume is constant and independent of the data it is processing.