Discovering Data Structures and Algorithms – D-D-D-DOUBLY LINKED LISTS

In what would probably be my last post on the subject of linked lists, we’re going to be talking about doubly linked lists, which is a variant of the singly-linked lists.

Seeing double

Let’s refresh our memories as to what a singly linked list looks like:

Recall in my previous posts that a singly linked list goes one way. Each node object will point to the next node until there are no more nodes to point to. If one wants to traverse through a linked list, they’ll have to loop through each node, having a pointer point to the current node. The loop will break once the pointer is not truthy. At the end of an iteration of the loop, the code must have the current node pointer be set to the current nodes “next” value (also referred to node.next).

Now let’s look at a visual representation of a doubly linked list.

Notice the key difference between a singly linked list and a doubly linked list. Each node now has an extra value that points to its previous node on top of the value that points to the next node. Pretty neat.

Implementation

An implementation of a node object would look something like this:

class DoublyLinkedListNode {
    constructor(data) {
        this.data = data;
        this.next = null;
        this.previous = null;
    }
}

Traversal from beginning to end would be the same as it normally would with a singly linked list:

let current = head;

while (current !== null) {
    //your code
    current = current.next;
}

However, we now have a new little feature given our extra pointer to the previous node. We can traverse backward if we have a given node like so:

let current = tail;

while (current !== null) {
    // your code
    current = current.previous;
}

Adding data to a doubly-linked list is similar to adding data to a singly linked list as well. However, not only do we need to consider what the node.next values should be for the nodes that are affected, but we now have to think about that the node.prev values have to be. Take for instance we want to add a node in between two nodes. We would probably have to do something like the following:

insertAfter(previousNode, data): 
  
        // 1. check if the given previousNode is NULL 
        if(previousNode === null)
            console.log("This node doesn't exist") 
            
        // 2. create new node object and set its value to data value passed in
        newNode = DoublyLinkedListNode(data) 
  
        // 3. Make next of the newly created node as next of the passed in previous node
        newNode.next = previousNode.next
  
        // 4. Make the next of previousNode as the newly created node  
        previousNode.next = newNode 
  
        // 5. Make the previousNode as previous of the newNode 
        newNode.prev = previousNode 
  
        // 6. Have the newNodes nextNode's previous value set to the newly created Node
        if(newNode.next !== null) 
            newNode.next.prev = newNode 

Lots of reassigning values between nodes. The addition of the pointer to previous nodes adds an interesting wrinkle. On the one hand, now we have the ability to traverse backward as well as forward. Tracking previous nodes is now handled by the node itself. For singly-linked lists, we would need to set aside space for a pointer that would keep track of the previous nodes as we iterate through nodes to do insertions or deletions.

However, with the addition of a previous pointer within a doubly-linked list, we need to do some more maintaining of what nodes point to what. We need to do a few more operations to set node.prev accurately.

So not all is well in the world of more connections. Perhaps you do need to keep things simple when picking a data structure to use.

In any event, this will be the last post on linked lists as we move on to more data structures.