# Deletion in Circular Linked List One of the most crucial data structures to learn while preparing for interviews is the linked list. In a coding interview, having a thorough understanding of Linked Lists might be a major benefit.

A Circular Linked List is a list that has all the nodes connected to form a cycle, i.e., the last node points towards the head node to complete the loop of the cycle. There is no node pointing to the NULL, indicating the absence of any end node. ## Deleting a Node 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 operating the deletion on the Circular Linked List, the given node must not be present in the Circular Linked List.

Note: Linked list do not contain duplicate nodes (nodes having same values).

## How To Delete Node From Circular Linked List

Let’s try to understand the problem statement with the help of examples.

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 deletion of the node.
• If node with value X is not present in the given circular linked list, then we will have to simply print Given node is not present in the list and return the head node.
• If node with value X is present, we will delete it from the list and return the modified list.
• In this example, node with value X = 14 is present in the list, so we delete it and return the modified list. • Also, you must make sure that the modified list should still be a circular linked list after deletion i.e, all the nodes are still connected forming a cycle.

Taking another example, say, 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 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 will be simple to delete node from circular linked list:

• 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 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

There can persist the following cases for the deletion operation:

1. 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.
2. 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.
3. 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.

Let’s see the dry run of the above algorithm.

### Dry Run For Deletion In Circular Linked List  ## Code Implementation for Deletion in Circular Linked List

```#include
#include

/* structure for a node */
struct Node {
int data;
struct Node* next;
};

/* Function to insert a node at the beginning of
void push(struct Node** head_ref, int data)
{
struct Node* ptr1 = (struct Node*)malloc(sizeof(struct Node));
ptr1->data = data;

temp = temp->next;
temp->next = ptr1;
}
else
ptr1->next = ptr1; /*For the first node */

}

/* Function to print nodes in a given
{
do {
printf("%d ", temp->data);
temp = temp->next;
}

printf("\n");
}

/* Function to delete a given node from the list */
void deleteNode(struct Node* head, int key)
{
return;

// Find the required node
struct Node *curr = head, *prev;
while (curr->data != key)
{
{
" in the list!!!");
break;
}

prev = curr;
curr = curr->next;
}

// Check if node is only node
{
free(curr);
return;
}

// If more than one node, check if
// it is first node
{
prev = prev->next;
free(curr);
}

// check if node is last node
{
free(curr);
}
else
{
prev->next = curr->next;
free(curr);
}
}

/* Driver code */
int main()
{
/* Initialize lists as empty */

/* Created linked list will be 2->5->7->8->10 */

printf("List Before Deletion: ");

printf("List After Deletion: ");

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
{
// Create a new node and make head as next
// of it.
Node* ptr1 = new Node();
ptr1->data = data;

/* If linked list is not NULL then set the
next of last node */
{
// Find the node before head and update
// next of it.
temp = temp->next;
temp->next = ptr1;
}
else
ptr1->next = ptr1; /*For the first node */

}

/* Function to print nodes in a given
{
do {
cout << temp->data << " ";
temp = temp->next;
}

cout << endl;
}

/* Function to delete a given node from the list */
{

// If linked list is empty
return;

// If the list contains only a single node
{
return;
}

// If head is to be deleted
{

// Find the last node of the list
last=last->next;

// Point last node to the next of head i.e.
// the second node of the list
return;
}

// or the end of list is not reached
{
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 */

/* Created linked list will be 2->5->7->8->10 */

cout << "List Before Deletion: ";

cout << "List After Deletion: ";

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.

ptr1 = Node()
ptr1.data = data

temp = temp.next
temp.next = ptr1

else:
ptr1.next = ptr1

# This is the main function which will delete the node which have value equal to key

return

d = None

last = 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")

# Once we have successfully deleted the specified node, this function will be used to print the modified list.

while(True) :
print( temp.data, end = " ")
temp = temp.next
break
print()

print("List Before Deletion: ")

print( "List After Deletion: ")
```

#### Output

List Before Deletion: 9 6 7 4 3 8 5
List After Deletion: 9 6 4 3 8 5

Time Complexity To Delete Node From 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).

In this blog, we have explained to you how to delete node from Circular Linked List. Linked List is one of the most important topics for the placements. Deletion in circular linked list will help you to grab more about data structures and their advantages. 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 checkout Prepbytes (Linked List).

## FAQ Related to Deletion In Circular Linked List:

1. How do you delete a node in a circular linked list?
2. Traverse the list using curr to find the node to be deleted and before moving to curr to the next node, every time set prev = curr. If the node is found, check if it is the only node in the list. If yes, set head = NULL and free(curr). If the list has more than one node, check if it is the first node of the list.

3. What is Circular linked list?
4. The circular linked list is a linked list where all nodes are connected to form a circle. In a circular linked list, the first node and the last node are connected to each other which forms a circle. There is no NULL at the end.

5. What is underflow in the linked list?
6. Underflow is a condition that occurs when we try to delete a node from a linked list that is empty. This happens when START = NULL or when there are no more nodes to delete. Note that when we delete a node from a linked list, we actually have to free the memory occupied by that node.