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

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.

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.