Inserting into a Doubly Linked List

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

Previously we covered the algorithm for recursively searching through a doubly linked list. It provided a detailed insight into how to traverse through a linked structure and to find and return items within it. 

Searching is an important functionality of a doubly linked list, however without any content to search for, it doesn't really do much. In this post, we'll cover the insertion algorithm so that we can start putting items into our doubly linked list and search for them. 



Hints: 

There are a couple of things to take note of about inserting an item into a linked list.

1. Insertion into a doubly linked list requires us to connect nodes together. This means that nodes are connected to each other through the next and previous pointer references. These pointers act as our guide ropes between all the nodes in the list. 


2. With linked structures, there is generally no need to worry about the order in which the data is stored, therefore we can make the insertion operation easier by adding the new node to the front of existing list. This avoids us having to keep a pointer to the tail of the list, or to always traverse it to insert into the end. 


3. Inserting at the head of a doubly linked list requires an update to the previous pointer reference of the current head node. In this instance we need to connect the previous of the current head to the new node and have the new nodes next as the current head.  


4. As with the search operation, it is important to keep a reference to the head of our linked list since it is our access point. 

Inserting into an empty list:

Figure 1 - Inserting node (Jerry) into an empty doubly linked list.

If we insert a node into an empty list, the node becomes the head of the list. This means that to access the rest of the list, we need to go through the node Jerry.

Inserting into a non empty list:

Figure 2 - Inserting node (Stuart) into a non empty list.

If we insert a node into a non-empty list, the new node becomes the head. Additionally, we need to update the previous pointer of the of Jerry to point back to Stuart and for Stuart's next to point to Jerry. This way we need the dual links together. 

Note - The dotted lines in the figures above, illustrate the insertion operation that is required to link the newly created node to either the head or the existing list.

Data Structure Representation:

The data structure to represent the node is the same as the one that we used in the search operation. 

Inserting into the head of a Doubly Linked List -

It does not really matter where we insert an item in a doubly linked list, so for this example, as with the single linked list, we'll insert the item at the head of the list. This means that each time we insert an item we need to ensure that -

1. If the list is not empty, the next pointer of our new node needs to point to the rest of the list. This will "link" our new node to the rest of the list. If we do not do this, then we have no way of accessing the rest of the list as we would have replaced the reference to the head with our new node. 


2. Our new node will become the head of the list, meaning that we need to ensure that the head reference is updated to point to our new node. For non-empty lists, point #1 needs to be done first, otherwise by overwriting the reference to head, we'll lose the only reference to the start location of the rest of the list. 


3. Because doubly linked lists have the additional predecessor pointer, when we insert the new node, we need to ensure that the predecessor pointer of the head node that we're replacing is updated to point back to our new node.

Since we're inserting an item to the front of the list, we won't need to loop through the list itself, therefore reducing the number of steps required in our algorithm to the following.

1. Create a new node object and initialise it with the new data.


2. Get current head of the list and set it to the next of our newly created node.


3. Get current head of the list and set its predecessor to point to our newly created node. 


4. Update the current head reference to our newly created node. 

If we implement the above steps in code, we'll produce the following insertion method - 

 /**
  * Public method to insert an item
  * into the doubly linked list.
  * @param name - The name of the item to
  * insert.
  */
  public void insertIntoList(String name) {
      insert(name);
  }
 
  /**
   * Method to insert an item into a doubly
   * linked list.
   * @param name - The name of the item to insert.
   */
   private void insert(String name) {
      Node newNode = new Node(name); // (1)
      // If the list is empty then we make the 
      // new node as the head.
      if (head == null) {
          head = newNode; // **
      }
      else {
   // Set the new node to point to the current head.
   newNode.next = head; // (2)
   // Set the current head to point back to the new node.
   head.previous = newNode; (3)
   // Set the new node as the head.
   head = newNode; (4)
      }
}

Figure 3 - Inserting an item into a doubly linked list.

The code in Figure 3 follows the algorithm (steps 1- 4) that we defined above. We create the node and insert it as the head of the list after we've updated the next and predecessor.

The one special case that we need to cover (step **) is when the list is empty. If we encounter this case, we can simply set the new node as the head of the list. Every insertion afterwards will follow the general insertion flow.

Complexity - 

The worst case time complexity to insert an item into the head of a doubly linked list is O(1) constant time. This is because we always have a reference to the head, and irrespective of the size of our list, it is always going to take the same amount of time to insert an item at the beginning.

Summary - 

Inserting an item into a doubly linked list is a fairly simple process. The important parts of the insertion method is to remember to update the next and predecessor pointers of the new node and head node before we set the new node as the head of the list. 

If we forget to do that we may lose the connections between the new node and the rest of the list, meaning that we lose access to those existing nodes.

Exercises - 

1. Implement an algorithm that inserts an item to the end of a doubly linked list in O(n) time. Improve the algorithm so that it can be inserted in O(1) constant time. (Hint - Keep a reference pointer to the tail of the list).