Understanding deletion before a given node

Deleting the node before the given node is similar to inserting before the given node. We need access to the node before the one that has to be deleted. Keeping this in mind, let's try to understand the different cases we must consider before coming up with a general solution.

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. Deleting the node after 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 given node is the first node

When the given node is the first node in the list, attempting to delete a node before it becomes an invalid operation. This is because, by definition, the first node has no predecessor, i.e., no node preceding it in the sequence. We can return the head because no other operation needs to be done.

Algorithm

• Step 1: Return the original head node.

3. The given node is the second node

This is a unique situation because removing the node before the second node essentially means deleting the linked list's head node. As learned earlier, this scenario is identical to deleting the first node. We need to update the head to store the reference to the second node and then 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.

4. The given node is any other node

To delete the node before a given node, we need to access the node two steps before the given node. We traverse the linked list while keeping track of the current, previous and previousToPrevious nodes. As soon as we reach the given node, we update the next pointer of the previousToPrevious node to hold the reference to the current node and then delete the previous node.

Algorithm

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

Implementation

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

Complexity Analysis

The time complexity of deleting a node before a given node depends on the position of the target node in the linked list. Since the list must be traversed to locate the node and its predecessor, the number of operations varies based on where the deletion occurs.

Best case

The best case occurs when the given node is the second node of the list. 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 second 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 second node in the list.

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

Worst Case - The given node is the last node in the list.

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