Linked List Data Structure in JavaScript

Kyle Shevlin
InstructorKyle Shevlin

Share this video with your friends

Send Tweet

A linked list is a collection of items where each item points to the next one in the list. Because of this structure, linked lists are very slow when searching for an item at a particular index. An array, by comparison, has quick gets when searching for an index, but a linked list must start at the beginning, often called the "head", and loop through each item's next property until we arrive at the item. This makes gets in a linked list an operation that takes O(n) time.

While gets might be slow in a linked list, it's other operations, like push and delete come with some great benefits we will see in the lesson.

Mike Schutte
Mike Schutte
~ 3 years ago

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.

Kyle Shevlin
Kyle Shevlininstructor
~ 3 years ago

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.

Mike Schutte
Mike Schutte
~ 3 years ago

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

Archer Software
Archer Software
~ 3 years ago

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.

Kyle Shevlin
Kyle Shevlininstructor
~ 3 years ago

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.

Jacob Juul
Jacob Juul
~ 3 years ago

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)

HuanCheng Bai
HuanCheng Bai
~ 3 years ago

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

HuanCheng Bai
HuanCheng Bai
~ 3 years ago

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

HuanCheng Bai
HuanCheng Bai
~ 3 years ago

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

HuanCheng Bai
HuanCheng Bai
~ 3 years ago

@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)

HuanCheng Bai
HuanCheng Bai
~ 3 years ago

@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)

rasmusbp
rasmusbp
~ 2 years ago

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();
Umang
Umang
~ 2 years ago

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?

David Krause
David Krause
~ 2 years ago

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

Dave
Dave
~ 2 years ago

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

Kamil L
Kamil L
~ 2 years ago

How these two lines works behind the scenes?

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

It makes no sense for me but works.

reynard93
reynard93
~ 2 years ago

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

Hans Brough
Hans Brough
~ 5 months ago

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?

Kyle Shevlin
Kyle Shevlininstructor
~ 5 months ago

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.