Understanding deletion of the given node

Deleting the given node is identical to deleting the node with the given data. The only difference is that instead of seeking the node with the specified data value, we will search for the node that matches the given node. Let's examine the various scenarios we need to consider.

1. The list is empty

If the list is empty and contains no elements, we cannot find the given node because it does not exist within the list. Therefore, deleting the given node is not possible because there is no reference point within the list to perform the deletion. In this case, 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 given node 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 given node, 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.

Implementation

When implementing the logic to delete the given node, we consider all the possible cases and subcases and write the code for each in conditional blocks.

Complexity Analysis

The time complexity of deleting a given node depends on its position in the linked list. As the node must be located through traversal before removal, the number of operations varies based on where the node appears in the list.

Best case

The best case occurs when the given node is 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 node is 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 given node is the first node.

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

Worst Case - The given node is the last node.

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