LinkedList in JavaScript


#1

Another day, another data structure in JS that every other language takes for granted :slight_smile:

class Node {
    constructor(value) {
        this.data = value;
    }
    set data(value) {
        console.log("Setting data: " + value);
        this._data = value;
    }
    get data() {
        return this._data;
    }
    set next(value) {
        this._next = value;
    }
    get next() {
        return this._next;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.count = 0;
    }
    add(value) {
        var node = new Node(value);

        // If first item
        if (this.head === null) {
            this.head = node;
        }

        if (this.tail === null) {
            this.tail = node;
        } else {
            // Add node to the end
            this.tail.next = node;
            this.tail = node;
        }

        this.count++;
    }
    remove(value) {
        // Empty linked list
        if (this.head === null) {
            console.log("There are no items!");
            return;
        }

        // Remove first item
        if (this.head.data === value) {
            // Remove first (and only) item
            if (this.head === this.tail) {
                this.tail = null;
                this.head = null;
                this.count--;

                return;
            }

            this.head = this.head.next;
            this.count--;
        } else {
            var n1 = this.head;
            var n2 = this.head.next;

            // Search through all the items
            while (n2) {
                if (n2.data === value) {
                    n1.next = n2.next;
                    this.count--;

                    if (n2 === this.tail) {
                        this.tail = n1;
                    }
                    return;
                } else {
                    n1 = n2;
                }
                n2 = n2.next;
            }
        }
    }
    removeFirst() {
        var n1 = this.head;

        // remove first item
        if (n1) {
            this.head = n1.next;
            this.count--;
        }

        // update tail if linkedlist is empty
        if (this.count === 0) {
            this.tail = null;
        }
    }
    removeLast() {
        var n1 = this.head;

        // cycle through and find the last item
        while (n1) {
            if (n1.next === this.tail) {
                this.tail = n1;
                this.count--;
                
                return;
            } else if (n1 === this.tail) {
                this.tail = null;
                this.head = null;
                this.count--;

                return;
            }
            n1 = n1.next;
        }
    }
    contains(value) {
        var n1 = this.head;

        while (n1) {
            if (n1.data === value) {
                return true;
            }
            n1 = n1.next;
        }
        return false;
    }
    clear() {
        this.head = null;
        this.tail = null;
        this.count = 0;
    }
}

The usage for it is simple:

var foo = new LinkedList();

foo.add("1");
foo.add("2");
foo.add("3");
foo.add("4");
foo.add("5");
foo.add("6");
foo.add("7");

foo.remove("1");
foo.remove("4");
foo.remove("7");

I haven’t done any extensive testing on it yet, so let me know if you find any issues with it :stuck_out_tongue:

Cheers,
Kirupa


#2

There are a couple of problems with single node lists. For example, removeLast() will do nothing because it starts comparing the second item (n1.next) to tail rather than head itself.

var foo = new LinkedList();

foo.add("1");
foo.removeLast();
foo.count //-> 1

remove() also fails slightly in this case in that it doesn’t clear tail.

var foo = new LinkedList();

foo.add("1");
foo.remove("1");
foo.head //-> undefined
foo.tail //-> Node

Of course you don’t really need the tail in this implementation anyway, since you can check next for null to determine if you’re at the last node in the list, That is unless you like having it as a convenient reference to the last item without iteration :wink:


#3

There’s an identity vs equality issue. For example, if you use new String("someString") instead of "someString", you get 3 different results depending on whether you’re using == or === in the two relevant cases in remove:

foo.add(new String("1"));
foo.add(new String("1"));
foo.add(new String("1"));
foo.add(new String("1"));
foo.add(new String("1"));
foo.add(new String("1"));
foo.add(new String("1"));

foo.remove("1");
foo.remove("1");
foo.remove("1");
foo.remove("1");
foo.remove("1");
foo.remove("1");
foo.remove("1");
foo.remove("1");
foo.remove("1");
foo.remove("1");
foo.remove("1");
// using 2x ==
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
There are no items!
There are no items!
There are no items!
There are no items!
0 "!"

// using 1x ==, 1x ===
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
1 "!"

using 2x ===
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
7 "!"

#4

Along these lines, given the current == usage, there’s also this kind of behavior:

var foo = new LinkedList();

foo.add({bar: 'hello'});
foo.add({baz: 'world'});
foo.add({qux: '!'});
foo // {"bar":"hello"}, {"baz":"world"}, {"qux":"!"}

foo.remove('[object Object]')
foo // {"baz":"world"}, {"qux":"!"}

foo.remove('[object Object]')
foo // {"qux":"!"}

// etc.


#5

Thanks for pointing these issues out sen, kril! I’ve updated the code to take into account single item lists. I’ve also replaced the == with ===. I think that solves most of the equality issues, but that is a tricky one.