Does my JS LinkedList class look right?

I'm trying to fully comprehend all I can concerning linked lists.

To do that, I decided making them (and making them work) in JS would be my best route.

I want to make sure no one sees any major flaws or careless mistakes (or pure dumbassery) in my code.

// Javascript Linked Lists v0.6

//ListNode class - for internal use (mostly)
class ListNode {
    constructor (value, next = null) {
        this.value = value;
        this.next = next;
    }
}

class LinkedList {
    constructor (head = null) {
        this.head = head;
        this.length = 0;
    }
    add(el) {
        let node = typeof el.value !== 'undefined' ? el : new ListNode(el);
        if (typeof node.next === 'undefined'){
            node.next = null;
        }
        let previous, current;
        if (this.head === null){
            node.previous = null;
            this.head = node;
        } else {
            current = this.head;
            while(current.next) {
                previous = current;
                current = current.next;
            }
            node.previous = current;
            current.next = node;
        }
        this.length++;
    }
    remove(val) {
        let current = this.head;
        let previous;
        if (current.value === val){
            this.head = current.next;
        } else {
            while (current.value !== val){
                previous = current;
                current = current.next;
            }
            previous.next = current.next;
        }
        this.length--;
    }
    clear() {
        this.head = null;
    }
    first() {
        return this.head;
    }
    next() {
        return this.head.next;
    }
    last() {
        let lastNode = this.head
        if (lastNode){
            while (lastNode.next) {
                lastNode = lastNode.next;
            }
        }
        return lastNode;
    }
    pop(){
        let node = this.last();
        this.remove(node.value);
        this.length--;
        return node;
    }
    shift() {
        let node = this.head;
        this.remove (node.value)
        this.length--;
        return node;
    }
    unshift(val) {
        let node = typeof val.value !== 'undefined' ? val : new ListNode(val);
        let current = this.head;
        node.next = current;
        node.previous = null;
        this.head = node;
        this.length++;
        return this.length;
    }
    addToHead(val) {
        return this.unshift(val);
    }
    indexOf(val){
        let current = this.head;
        let i = -1;
        while (current) {
            i++;
            if (current.value === val){
                return i;
            }
            current = current.next;
        }
        return -1;
    }
    contains(val) {
        return this.indexOf(val) > -1;
    }
    elementAt(i){
        let current = this.head;
        let count = 0;
        while (count < i){
            count++;
            current = current.next;
        }
        return current.value;
    }
    addAt(ind, val){
        let node = typeof val.value !== 'undefined' ? val : new ListNode(val);
        let current = this.head;
        let previous;
        let currentIndex = 0;
        if (ind > this.length){
            return false;
        }
        if (ind === 0){
            node.next = current;
            node.previous = null;
            this.head = node
        } else {
            while (currentIndex < ind){
                currentIndex++;
                previous = current;
                current = current.next;
            }
            node.next = current;
            node.previous = previous;
            previous.next = node;
        }
        this.length++;
    }
    removeAt(index){
        let current = this.head;
        let previous;
        let currentIndex = 0;
        if (index < 0 || index >= this.length){
            return null;
        }
        if (index === 0){
            this.head = current.next;
        } else {
            while (currentIndex < index){
                currentIndex++;
                previous = current;
                current = current.next;
            }
            previous.next = current.next;
        }
        this.length--;
        return current.value;
    }
    count() {
        return this.length;
    }
    isEmpty() {
        return this.length === 0;
    }
    print(current = this.head) {
        if (current){
            console.log (current.value)
        } else {
            return;
        }
        this.print(current.next)
    }
}

// create a linked list
let list = new LinkedList();
let a = "a";
let b = "b";
list.add(a)
list.add(b)
list.add("c")
let d = new ListNode("d");
list.add("e")
list.addAt(3, d)

image


Looks right.
Although the last method is a little inefficient; in many applications, it's common to give the list object references to both the first and last nodes.

Also, what does this give you?

let list = new LinkedList();
list.add("foo")
list.add("bar")
list.add("baz")
list.add(list.next())
for (i=0 ; i<10 ; i++) {
  console.log (list.shift().value)
}
console.log("Length: " + list.length);

It looks like some of your functions give the nodes a previous property, but this isn't used. Also, your length variable can easily get confused; because add increments it without checking if the added element is a ListNode which already has a next.

Javascript nerds would say that any list class should be Enumerable so that you can use it with foreach/map/grep/etc; but I think that's more complexity than you need.


Also, what does this give you?

Ruh roh!

I done been overlooking stuff!

First, I got an infinite loop (because I failed to add code to make sure there was something to shift).

Now, my length is -16. Hehehe.

What, oh what, have I done? (I'll be right back!)


You might want to look at some sort of unit testing. At its simplest, have a function that uses your code is different ways and tests the end result is what you think it should be. There are also unit testing frameworks, but that might be overkill here. It is a good habit to unit test code like this.


Hrmm... I don't know what I've done, but I apparently lack the concentration required to troubleshoot it right now.

I shall return, though -- either with a "fix" or with questions.


You might want to look at some sort of unit testing.

Ah, I posted that last post without refreshing the page and didn't see this.

It does sound a like a good idea.


First, I got an infinite loop (because I failed to add code to make sure there was something to shift).

I suspect you ended up with an infinite loop because the list has two elements whose next properties point to each other :)

LISP-style lists can handle this, because you can have lists that merge. It just means that you can't loop over them, because infinite lists exist. And, of course, the length property isn't meaningful.

But most list libraries use a double-linked list (DLL), where each element has both next and prev properties.
When your add function comes to add a new element node after an existing element previous, you would do something like:

