Why implementing linked lists in JavaScript ?

At least two motivations:

Implementation

I will be inspired by the Haskell API for linked lists (haa, that lack of creativity. You often rely on your basic training when struggling to find new ideas, that’s why the idea of discipline is so dear to me).

We will define elementary operations to apply on lists and also a standard function (max will do).

In Haskell the two operators are : (cons) and ++ (mappend).

The cons operator is already implemented as the append and the mappend function as the concat method (let’s keep things simple).

The new prototype is now, after some minutes of debugging and learning how to use the nod interpreter:

// Notice how the `append` definition has changed.
// The type of `this.next` is now a LinkedList, and
// the value is stored in a dedicated container (value).

module.exports = {
    LinkedList: function(value) {
        this.next = null;
        this.value = value;
        this.append = function (obj) {
            var newList = new this.constructor(obj);
            newList.next = this;
            return newList;
        }

        this.concat = function (listToAppend) {
            console.log(this.toString())
            if (this.next === null){
                this.next = listToAppend;
            } else {
                this.next.concat(listToAppend)
            }
        }
        // Let's implement a toString() method, because having
        // a textual representation of objects is always nice.
        this.toString = function(){
            if (this.next != null){
                return this.value + "," + this.next.toString();
            }
            return this.value;
        }
        this.max = function(){
            console.log(this.toString());
            if (this.next === null) {
                return this.value;
            } else {
                return Math.max(this.value, this.next.max())
            }
        }
    }
}

All of that can be a little tricky.

Notice that I use only recursive functions.

Let’s test

Fire the node interpreter and load the above file:


> ll = require('./javascriptLL.js')
> x = (new ll.LinkedList(-2)).append(4).append(2).append(3)
> x.toString()
'3,2,4,-2'
> y = (new ll.LinkedList(8)).append(3))
'3,8'
> x.concat(y)
> x.toString()
'3,2,4,-2,3,8'
> m = x.max()
> m
8

Everything seems to work, we could add the head and tail methods (easy enough).

Some small remarks and warnings: the empty list is not properly defined here because the constructor returns as a default a list with a single element, whose value is null eventually if no argument is passed as a parameter.

This make things not quite as precise as how it is implement in Haskell. However it was good for fun and practice :)

For you guys really more interested in pure FP, you can check the following links: