Sometimes when you are using a linked list structure, you may find yourself needing the "previous" node. However, when all you have at your fingertips is the "next" node in the list, completing this kind of operation can become a monstrously inefficient task to the order of O(n) time to complete. This is one of the drawbacks the singly linked lists present compared to arrays. But when faced with a situation where a linked list structure is your only option, doubly linked lists are able to swoop in and save the day.

Assumptions

Knowledge of <a href="https://www.devmaking.com/learn/data-structures/linked-list/" target="_blank" style="color:inherit;">Linked Lists</a>
Understanding of <a href="https://www.devmaking.com/learn/algorithms/big-o-notation/" target="_blank" style="color:inherit;">Big-O Notation</a>

What is a Doubly Linked List?

A Doubly Linked List is a linked list structure composed of nodes that contain references to the next and previous nodes, allowing for traversal in both directions, as opposed to singly linked lists which can only traverse in a forward direction.

The Doubly Linked Node

A doubly linked list node is similar a singly linked list node, containing an additional reference to the node that comes before itself.

 /* pseudo-code */
 class Node { // Doubly Linked Node
   int value;
   // References to the previous and next nodes of the list.
   Node previous;
   Node next;
 }

Before going forward, it should be noted that, while we are only adding one more pointer, we are also effectively doubling the amount of work that we as developers need to perform to make sure the references are also in check!

Conceptualizing Doubly Linked Lists

To help conceptualize doubly linked lists, we'll borrow a page out of the example given from the singly linked list discussion. Once again, we have a group of strangers in a single-file line, and each person has a piece of paper in their pocket with a number on it. Unlike last time, each person is able to talk to the next and previous person in line. Also unlike last time, we want to find what number the i<sup>th</sup> person in line has, given the size of the line and the ability to start at the beginning or end.

The goal: given the size of the line, find what number the i<sup>th</sup> person has in their pocket as fast as possible.

You may be curious what role the size of the line has in this; knowing the size of the list, we can cut in half the maximum number of people we need to ask. Given a line of size n, we can work out that if i > ( n / 2 ), starting at the back of the line and counting down to the i<sup>th</sup> will always make finding what number the i<sup>th</sup> person has faster.

Not all Doubly linked list implementations keep track of the size persistently, however this is one of the optimizations that allows us to take advantage of the directional traversal offered by doubly linked lists. In this example, being able to talk to the person in front and behind you, as well as starting from the beginning or end of the line displays the same properties of doubly linked lists. Additionally, the math used to find the i<sup>th</sup> person in the list efficiently is utilized in the implementation of the doubly linked list get function which you will see more of soon.

Doubly Linked List Searching

The act of searching a doubly linked list to see if a specific element exists is the same as with singly linked lists: starting at the head node, we traverse the list one-by-one until the value is found or there are no more nodes to look at. This operation is O(1) in it's best case and O(n) in it's worst case.

 /* pseudo-code */
 // We will call this the head now that we are also managing a tail node.
 Node head;

 function contains (int key){
   Node tmp = head;
   while ( tmp is not null ){
     if ( tmp.value equals key ){
       return true;
     }
     tmp = tmp.next;
   }
   return false;
 }

The Get Function

This was lightly touched on in the conceptualization, so let's dive in deeper. If we have a list of 100 elements and are looking for the value on the 99th element, it would make sense that we would want to check starting at the last element and not the first. Since we have control over which end of the list we start at, we can make it more efficient by splitting the list into a front half and a back half. That is where the statement if i > n / 2 comes into play. If it evaluates to true, we know to traverse backwards, otherwise it is faster to traverse forwards.

 /*pseudo-code*/
 // Head and Tail of the doubly linked list.
 Node head, tail;
 // Size of the doubly linked list.
 int size;

 function get (int index) {
   // Ensure the index is within limits.
     if(index &gt; size || isEmpty()) {
       throw an out of bounds error;
     }
     // Neat trick: worst case can be half the size of the list by storing size.
     if(index &gt; size / 2) {
       index = (size - 1) - index;
       Node tmp = tail;
       while(index &gt; 0) {
         tmp = tmp.prev;
         index = index - 1;
       }
       return tmp.value;
     }
     else {
       Node tmp = head;
       while(index &gt; 0) {
         tmp = tmp.next;
         index = index - 1;
       }
       return tmp.value;
     }
 }

> It is notable that while we are cutting in half the number of elements that we would need to traverse in a worst case ( n / 2 ), under Big-O rules, the get method would still classify it's worst case as O(n). That is why it is important to remember that Big-O is a generalization method to help us understand relative growth of functions, and not an exact number.

Doubly Linked List Insertion

