Linked List Data Structure in JavaScript

Love the series so far! I think you could take a second to explain how setting the tail in the push function is mutating by reference. That might be obvious to other people, but I imagine a decent amount of people more used to functional programming could be confused by this. I had to hop into a repl to see that in fact the head gets mutated when you mutate tail.

I'm also curious if you learned this specific technique from another resource? When I was doing this by hand I saw that head is what is really holding all the links, while I expected tail to. I don't have a CS degree either so maybe I'm just missing something.

I do a lot of mutating in this series, perhaps I can make an update at some point to demonstrate these being built immutably and functionally. If I had done it functionally, we'd end up with the same problem going the other direction 😁.

As for other resources, I've learned this stuff from a bunch of places (too many to list) and combined them as I was writing out the course. Essentially, this information is freely available, I just curated and made lessons for it.

Yeah that is totally fair (re: the other direction). Thanks!

Hi, Kyle, this is a great course! thanks a lot. However, I found an error in list.delete method. The check at the begining of the method should be if (index < 0 || index >= this.length) (greater or equal), otherwise you've got Cannot read property 'next' of null for list.delete(4) case.

Hi Archer, thanks for catching that bug. My tests failed to cover deleting the tail and I missed that, but I've got test coverage and updated content/code for you. The lesson itself has been updated to reflect the change and the code sandbox code as well.

couldn't you start the while loops iterator at 1 in the last case of your delete method? (since you already did the index === 0 check)

for delete and get method, besides conditions of index === 0, index === this.length - 1 should be take into considerations too. so we can replace this statement

if (index === 0) {
    return this.head;
}

with

if (index === this.length - 1) {
    return this.tail;
}

so this methods may get more efficient

for delete and get method, besides conditions of index === 0, index === this.length - 1 should be take into considerations too. so we can replace this statement

if (index === 0) {
    return this.head;
}

with

if (index === this.length - 1) {
    return this.tail;
}

so this methods may get more efficient

for delete and get method, besides conditions of index === 0, index === this.length - 1 should be take into considerations too. so we can replace this statement

if (index === 0) {
    return this.head;
}

with

if (index === this.length - 1) {
    return this.tail;
}

so this methods may get more efficient

not replace but add

@Kyle Shevlin the following test code will fail the delete method

let list = createLinkedList() list.push('Anthony') list.delete(0) console.assert(list.tail === null)

@Kyle Shevlin the following test code will fail the delete method

let list = createLinkedList() list.push('Anthony') list.delete(0) console.assert(list.tail === null)

Hi Kyle, thanks for this course. Really enjoy the pace and broken down examples. One feedback on this particular lesson: Perhaps I'm missing something obvious here, but I believe the concept of a linked list could have been conveyed in a simpler manner, by using an array in closure _(as you did with other data structure examples)_in combination with computed getters instead of the imperative state management. I know this can have a negative performance impact on the larger scale, but in context of this course I think it would remove some of the mental overhead.

Example:

const createLinkedList = () => {
    const list = [];
    const linkedList = {
        get tail () {
            return list[list.length - 1] || null;
        },
        get head () {
            return list[0] || null;
        },
        get length () {
            return list.length;
        },
        isEmpty () {
            return list.length === 0;
        },
        push (value) {
            const node = {
                value,
                get next () {
                    return list[list.indexOf(node) + 1] || linkedList.head;
                },
                get previous () {
                    return list[list.indexOf(node) - 1] || linkedList.tail;
                }
            };
            list.push(node);
            return node;
        },
        pop () {
            if (this.isEmpty()) {
                return null;
            }
            return list.pop();
        },
        get (predicate) {
            return list.find(predicate) || null;
        },
        delete (predicate) {
            const node = this.get(predicate);
            if (!node) {
                return null;
            }
            list.splice(list.indexOf(node), 1);
            return node;
        }
    };
    return linkedList;
}

const myList = createLinkedList();

Can't we use a previous method with the next method to link the node to the previous element as well? This will prevent us to loop through for finding the previous element. What do you think?

https://www.youtube.com/watch?v=aKvLRdXxJYY

Can you explain these two lines (from the push method)

this.tail.next = node
this.tail = node

i don't get why you need to set .next if you're overwriting the tail on the next line. muy confused

How these two lines works behind the scenes?

this.tail.next = node
this.tail = node

It makes no sense for me but works.

The current tail next will become the node u are inserting. Then the inserted node is settled as the tail to become the new tail. This.tail is like slapping a label stating which is the tail so you are slapping the label to another element

the push code mentioned above seems confusing and prone to causing misunderstandings if it were actually used on a team. Is there a clearer way to accomplish the same task?

If you changed it to:

const currentTail = this.tail
currentTail.next = node
this.tail = node

Would that make it any simpler for you?

As is, it's just a sequence of instructions:

• set the current tail's next property to the new node. The current tail will soon become the penultimate item in the list with the next instruction.
• set the list's tail to the new node. This moves the previous tail to the penultimate position in the list.