Deleting from a Doubly Linked List

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

In the past couple of posts we've covered the process of searching and inserting items into a doubly linked list. This post will cover the last of the three basic operations on doubly linked lists, deletion.

Since there is no way to directly access items in a doubly linked list like we can with an array, deleting an item involves the following steps. 

1. Search through the list to find the node we want to remove (if it exists). 
2. Connect the predecessor of the found node to the next of found node. 

Step 2 is important as if we do not complete this step then we would have two separate lists since we would have removed the connecting node.

If you've read the post on removing from a single linked list, the following analogy will sound similar. Imagine a doubly linked list as a line of coupled train carriages, if we remove a carriage, we'll need to re-couple the carriages on either side of the one we want to remove to keep the train connected. If we do not, then we'll have two sets of carriages. 

The analogy for single and doubly linked lists is the same, the only addition here is that we need to update the additional next pointer that our node contains. 

Figure 1 - Steps to delete a node (Jerry) from a doubly linked list.

The main body of work in the deletion of a node from a doubly linked list is to update the predecessor and next references to point to the nodes on either side of the one we want to remove. This step isn't as difficult as it would be for a single linked list since all nodes in a doubly linked list already contain the reference to the next and predecessor nodes.

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 Doubly Linked List -

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

1. Finding our target node to remove. 
2. Linking the predecessor nodes next to our target nodes next.
3. Linking the predecessor pointer of the target nodes next to the predecessor of the target node.

The steps might sound a little confusing so refer to Figure 1, to get an illustration.

Finding the target node - (Step 1)

Finding the node to remove is no different to what we've learnt previously when searching for an item in a doubly linked list. We're required to modify the search method slightly to return the node itself rather than the value as we have done previously. All this involves is to change the return type of the search method from String to Node. 

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. 

Linking the predecessor and next nodes together (Step 2 & 3)

Comparative to the explanation provided above, linking the nodes either side of the target node is relatively straight forward since we have all the pieces required.

Each node contains a reference to the node that came before it and the node that comes after it. All we need to do with the target node is to join them both together to finish the removal process.

To do that we just follow the steps 2 and 3 individually.

 
 /**
  * Public method to delete an item from
  * the doubly linked list.
  * @param name - The name of the item to 
  * remove.
  * @return true if removal was
  * successful, false otherwise.
  */
  public boolean deleteFromList(String name) {
     Node nodeToRemove = search(head, name); // (1)
     if (nodeToRemove == null) {
  return false; // No item of such name to remove.
     }
     else {
         if (nodeToRemove == head) { // (**)
         // Removing the head means to only assign
         // the head to the next since there is no 
         // predecessor.
         head = nodeToRemove.next;
     }
         else {
              Node predecessorNode = nodeToRemove.predecessor; 
              Node nextNode = nodeToRemove.next; 
              // Join the predecessor and next nodes together.
              predecessorNode.next = nextNode; // (2)
              nextNode.predecessor = predecessorNode; // (3)
         }
         return true;
     }
}

Figure 2 - Steps to delete a node from a doubly linked list.

To step through the code we perform the steps outlined by the algorithm in numbered order (1), (2) and (3).

Steps 2 and 3 are the process of joining the nodes either side of the one we want to remove together. From Figure 1, we remove Jerry, this means that we need to connect Stuart and Dave together so we connect Stuart's next with Dave and Dave's predecessor with Stuart. 

Doing so removes the relationship that Jerry had with the two of them, meaning that he's been removed from the list and the list still maintains its linked state.

Complexity - 

The linking of the predecessor and next nodes takes O(1) constant time, however we're still required to search for the item that we want to remove, which from our analysis of searching a linked structure takes O(n) worst case time since we have no idea where in the list our item is. 

A doubly linked list at least saves us the process of having to search through the list twice, once to find the node to remove and another to find its predecessor since the node maintains a reference to it.

It does however cost us the additional space required to maintain the predecessor pointer compared to a single linked list.

Summary - 

The main thing to remember when performing any of the operations on doubly linked lists is to always remember where the predecessor and next pointers of a node are pointing to. 

These connections are the main lifeline of the linked structure, without them the list cannot be maintained correctly. 

The deletion operation on a doubly linked list is where we can see the main benefit of having an additional pointer to the predecessor when compared to a single linked list. Because each node knows where its come from and where its going to, we don't need to perform an additional search to know where to maintain the connections if we want to delete. 

Its a two step process to remove from a doubly linked list - 

Search through the list to find the node we want to remove (if it exists). 

Connect the predecessor of the found node to the next of found node. 

Exercises - 

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