Posted on by Kalkicode
Code Circular Linked List

# 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:

1. The linked list is empty.
2. The node to be deleted is the head node.
3. The node to be deleted is in the middle.
4. 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):
print "Empty linked list"
return
prev = None

while True:
if temp.data == key:
if prev is None:
# Node to be deleted is the head
# Only one element in the list
else:
# Update the head and last node's next
temp = temp.next
else:
# Node to be deleted is not the head
prev.next = temp.next
temp = None
break
prev = temp
temp = temp.next
print "Given node is not exist"
break``````

## Algorithm Explanation

1. Check if the linked list is empty. If it is, print a message and return.
2. Initialize `temp` and `prev` pointers to traverse the list. `prev` will keep track of the previous node.
3. Traverse the list using the `temp` pointer until the node with the specified value (`key`) is found.
4. 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.
5. If `temp` is not the head, it means the node to be deleted is not the head. Update the `next` pointer of the previous node to bypass the node to be deleted.
6. Delete the node with the specified value.
7. If the element is not found, print a message.

## 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.

## Comment

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.

Categories
Relative Post