Doubly Linked Lists (Searching)

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

A doubly linked list is another example of a linked structure. As with single linked lists, it also comprises of a group of nodes connected together in a chain to form the list. 

The nodes in a doubly linked list contain the following properties -

1. The data field(s) - each node can contain any number of data fields.
2. Pointer to next - each node contains a pointer to the successor node in the list.
3. Pointer to previous - each node contains a pointer to its predecessor node in the list. 

The doubly linked list gets its name from the number of pointers that each node has. With the two pointers, each node knows about both its successor and predecessor.

Figure 1 - Doubly Linked List Structure.

Figure 1 illustrates the doubly linked list structure from left to right. The entry point into the list structure is from the head and progresses to the tail with the node denoted as "Dave". The directional arrows indicate where the two pointers in each node point to, which are the the predecessor and successor nodes. 

Because of the bi-directional relationships in for each node, it means that "Sue" knows both "John" and "Dave". 

Data Structure Representation 

The data structure representation of a doubly linked list is an extension to the generalised node structure that we described in the Linked Structures and Pointers introduction, the difference here is that we're adding an additional pointer to the previous node in the list.

/**
* The Node class.
* 
* This class is represents the nodes in a
* doubly linked list.
*
*/
private class Node {
  
 /**
  * The data that the node contains.
  */
  public String name;
  
 /**
  * A reference to the successor node.
  */
  public Node next;
  
 /**
  * A reference to the predecessor node.
  */
  public Node previous;
  
 /**
  * Constructor to initialise a new node.
  * @param nameTmp - The name value for the node.
  */
  public Node(String nameTmp) {
      this.name = nameTmp;
      this.next = null;
      this.previous = null;
  }

Figure 2 - Doubly linked list node represented in code.

Doubly Linked List Operations - 

As with other linked structures, a doubly linked list also has the same three basic operations, searching, inserting and deleting. The algorithm required to perform those operations are very similar to that of other linked structures and in the case of deleting can actually be more efficient which we'll explain in a future post.

For now we'll focus on describing the algorithm for searching through a doubly linked list.

Searching a Doubly Linked List - 

The algorithm for searching through a linked structure is a common element found in both the inserting and deleting operations. If we wish to insert into a particular location in the list, we're required to search for the correct location to insert, and if we wish to delete then we also need to search for the correct item to remove. 

The reason that we're required to do this is because we do not have direct access to the node elements in a list like we would in an array. Because linked structures are not housed in contiguous memory locations, we're required to navigate from the head of the list through n number of nodes until we've found the item that we want. 

Figure 3 - Searching a doubly linked list requires jumping through each node.

The algorithm for searching through a doubly linked list can be done both iteratively and recursively, with both methods sharing the same steps as defined below

1. Set the head node as the current node.
2. If the list is empty, return null indicating the item does not exist in the list, otherwise continue. 
3. If the current node contains the item we're looking for, then return the item. 
4. Otherwise, go to the next node and repeat step 2. 

If we follow the above algorithm, we'll reach one of two conclusions, either we find the item in the list and we return it, or we return null or an equivalent value indicating that the item we wish to find is not in the list. 

Recursively Searching a Doubly Linked List - 

The idea behind recursion is to reduce the input size upon each call to the recursive method until we either reach the result we expect or we reach the base case and return the result. 

In the context of searching, each call to the recursive method acts as step 4 in our algorithm defined above. The idea is to call the search method again but with the next node as the method argument, thus reducing the overall list size by one each time the method is called. If we continue to do this, the list size will either reduce to zero indicating the item is not in our list or we find the item we're looking for and we return the value. 

The following code implements the algorithm outlined above for searching a doubly linked list. 

 
 /**
  * Public method to search for an
  * item in the doubly linked list.
  * @param name - The item we're looking for.
  * @return The found node, or null otherwise.
  */
  public Node searchList(String name) {
      return search(head, name);
  }
 
 /**
  * Method to search a doubly linked list.
  * @param currentNode - The current node being inspected.
  * @param name - The item we're looking for.
  * @return The found node, or null if not found.
  */
  private Node search(Node currentNode, String name) {
      if (currentNode == null) {
   return null; // The list is empty.
      }
      if (currentNode.name.equals(name)) {
   return currentNode; // Item is found.
      }
      else {
   // Continue searching the list.
   return search(currentNode.next, name);
      }
}

Figure 4 - Searching a doubly linked list recursively.

The main part here to take note of is the search method where we check the current node against the steps that we have defined above. 

Each time we call the search method we advance it along by passing in the next node as the method argument. This ensures that the next time the method is called, it is the next node that will be inspected and not the same one. We don't need to worry if we're passing in null since the recursive method checks this for us and if we do encounter a null node, it means that we've reached the end of the list and we return.

Complexity - 

The worst case time complexity to search a doubly linked list is O(n) where n is the number of nodes in our list. The nature of linked structures prevent us from directly accessing each node and the only way into the list is through the head node. This means that all search operations are required to go through the same nodes from start to end.

Without knowing the order of the nodes, the worst case time complexity of O(n) is achieved if the item is not present in the list. In this situation we're required to search through the entire list, head to tail to check for the location of the item. 

Whilst it is possible to search from tail to head in a doubly linked list, it does not improve the worst case time complexity. 

Summary - 

Searching through a doubly linked list is the same as searching through a singly linked list. The addition of the extra pointer to a nodes predecessor in a doubly linked list does not yield any benefits when it comes to searching. 

Notes to take away are - 

1. Searching a linked list is recursive, each call of the search method allows reduces the list size by one, leaving a smaller list to perform the search actions upon.
2. The head of a doubly linked list is the access point to the rest of the nodes in the list.
3. A doubly linked list has the added bonus of a predecessor node that allows us to query both the entry and exit points of our current node. From this, if we kept a reference to the tail of the list, we could possibly perform a reverse search.

Exercises - 

1. Implement an algorithm that allows us to perform a search by using the tail of a doubly linked list rather than the head.