Understanding deletion by given data

Deleting a node with the given data in a singly linked list can be implemented by piggybacking on the search operation. Instead of returning the data after finding it, we delete it in this operation. Let’s consider the possible cases when deleting a node with the given data.

1. The list is empty

When the list is empty, meaning it contains no elements, any attempt to delete a node is unnecessary because there are no nodes in the list. Since there is nothing to remove, the list remains unchanged. We can return the existing head, as the list is empty, and no node needs to be deleted.

Algorithm

• Step 1: Return the original head node.

2. The first node is deleted

If the data matches the first node, this case becomes the same as deleting the first node. We update the head to store the reference to the second node and delete the old head.

Algorithm

• Step 1: Create a temporary pointer to store the current head node.
• Step 2: Move the head pointer to the next node.
• Step 3: Delete the original head node to free up memory.
• Step 4: Return the new head node.

3. The node to be deleted is not the first node

To delete a node that is not the first node of the linked list, we need access to the node 1 step before the one to be deleted. We will traverse the list from the beginning while keeping track of the current and previous nodes. This way, when we reach the node with the given data, we will have access to its previous node, which we need to update. Deleting the given node involves a three-step process.

Algorithm

• Step 1: Traverse the list, keeping track of `current` and `previous` nodes until reaching the `given` node.
• Step 2: Set the `previous` node's `next` pointer to hold the node's reference stored in the `next` pointer of the `current` node.
• Step 3: Delete the `current` node to free up memory.
• Step 4: Return the original head node.

4. The node to be deleted could not be found

If the data provided does not match the data of any node in the linked list, then such a node does not exist in the list, so we return the existing head.

Algorithm

• Step 1: Traverse the list, keeping track of `current` and `previous` nodes until reaching the `given` node.
• Step 2: Return the original head node.

Implementation

When implementing the logic for deleting a node with a given data operation, we consider all the possible cases and write the code for each in conditional blocks.

Complexity Analysis

The time complexity of deleting a node with the given data depends on the position of the node in the linked list. Since the list must be traversed to locate the node containing the specified data, the number of operations varies based on where the node is found.

Best case

The best case occurs when the given data matches the first node. In this case, the function must delete the first node of the list. This process takes constant time, regardless of the linked list's size.

Worst case

On the other hand, the worst case occurs when the given data matches the last node. In this case, the function must delete the last node of the list. This process takes linear time proportional to the length of the linked list, i.e., O(N).

The function's space complexity is constant, as it only creates a few variables that take up a fixed amount of space regardless of the size of the linked list.

Best Case - The node with given data is the first node

• Space Complexity - O(1)
• Time Complexity - O(1)

Worst Case - The node with the given data is the last node

• Space Complexity - O(1)
• Time Complexity - O(N)