Singly and doubly linked lists in Javascript

Let’s do a quick recap on a data structure called linked list. First of all, why do we need lists at all? The answer is the same as for every other data structures: efficiency. It is yet another way of organizing data in memory which has its drawbacks and benefits. And we’re going to introduce some complexity to be able to enjoy some of those.

The main and most prominent feature of lists is the potential ability to insert and remove any item in constant time. Compare that to array, where you often need to rearrange the elements after modifying. That makes life easier in certain cases.

A trade-off here is that we’re losing the ability to access any item in constant time like we could do with arrays. Since every item in array in contiguous in memory, the access address of every other element can be easily calculated. Another thing which is lost is spatial memory locality, since elements are not contiguous anymore.

Screen-Shot-2018-05-19-at-11.43.15-AM

OK, now that we’re convinced that lists are important, how about to implement one from scratch so we can have a more detailed look?

There are different ways to implement lists and we’ll look at one. Depending on the set of tasks we’re going to use our list for, we need to carefully design our class interface. Which methods to include in interface is up to you as a data structure designer. Here are some of the most frequently seen methods that we’re about to set up, they’re going to make more sense later on:

    insertAtHead(val)
    insertAtTail(val)

    removeAtHead(val)
    removeAtTail(val)

    insertAtIndex(index, val)
    deleteAtIndex(index)

    insertAfterKey(key, val)
    insertBeforeKey(key, val)

    getIndexByValue(val)
    getValueAtIndex(index)
    getNodeAtIndex(index)

    doForEach(fn)
    stringify()

Q: Why do we have insertAtHead() if it does pretty much the same as insertAtIndex(0)?

A: It makes implementation simpler. We’ll be dealing with edge cases, particularly when list is empty or has only one element – and we need to react to those cases accordingly. It is up to you which methods to expose publicly, you may choose to expose only latter which internally still use insertAtHead().

A*: This is only one example of designing this data structure. One of the most rational and intuitive in my opinion. Another common way is to make “head” always point to “dummy” empty element which helps to avoid some edge cases by introducing a few others.

Q: Do I need singly and doubly linked list?

A: It depends on your requirements. They’re not that different: doubly linked list requires a bit more bookkeeping, but it allows to remove elements from anywhere in the list in constant time, given that you have a pointer to that element. Searching for elements is still linear, since you need to check on every item in the worst case. Doubly linked list allows to traverse the list backward which might be desired in some scenarios.

Let’s start with the simple singly linked node. We’ll need two classes: one for items and another for list itself which acts as an entry point.

Q: Is it possible to combine them into one? Let the nodes have the methods?

A: It is possible but hardly needful. There’s hardly a reason to do that with linked lists.

Here’s how we define our classes. I like the idea of inline initializing of arguments as it helps to save a few lines later. The values of our list can be anything, from primitives to links to other data structures.

class ListNode {
    constructor(val, next = null) {
        this.next = next
        this.val = val
    }
}

class LinkedList {
    constructor(head = null, tail = null) {
        this.head = head
        this.tail = tail
    }
}

let list = new LinkedList()

Q: Why do we need ‘tail’ property? Is it really necessary?

A: Not really, but it has additional benefits. It’s our design choice: it allows us to add elements to tail in constant time. We don’t need to traverse the whole list, since we’re making sure our ‘tail’ is always points to the last element. It doesn’t help us to remove items from ‘tail’ in case of singly linked list though, we would need to access previous element to do that. At least as long we don’t store ‘pre-tail’ as well.

Let’s look at our first methods:

    insertAtHead(val) {
        if (!this.head) {
            this.head = new ListNode(val, null)
            this.tail = this.head
        } else {
            this.head = new ListNode(val, this.head)
        }
    }

    insertAtTail(val) {
        if (!this.head) {
            this.head = new ListNode(val, null)
            this.tail = this.head
        } else {
            this.tail.next = new ListNode(val, null)
            this.tail = this.tail.next
        }
    }

Again, there are more ways to do that, feel free to invent your own. It’s likely going to be a good way as long as it does exactly what it is supposed to. Those ‘this.head’ checks are edge cases guards when the list is empty.

Similar goes for deletion:

    removeAtHead(val) {
        if (this.head === this.tail) {
            this.head = null
            this.tail = null
        } else {
            this.head = this.head.next
        }
    }

    removeAtTail(val) {
        if (this.head === this.tail) {
            this.head = null
            this.tail = null
        } else {
            let curr = this.head

            while (curr.next !== this.tail) {
                curr = curr.next
            }

            curr.next = null
            this.tail = curr
        }
    }

Now, the methods accessing list by indexes are a bit more clunky. We use a helper method to get the node using the index.

    insertAtIndex(index, val) {
        if (index === 0) {
            return this.insertAtHead(val)
        }

        let node = this.getNodeAtIndex(index - 1)
        if (!node) {
            return
        }

        if (node.next) {
            node.next = new ListNode(val, node.next)
        } else {
            node.next = new ListNode(val, null)
            this.tail = node.next
        }
    }

    removeAtIndex(index) {
        let curr = this.getNodeAtIndex(index)
        if (!curr) {
            return
        }

        if (index === 0) {
            return this.removeAtHead()
        }

        let node = this.getNodeAtIndex(index - 1)

        if (curr.next) {
            node.next = curr.next
        } else {
            node.next = null
            this.tail = node
        }
    }

    getNodeAtIndex(index) {
        let curr = this.head

        while (curr && index--) {
            curr = curr.next
        }

        return curr
    }

Deletion of the last element:

Screen-Shot-2018-05-19-at-12.54.11-PM

If you made it this far, then you should know everything it takes to carry on by yourself from there. You might try to implement the rest on your own or check the finished code for singly linked list here on github.

Q: How can I get the list length?

A: That’s right, we don’t have such method right now. You should be ready to create it on your own now by traversing the list and counting the number of nodes. It could be done in constant time, if you choose to keep track of length in your instance variable.

Let’s now take a look on doubly linked list. Their are very similar by design: the only difference from conding perspective is ‘prev’ pointer on the node, which is pretty self-explanatory. We’ll look at a few methods to see the differences.

class DListNode {
    constructor(val, next = null, prev = null) {
        this.val = val
        this.next = next
        this.prev = prev
    }
}

class DLinkedList {
    constructor(head = null, tail = null) {
        this.head = head
        this.tail = tail
    }

    insertAtHead(val) {...}

    insertAtIndex(index, val) {
        if (index === 0) {
            return this.insertAtHead(val)
        }

        let node = this.getNodeAtIndex(index - 1)
        if (!node) {
            return
        }

        if (node.next) {
            let tmp = new DListNode(val, node.next, node)
            node.next.prev = tmp
            node.next = tmp
        } else {
            let tmp = new DListNode(val, null, node)
            node.next = tmp
            this.tail = tmp
        }
    }

    removeAtHead() {...}

    removeAtIndex(index) {
        let curr = this.getNodeAtIndex(index)
        if (!curr) {
            return
        }

        if (index === 0) {
            return this.removeAtHead()
        }

        if (curr.next) {
            curr.next.prev = curr.prev
            curr.prev.next = curr.next
        } else {
            curr.prev.next = null
            this.tail = curr.prev
        }
    }

    getNodeAtIndex(index) {...}
}

Here’s what insertion looks like:

Screen-Shot-2018-05-19-at-12.16.32-PM

Now all the class methods have to make sure that prev is always up-to-date, no matter what. Doubly linked list also allow us to traverse the list in both directions and easily remove elements from the tail. Full code is on github.

Now that you have your own list implementation at your disposal, you’re should be comfortable enough to face more challenging problems. Good luck with your journey!