Inserting elements into a doubly linked list follows the same logic pattern as singly linked list, with the twist of requiring some extra steps to link the previous nodes. Due to the added complexity that the additional previous reference introduces, correct implementation of these methods does require a solid understanding of the concepts at work. The method's that'll be covered are addFirst, addLast, addAfter, and addBefore.

Add First

If you are familiar with inserting into the beginning of a singly linked list, this method will look familiar with only an additional step required, which is linking the previous node of the head before reassigning the head of the list.

To review, adding to the front of a doubly linked list requires creating a new node, linking it's next pointer to the head of the list, linking the current head node's previous pointer to the new node, and finally setting the newly inserted node as the head of the list.

/* pseudo-code */
// Node references representing the front and the back of the doubly linked list.
Node head;
Node tail;
// Tracks the number of elements in the doubly linked list.
int size;

function addFirst(int value) {
    // The new node that will be inserted
    Node newNode = new Node(value);
    // Point the new nodes next pointer to the "old" head of the list.
    newNode.next = head;
    // Extra step compared to linked list addFirst
    head.previous = newNode;
    // Set the new node as the new head of the list.
    head = newNode;
    // Increment the size.
    size++;
}

> In implementation, we'll want to make sure that the head of the list is not null before assigning its previous pointer.

Here is a visual representation of addFirst:

Add Last

In a basic singly linked list where we only keep track of the head of the linked list, adding to the end of the list requires traversal of the entire structure, resulting in performance that is O(n). Doubly linked lists more often track the head and the tail. As a result, we do not need to traverse the entire list to insert a new element; we can insert at the end by adding a node after the tail pointer and setting that new node to be the new tail of the list, requiring only O(1) time to in implementation.

> As mentioned earlier, keep in mind that we need to take care of both the next and previous pointers to properly allow forwards and backwards traversal.

/* pseudo-code */
Node head;
Node tail;
int size;

function addLast(int value){
    Node newNode = new Node(value);
    // Set the next element in the list to the new node.
    tail.next = newNode;
    // Set the new node's previous pointer to the "old" end of the list.
    newNode.previous = tail;
    // Reference the new node as the end of the list.
    tail = newNode;
    // Increment the list size.
    size += 1;
}

Add After

Up to this point, the operations have been pretty standard, but with the insertion of intermediary nodes, things get a little more interesting. Adding after a node is at worst case O(n) as we have to iterate through the entire list, checking each element.

To insert a node after another in a doubly linked list, the list is iterated until a matching element is found. Once that happens, a new node is created who's next node is the matched element's next node, and it's previous node is the matched element. However we don't stop there; the two nodes that our new node points to still point to each other, and not the new node. To fix this, we can call upon the nodes in a manner like so:

 newNode.next.previous = newNode;
 newNode.previous.next = newNode;

> At first glance for those who are gaining familiarity with pointers/references, this may seem like we're just going to the next node and then back again, or vise versa in the latter case, and this might as well be two lines of useless code. What's happening is, we are first peering into the next node in the list, then changing that node's previous pointer to point to the new node. In the latter line, we're doing the same thing with the new node's previous node: peering into it and changing it's next pointer to the new node.

Let's implement this in some pseudo code to get a better picture:

 /* pseudo-code */
 Node head;
 Node tail;
 int size;

 function addAfter(int key, int value){
   // we have some base cases to tackle:
   if(size == 0){
     /*
       Depending on your implementation, 
       you might return, or add a node 
       */
   }
   // Make a node to traverse the list
   Node tmp = head;
   while(tmp != null) {
     // if we get a match, let's add a node after.
     If(tmp.value equals key){
       Node newNode = new Node(value);
       newNode.next = tmp.next;
       newNode.previous = tmp;

       tmp.next = newNode; // * (1)
       /* (1) is an equivalent operation to
           newNode.previous.next = newNode in this case.
         */

       // *(2) See analysis below.
       if(newNode.next is not null){
         newNode.next.previous = newNode;
       } else {
         tail = newNode; 
       }
       size++;
       return;
     }
     tmp = tmp.next;
   }
   /*
     Depending on your implementation, you might return,
     or add a node to the end of the list.
   */
 }

Before showing what this looks like visually, it is best to touch on the if block that we've noted with *(2). If we are inserting after a certain element, there is a chance that the element in question is the last element of the list. By checking if the next node is null, we can rule out whether or not this is the case. If not, we can safely go ahead and properly set the pointers.

In the case that we are inserting after the last element of the list, there is no backwards pointer to set in a next node. Additionally, we know that the node we are adding after is also the tail of the list, so upon inserting the new element, we need to adjust the pointer to keep our list in tact.