if (node.prev) {
  node.prev.next = node.next;
}
if (node.next) {
  node.next.prev = node.prev;
}
node.next = previous.next;
if (previous.next) {
  previous.next.prev = node;
}
previous.next = node;
node.prev = previous;

which removes node from any list it's previously been in.

Or, depending on how you're going to use it, you might allow the node and all its successors to be moved as a unit. But in this case, it might be a good idea to check that the added node isn't already in this list; for which you would probably need a reference to the list object.


Okay, I still have to read most of the stuff posted after the first example that threw me for an infinite loop.

Here's that code (slightly modified, so as to avoid an error):

list = new LinkedList();
list.add("foo")
list.add("bar")
list.add("baz")
list.add(list.next())
for (i=0 ; i<10 ; i++) {
  console.log (list.shift()?.value) // added the question mark to avoid an error when the list is empty
}                                      
console.log("Length: " + list.length);

OUTPUT

foo debugger eval code:7:11
bar debugger eval code:7:11
baz debugger eval code:7:11
bar debugger eval code:7:11
undefined debugger eval code:7:11
undefined debugger eval code:7:11
undefined debugger eval code:7:11
undefined debugger eval code:7:11
undefined debugger eval code:7:11
undefined debugger eval code:7:11
Length: 0

Linked Lists v0.7

// Javascript Linked Lists v0.7

//ListNode class - for internal use (mostly)
class ListNode {
    constructor (value, next = null) {
        this.value = value;
        this.next = next;
    }
}

class LinkedList {
    constructor (head = null) {
        this.head = head;
        this.length = 0;
    }
    add(el) {
        let node = typeof el.value !== 'undefined' ? {value: el.value} : new ListNode(el);
        //if (typeof node.next === 'undefined'){
            node.next = null;
        //}
        let previous, current;
        if (this.head === null){
            node.previous = null;
            this.head = node;
        } else {
            current = this.head;
            while(current.next) {
                previous = current;
                current = current.next;
            }
            node.previous = current;
            current.next = node;
        }
        this.length++;
    }
    remove(val) {
        let current = this.head;
        let previous;
        if (current.value === val){
            this.head = current.next;
        } else {
            while (current.value !== val){
                previous = current;
                current = current.next;
            }
            previous.next = current.next;
        }
        this.length--;
    }
    clear() {
        this.head = null;
    }
    first() {
        return this.head;
    }
    next() {
        return this.head.next;
    }
    last() {
        let lastNode = this.head
        if (lastNode){
            while (lastNode.next) {
                lastNode = lastNode.next;
            }
        }
        return lastNode;
    }
    pop(){
        let node = this.last();
        this.remove(node.value);
        this.length--;
        return node;
    }
    shift() {
        if (!this.head){
            return null;
        }
        let node = this.head;
        this.head = this.head.next;
        this.length--;
        return node;
    }
    unshift(val) {
        let node = typeof val.value !== 'undefined' ? val : new ListNode(val);
        let current = this.head;
        node.next = current;
        node.previous = null;
        this.head = node
        this.length++;
        return this.length;
    }
    addToHead(val) {
        return this.unshift(val);
    }
    indexOf(val){
        let current = this.head;
        let i = -1;
        while (current) {
            i++;
            if (current.value === val){
                return i;
            }
            current = current.next;
        }
        return -1;
    }
    contains(val) {
        return this.indexOf(val) > -1;
    }
    elementAt(i){
        let current = this.head;
        let count = 0;
        while (count < i){
            count++;
            current = current.next;
        }
        return current.value;
    }
    addAt(ind, val){
        let node = typeof val.value !== 'undefined' ? val : new ListNode(val);
        let current = this.head;
        let previous;
        let currentIndex = 0;
        if (ind > this.length){
            return false;
        }
        if (ind === 0){
            node.next = current;
            node.previous = null;
            this.head = node
        } else {
            while (currentIndex < ind){
                currentIndex++;
                previous = current;
                current = current.next;
            }
            node.next = current;
            node.previous = previous;
            previous.next = node;
        }
        this.length++;
    }
    removeAt(index){
        let current = this.head;
        let previous;
        let currentIndex = 0;
        if (index < 0 || index >= this.length){
            return null;
        }
        if (index === 0){
            this.head = current.next;
        } else {
            while (currentIndex < index){
                currentIndex++;
                previous = current;
                current = current.next;
            }
            previous.next = current.next;
        }
        this.length--;
        return current.value;
    }
    count() {
        return this.length;
    }
    isEmpty() {
        return this.length === 0;
    }
    print(current = this.head) {
        if (current){
            console.log (current.value)
        } else {
            return;
        }
        this.print(current.next)
    }
}

Now I shall scroll up and read everything after that code first appeared. I've surely got more fish to fry.


Can I do anything special with this that I couldn't otherwise do with an array in JS?


With a basic list, probably not. But for certain applications…

In my case, I'm rolling my own linked list because I'm using a slightly unorthodox method to remove elements from the list:
Removal:

this.next.prev = this.prev
this.prev.next = this.next

And to undo removal:

this.prev.next = this.next.prev = this

It's a lot faster than standard arrays for tasks where you'll be repeatedly deleting and undeleting elements, but you don't need to add anything new. Two integer assignments and you're done :)

Also, cyclical linked lists (the last element's next points to the first element again) can be used in interesting ways. For example, if you want to loop over a list starting with a specified element, you can easily loop until you get back to the start point. No need to keep track of an index, or create a temporary data structure to collate your array.

Some of these are rather unusual tasks, that you probably won't need often. The array is a general-purpose tool, so it's often quite inefficient compared to a specific type of list made for a specific task. So it's good to understand how these things work under the hood, in case you ever need them :)


Log in to post a reply.

Support

Forums