Singly vs. Doubly Linked Lists

This blog briefly compares Singly Linked Lists and Doubly Linked Lists in JavaScript.

What Are Lists?

Lists are a data structure used to keep order of an object. Unlike an array, a list is not an actual data type in JavaScript and does not give its items an index. Instead, lists are created from Objects and use nodes to point to the previous or next node to keep order, depending on the list type.

Singly Linked Lists

To create a singly linked list, first create a class to represent a node, or the items you are collecting in the list. This class represents the blueprint for each item to be added to the list.

In the below example, I am using Color to act as the node class. Each color will have a name and a .next property to reference the next color in the list. The .next property will default to null when the color is created.

class Color {
    constructor(name){
        this.name = name;
        this.next = null;
    }
}

While we could use this Color class to create new colors, we'll let our list take care of that in the next example.

The Rainbow class is used to maintain our ordered list. The push method is defined inside the class and is used to create and add items at the end of the list.

class Rainbow {
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(name){
        let newColor = new Color(name);
        if(this.length === 0) {
            this.head = newColor;
            this.tail = this.head;
        } else {
            this.tail.next = newColor;
            this.tail = newColor;
        }
        this.length++;
        return this;
    }

let list = new Rainbow()
list.push("Red")
list.push("Orange")
list.push("Yellow")

console.log(list)
// Rainbow {
//     head: Color { name: 'Red', next: Color { name: 'Orange', next: [Color] } },
//     tail: Color { name: 'Yellow', next: null },
//     length: 3
//   }

Note that Singly Linked Lists only flow one way - from the head (Red) to the tail (Yellow).

This can become an issue if you care about time when trying to access the last item in a Singly Linked List, as you must iterate through each item to find the .next item until you reach the last value. For small lists this may not be a problem, but the larger the list grows, the more time it takes to iterate to the last item, giving a Big O of linear time (O(n)).

class Rainbow {

    ...

    get(index){ 
        if(index < 0 || index >= this.length) return null;
        let counter = 0;
        let color = this.head;
        while (counter !== index) {
            color = color.next;
            counter++;
        }
        return color;
    }
}

list.get(1) // this is index of 1, so the 2nd item, Orange
// Color { name: 'Orange', next: Color { name: 'Yellow', next: null } }

Doubly Linked Lists

Doubly Linked Lists are almost identical to a Singly Linked Lists, however they have an additional property called prev that represents the previous item in the list. This gives us access to move either forward or backwards through the list.

class Color {
    constructor(name){
        this.name = name;
        this.next = null;
        this.prev = null;
    }
}

class Rainbow {
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(name){
        let newColor = new Color(name);
        if(this.length === 0) {
            this.head = newColor;
            this.tail= newColor;
        } else {
            this.tail.next = newColor;
            newColor.prev = this.tail;
            this.tail = newColor;
        }
        this.length++;
        return this;
    }
    get(index){
        if(index < 0 || index >= this.length) return null;
        let count, color;
        if (index <= this.length/2){
            count = 0
            color = this.head;
            while (count != index){
                color = color.next;
                count++;
            }
            console.log("Moved Forward")
        } else {
            count = this.length - 1;
            color = this.tail;
            while (count != index){
                color = color.prev;
                count--;
            }
            console.log("Moved Backward")
        }
        return color;
    }
}

let list = new Rainbow()
list.push("Red")
list.push("Orange")
list.push("Yellow")

console.log(list)
// Rainbow {
//     head: <ref *1> Color {
//       name: 'Red',
//       next: Color { name: 'Orange', next: [Color], prev: [Circular *1] },
//       prev: null
//     },
//     tail: <ref *2> Color {
//       name: 'Yellow',
//       next: null,
//       prev: Color { name: 'Orange', next: [Circular *2], prev: [Color] }
//     },
//     length: 3
//   }

list.get(0)
// "Moved Forward"
// <ref *2> Color {
//   name: 'Red',
//   next: <ref *1> Color {
//     name: 'Orange',
//     next: Color { name: 'Yellow', next: null, prev: [Circular *1] },
//     prev: [Circular *2]
//   },
//   prev: null
// }

list.get(2)
// "Moved Backward"
// <ref *1> Color {
//   name: 'Yellow',
//   next: null,
//   prev: <ref *2> Color {
//     name: 'Orange',
//     next: [Circular *1],
//     prev: Color { name: 'Red', next: [Circular *2], prev: null }
//   }
// }

Difference Between Singly & Doubly Linked Lists

In short, the main difference is that Singly Linked Lists can only move in one direction, which can be unfavorable if you need to access items in the end of the list. Doubly Linked Lists track an extra property called .prev that allows us to travel in reverse. While time is shorten when accessing with Doubly Linked List, it requires us to store an additional variable in memory.