Now let's see what this looks like from a visual perspective:

Add Before

Inserting an element before another is one of the cases where the niceties of doubly linked lists start to show themselves. In singly linked lists, this operation required keeping track of two pointers. While the skill required to implement a doubly linked list addBefore function is on par with the singly linked list version, it is much more intuitive to reason. To perform this operation, the list will be iterated until a match is found, then using our previous pointers, we can make the insertion.

 /* pseudo-code*/
 Node head;
 Node tail;
 int size;

 function addBefore(int key, int value){
   // Base case covered first:
   If(size == 0){
     // Do something, or return.
   } 
   Node tmp = head;
   while( tmp is not null ){
     if( tmp.value equals key ) {
       Node newNode = new Node(value);
       newNode.next = tmp;
       newNode.previous = tmp.previous;

       tmp.previous = newNode;

       if( newNode.previous is not null ) {
         newNode.previous.next = newNode;
       }
       else {
         // * (1)
         head = tmp;
       }
       size++;
       return;
     }
   }
 }

> *(1) Just like with addAfter, if we are inserting before on the beginning of the list, we want to make sure that the head node pointer is correctly placed.

Doubly Linked List Deletion

If you are comfortable with the dynamics of adding an intermediary node, removing a node from a doubly linked list should feel like doing the steps in reverse. To remove a node, we scan until we find it's value, then make its two neighbor's point to each other instead of the node to be deleted. In a main case, that operation will look a little like this:

 node.previous.next = node.next;
 node.next.previous = node.previous;

Now all that is needed is to pad the operation with some boundary checks to ensure that the head and tail are accounted for, and we can safely remove a node from a doubly linked list!

 /* pseudo-code */
 Node head;
 Node tail;
 int size;

 function remove(int key) {
   if( size == 0 ){
     return;
   }
   Node tmp = head;
   while( tmp is not null ) {
     if( tmp.value equals key ) {
       /* (1) */
       if( tmp.previous is not null ) {
         tmp.previous.next = tmp.next;
       }
       else {
         head = tmp.next;
       }
       /* (2) */
       if( tmp.next is not null ) {
         tmp.next.previous = tmp.previous;
       }
       else {
         tail = tmp.previous;
       }
       size--;
       return;
     }
   }
 }

Some Analysis on the code:

Within the first if statement is our operation that changes the previous neighbor's pointer to point at the deleted node's next neighbor. If there is no previous node in the list, we must be at the head of the list, and therefore moving the head pointer forward to the next item in the list.
Now we want to carry out the operation that changes the previous neighbor of the next node to the deleted node's previous neighbor. Once again, if we do not have a next neighbor in the list, we must be at the end of the list, so instead we back up the tail pointer once over.

> It may appear that in the case where there is only one node in the list that the head and tail pointers "cross", but because they are both pointing to a null element, they point to the same place.

To Link Or Doubly Link

Here's the big question: if doubly linked lists are better for runtime than singly linked lists and come with the advantage of being able to be traversed in two directions, why aren't all linked lists doubly linked lists?

Performing some analysis on the properties of the two structures reveals the answers:

Performance

Singly Linked Lists:

Get / Delete / Insert: worst case is O(n), best case is O(1).
Getting a previous node in the list: O(n).

Doubly Linked Lists:

Get: worst case is O(n)*, best case is O(1).
Delete / Insert: worst case is O(n).
Getting a previous node in the list: O(1).

> * Although as discussed earlier, it will only ever need to look at n / 2 elements compared to singly linked lists.

Memory

Because Doubly Linked List nodes must maintain an additional previous pointer, they are not advisable for systems with a tight memory budget.

Complexity

Though it may not be something that is initially thought of when weighing the pros and cons of Data Structures, the complexity of implementation causes two potential issues for developers:

Code that is complex is often prone to containing defects. This is one of the reasons some prefer singly linked lists due to their less complex nature; they produce less bugs.
When working in teams, inevitably the code may be reviewed or changed as the requirements of the project change. Code that is complex to understand not only attributes to the first point reintroducing itself, but complex code also eats up another valuable resource: time. The developer reviewing the code must take more time to understand the current implementation in order to correctly extend or modify the code.

> While for some these points may be enough to stray away from using doubly linked lists on their project, it is useful to note that the relationship with complexity and bugs is prevalent throughout programs in general, and the level of complexity is relative to the skill of the developers and the simplicity of the compared data structure.

In a nutshell, we should utilize a doubly linked list over a singly linked list when memory is not an immediate concern, performance is at the forefront, and there is a confident developer behind the keyboard, and after reading this you very well may be!