Deletion a node from Circular Linked List
In the problem of deleting a node from a circular linked list, we are working with a circular linked list data structure. The task is to remove a node with a specific value from the circular linked list while maintaining its circular nature.
Problem Statement
Given a circular linked list and a value (key), we need to find and delete the node that contains the given value. After the deletion, the circular structure of the linked list should be preserved.
Example
Consider a circular linked list with the following elements: 1 -> 2 -> 3 -> 4 -> 5 -> 6. If we want to delete the node with the value 4, the list becomes: 1 -> 2 -> 3 -> 5 -> 6.
Idea to Solve the Problem
To delete a node with a given value from a circular linked list, we need to consider several cases:
- The linked list is empty.
- The node to be deleted is the head node.
- The node to be deleted is in the middle.
- The node to be deleted is the last node.


We'll handle these cases to ensure that the circular structure is preserved after the deletion.
Pseudocode
Here's the pseudocode to delete a node with a given value from a circular linked list:
function deleteNode(circularLinkedList, key):
if circularLinkedList.head is NULL:
print "Empty linked list"
return
temp = circularLinkedList.head
prev = None
while True:
if temp.data == key:
if prev is None:
# Node to be deleted is the head
if temp.next is circularLinkedList.head:
# Only one element in the list
circularLinkedList.head = None
else:
# Update the head and last node's next
while temp.next is not circularLinkedList.head:
temp = temp.next
temp.next = circularLinkedList.head.next
circularLinkedList.head = circularLinkedList.head.next
else:
# Node to be deleted is not the head
prev.next = temp.next
temp = None
break
prev = temp
temp = temp.next
if temp == circularLinkedList.head:
# Element not found
print "Given node is not exist"
break
Algorithm Explanation
- Check if the linked list is empty. If it is, print a message and return.
- Initialize
temp
andprev
pointers to traverse the list.prev
will keep track of the previous node. - Traverse the list using the
temp
pointer until the node with the specified value (key
) is found. - If
temp
is pointing to the head, it means the node to be deleted is the head.- If the circular list contains only one element, set the head to
None
. - Otherwise, update the
next
pointers to remove the head node while preserving the circular structure.
- If the circular list contains only one element, set the head to
- If
temp
is not the head, it means the node to be deleted is not the head. Update thenext
pointer of the previous node to bypass the node to be deleted. - Delete the node with the specified value.
- If the element is not found, print a message.
-
1) Delete a node in circular linked list in java
2) Delete a node in circular linked list in c++
3) Delete a node in circular linked list in c
4) Delete a node in circular linked list in c#
5) Delete a node in circular linked list in php
6) Delete a node in circular linked list in python
7) Delete a node in circular linked list in ruby
8) Delete a node in circular linked list in scala
9) Delete a node in circular linked list in swift
10) Delete a node in circular linked list in kotlin
11) Delete a node in circular linked list in golang
12) Delete a node in circular linked list in vb.net
13) Delete a node in circular linked list in node js
14) Delete a node in circular linked list in typescript
Time Complexity
The time complexity of deleting a node from a circular linked list is O(n), where n is the number of nodes in the circular linked list. This is because in the worst case, we might have to traverse the entire list to find the node to be deleted. The space complexity is O(1) as we are using only a constant amount of extra space for pointers.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment