Deleting from a Single Linked List

Note - The code examples used in this post are located at my GitHub account - Single Linked Lists

In the past couple of posts we've covered the process of searching and inserting items into a single linked list. Now we're onto the last of the three basic operations of a single linked list, deletion.

Because we cannot directly access items in a single linked list like we can with an array, deleting an item from a single linked list involves the following steps - 

1. Finding the node in the list containing the item we want to remove. (If it exists)
2. Find the predecessor of the node we want to remove such that it can be re-coupled to the successor of the node. 
3. Linking the predecessor node with the successor node of the node we wish to remove.

Step 2 is particularly important as without performing the step, we will end up with two lists. 

If we think of our linked list as a line of coupled train carriages, if we remove one, we'll need to re-couple the carriages on either side of the one we removed to connect the train together again, otherwise we'll have unconnected carriages that will go nowhere when the train departs.

An illustration of what we want to try to achieve with deletion is shown below - 

Figure 1 - Deleting the node "Dave" from our linked list. 

Note - The dotted lines represent the operation that we want to achieve, which in this instance is to connect nodes "Jerry" and "Stuart" together since we want to remove "Dave". 

From Figure 1, the general idea is to link the incoming (predecessor) arrow with the outgoing (successor) arrow for the node that we want to remove. 

Data Structure Representation:

For the deletion operation, there are no data structure modifications that need to be done to the Node object that we've been using. 

Deleting from a Single Linked List -

As mentioned above, the process to delete a node from a single linked list involves -

1. Finding our target node to remove. 
2. Finding our target nodes predecessor
3. Linking the predecessor nodes successor (nextNode) to our target nodes successor (nextNode). 

Finding the target node - 

Finding the node to remove is no different to what we've learnt previously when searching for an item in a linked list. The only difference here is that instead of returning a boolean condition for the existence of the node, we return the node itself. 

I won't go into the code changes required since its just a change of the returned data type, however they will be in the code examples provided. 

Finding the target nodes predecessor - 

To find the target nodes predecessor we need to make another pass through our list to check each nodes nextNode to see if it is our target node.

  

 /**
 * Find the predecessor node of a given node. 
 * 
 * @param targetNode - The target node.
 * @param currentNode - The current node.
 * @return The predecessor if found, null if empty
 */
 public static Node findPredecessor(Node targetNode, Node currentNode) {

    // If there is no current node, the list is empty.
    if (currentNode == null) {
 return null;
    }
    // Check if the successor is the target node.
    if (targetNode.equals(currentNode.getNext())) {
            return currentNode;
    }
    else {
          // Continue through the list to find the predecessor.
   return findPredecessor(targetNode, currentNode.getNext());
    }
}

Figure 2 - Finding the predecessor for a given node. 

To find the predecessor, we in essence perform another search. The difference here is that for each node that we encounter, instead of checking if the current node equals our target node, we need to check if the current nodes successor (nextNode) is equal to our target.

If it does, it means that we've found the predecessor. To refer to Figure 1, if our target node is "Dave" it means we've found its predecessor in "Jerry".

If our current nodes successor is not our target node, we must continue through our list.

Since the method is called recursively, our list size is reduced each time. If we encounter a situation where the list is null, it means our list is empty meaning that we don't have a predecessor. This should only ever be the case if we're at the head of our list.

Once we have found our predecessor, we'll have to connect it to the successor of our target node.

Connecting the predecessor to the successor

The last step in deleting a node from a single linked list is to connect the nodes either side of the target node together. 

By now, from the result of the previous two steps, we would have - 

1. The current node to remove.
2. A reference to the current nodes successor (nextNode)
3. A reference to the current nodes predecessor.

To perform this final step is nothing that we've not covered before. It is essentially a process of "inserting" the successor node as the predecessors nextNode.

 /**
 * Connect the predecessor and successor nodes together.
 *
 * The aim here is to connect the successor to the predecessors nextNode.
 * 
 * @param nodeToRemove - The node that we wish to remove.
 * @return - The modified list without the removed item.
 */
 public static Node connectPredecessorAndSuccessor(Node nodeToRemove, Node linkedList) {
    
    Node predecessor = findPredecessor(nodeToRemove, linkedList);
  
    // Predecessor can be null if the node to remove
    // is at the head of the list. In this case we need
    // to set the current nextNode to be the new head of
    // the list.
    if (predecessor == null) {
         linkedList = nodeToRemove.getNext();
    }
    else {
         // Otherwise we join the predecessor to the successor.
  predecessor.setNext(nodeToRemove.getNext());
    }
    return linkedList;
}

Figure 3 - Connecting the predecessor with the successor

Once the nodes have been connected, we would have a smaller but still linked list. It could be useful then to set the reference to the current node to be null to ensure it is cleaned up correctly. In other languages, there might be a specific need to deference to ensure that the removed node is removed from memory.

Complexity - 

The main issue with deleting an item from a single linked list is that we do not know about it's predecessor since a node only knows where to go next and not where it came from. Thus we're required at the very least to complete another pass to find it, therefore making the run time complexity as O(n).

The reason that it is O(n) and not O(n²) is that the search and predecessor methods are not nested operations. Both are O(n) functions, but are performed individually, meaning that the complexity is O(n) + O(n), which results in O(n) when we add the functions together .

Summary - 

The important thing to remember about deleting an item from a single linked list is to ensure that the list is still connected when the node has been removed. The concepts to apply to implement the removal are not so different to those that we had to use to implement both the insertion and deletion operations. 

To delete, all we need to do is to break down the task into the three required steps - 

1. Finding our target node to remove. 
2. Finding our target nodes predecessor (The previous node that lead to our target)
3. Linking the predecessor nodes successor (nextNode) to our target nodes successor (nextNode). 

By doing the three steps individually, we can simplify the problem to incrementally reach our goal of removing the node.

Exercises - 

1. Implement the methods to perform a removal of a node from a single linked list.


2. Run the code from DeleteNodeFromSingleLinkedList and experiment by adding and removing different items from the list and observe the program flow.