Objectives

By the end of this chapter, you should be able to:

• Compare singly linked lists, doubly linked lists, and arrays
• Diagram inserting and removing from a doubly linked list
• Compare run times of doubly linked lists and singly linked lists for the following operations: insert, remove, push, pop, find, access an element

Doubly Linked Lists

A doubly linked list is a type of linked list that has both a next reference and a previous reference for each node. This allows iteration in both directions: forward and backward. Typically a doubly linked list would also have a head reference and a tail reference.

Below is a conceptual diagram of a doubly linked list:

Doubly Linked List Advantages, Disadvantages, and Differences

Advantage - O(1), constant time push, pop operations. Since a linked list is not stored contiguously, each node only takes up one memory slot at a time. Therefore, doing operations like push are always constant time (assuming you have a reference to the last element in the list, or the tail) because the entire list does not need to be copied over. Only the pointer of the last node in the list needs to be updated.

Disadvantage - O(n) element access. A linked list is not stored contiguously and we only have a reference to the head (and possibly the tail) node. That means that finding an element at a specific index requires iterating through the list until that node is reached. This is a O(n) operation, but it is a constant time operation in an array.

This looks exactly like a singly linked list! So where is the difference? If we think about how elements are accessed in a singly linked list, if they are not at the beginning, we need to traverse through the entire list. This is not the case with doubly linked lists!

Since we have the ability to access a previous node in a doubly linked list, we can write a more efficient way to find nodes by either starting from the beginning or end and reduce the amount of traversing by half! The only tradeoff here is that a doubly linked list will consume more memory than a singly linked list because of the additional references to previous nodes.

Implementation in JavaScript

If you were to implement the list in JavaScript, a Node and DoublyLinkedList constructor function would be:

function Node(val) {
    this.val = val;
    this.next = null;
    this.prev = null;
}

Creating a small list using the Node constructor:

// Creating a doubly linked list with 1 element plus a head a tail reference
var head = new Node(30);
var tail = head;

// Adding -85
var newNode = new Node(-85);
tail.next = newNode;
newNode.prev = tail;
tail = newNode;

// Adding 10
newNode = new Node(10);
tail.next = newNode;
newNode.prev = tail;
tail = newNode;

Note that because we keep a reference to each node's previous node, pop is O(1) on doubly linked lists, while it is O(n) on singly linked lists. Finding a node by its index is also faster with a doubly linked list, since you can choose to traverse the list either from the front (for nodes in the first half) or from the back (for nodes in the second half). However, the complexity of finding a node by index is still O(n) - remember, big O notation doesn't care about constants, and cutting the runtime of a linear algorithm in half still results in a linear algorithm!

As with singly linked lists, the best way to understand doubly linked lists is to try to implement them. Let's do that next.