Understanding deletion after a given node
When deleting a node, we require access to the node one step before the node to be deleted to manipulate its next pointer. If we already have the previous node, the deletion process becomes straightforward. This is what makes this deletion operation the simplest of all delete operations. Let's examine all the cases 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. 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.
The list is empty
Algorithm
- Step 1: Return the original head node.
2. The given node is the last node
When the given node is the last node in the list, attempting to delete a node after it becomes an invalid operation. This is because, by definition, the last node has no successor, i.e., no node following it in the sequence. We can return the head because no other operation needs to be done.
The given node is the last node
Algorithm
- Step 1: Return the original head node.
3. The given node is not the last node
To delete a node after a given node, we can update the next pointer of the given node to skip over the node that needs to be deleted. Then, we can remove the node that we want to delete.
The given node is not the last node
Algorithm:
- Step 1: Create a temporary pointer to store the reference of the node after the `given` node.
- Step 2: Set the `next` pointer of the `given` node to hold the node's reference stored in the `next` pointer of the node after the `given` node.
- Step 3: Delete the node after the given node to free up memory.
- Step 4: Return the original head node.
Implementation
When implementing the logic for deleting a node after a given node operation, we consider all the possible cases and write the code for each in conditional blocks.
C++
Java
Typescript
Javascript
Python
It is important to emphasize the order of these assignment and deletion operations. We must ensure we do not access a node after it is deleted, so deletion should be the last step. An incorrect sequence of operations can lead to a program crash, and such errors are hard to debug.
Complexity Analysis
We need to make some pointer manipulations to delete the node. Therefore, the time complexity is constant. Similarly, we don't create any new nodes in all cases, so the space complexity is also constant, i.e., O(1).
Best Case
- Space Complexity - O(1)
- Time Complexity - O(1)
Worst Case
- Space Complexity - O(1)
- Time Complexity - O(1)