Data Structures — Various deletions scenarios in a Linked List
The previous article Linked List, shows how to implement a basic linked list that has a head pointer. We also implemented the deletion of nodes at the head of the list with a constant-time complexity of O(1).
Since we had access to the front of the list, we can immediately delete any new node from the list using its head pointer. Imagine if you have to do the deletion in the following scenario.
- Delete at a specific position.
- Delete a specific node.
- Delete at the end of the list.
These are possible scenarios that you may need to implement into your basic linked list. Let’s look at each of these scenarios and their implementations.
Delete at a specific position.
The method to remove a node at a specific position would need a parameter with the value of the position as shown below.
Now to implement this method, there are a couple of scenarios to consider.
- The position value is less than 0
Just like an array, our position value here is a zero-based index. So if the value given is less than 0, we have to do nothing.
- The list is empty
In this case, we also have nothing to do on an empty list.
- The position to remove is equal to 0.
This means the user wants to remove the first item. This is similar to what we have implemented already in the previous article in the basic Linked List with a method Remove which removes the element in the head.
- The position value is more than the size of the list.
We need to consider this scenario so that we don’t hit any memory errors trying to access an element that is out of range. Since in our implementation we are not keeping track of the size of the list, we depend on our traversal to determine if have reached the end of the list.
Having considered all the above scenarios, here is our final implementation of the removal at a specific position method.
Delete a specific node
This is similar to deleting at a specific position, but instead of searching for the position to delete, we have to traverse the list to find a specific node with the reference value provided. Once we found the node with the value we are looking for, we can then delete the node at that position.
One important thing to note is we need 2 pointers when doing the traversal. One is to keep track of the current node we are looking for, and one to keep the track of the previous node. This is important because when we delete a node, we need to re-arrange the link from its previous node to its next node. Since we don’t have a pointer in the node that points backward, then it's best to keep tracking the previous node.
Another point to consider is when the node to delete is in the head, then it's best to reuse the Remove function in the base class since it handles the removal at the head.
Here is the implementation of delete a specific node.
Delete at the end of the list.
Deleting at the end of the list needs the same traversal of each node from the head node up until the last node in the list. To determine the last node, remember that the last node of the list has its next pointer that does not point to anything so its value is NULL.
The final implementation of deleting at the end of the list is as follows.
The full implementation of the linked list can be found in this Github repo:
