Linked List Data Structure in JavaScript
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.
Instructor: [00:00] A linked list is a collection of items where each item has a connection to the next item in the list, hence, the word "linked" in the name.
[00:07] To make our linked list, we first want to create a node object for each item in our list. Our node has two properties -- the value stored at this node and a next property which gets pointed to the next item in our list. This property defaults to null.
[00:22] Next, we want to make our list data structure. Our list will have several properties we want to keep track of -- a head property, a tail property, and a length property. We'll also want to create several methods for our list -- push, pop, get, delete, and is-empty.
[00:37] Our head and tail will both start as null and our length will start as zero. We can also implement the is-empty method pretty quickly as it just returns whether or not the length is zero. Now we want to add our push method.
[00:50] When we want to push a value onto our list, we need to first turn that value into a node using our create-node factory function. Push places a new node at the end of our list. Depending on the length of our list, we might need to take somewhat different actions in order to achieve this.
[01:07] No matter what state our list is in, we know that eventually we need to update our tail property to this node that we've just created. We also know that we will need to increment our length property, so let's write that.
[01:21] Now if our list does not have a head, that is the first item in the list, then we can also deduce that it doesn't have a tail, the last item in its list because the list is empty.
[01:30] The opposite is also true. If our list has a head then we know that it has a tail as well because even a list of length one has a head and a tail.
[01:39] If we don't currently have a head, our list head property is set to our new node. Since we didn't have a head, we also don't have a tail, and that needs to be set to this node as well. Since this is a special case, we increment the length here and return the node now.
[01:54] However, in scenarios where our list does have a length, and thus has a head and a tail, our new node gets set to our current tail's next property. Then we reset the tail like I said and we increment the length, so the only thing we have left is to return the node.
[02:09] Now we'll move on to our pop method. Things get a bit more complicated here. We need to reason out a few scenarios. How do we pop items when our list is empty, when our list has a length of one, and when our list has many items? An empty list is easy if there's nothing to pop. We'll just return null.
[02:28] Now for our remaining scenarios, a list of length one and a list of a length greater than one. We're always going to return the tail node, so let's store that in a variable.
[02:38] A list of length one means that our head and our tail are the same node, which means in order to pop this node off of our list, we also need to set our head and tail back to null. When we do this, we also need to reset our length to zero. Given that our length is one, we can just decrement it, and then we return the node that we've stored.
[02:59] Now for all other scenarios, we need to set the item before our tail, the penultimate item, as the new tail with its next value set to null. How do we do this?
[03:08] This is one of the inefficiencies of linked list. Whenever we have to find an item, we have to start at the head and continue to call next until we find that item. For our case, we're going to start by having a variable called current that we're going to set to the head. Then we're going to create a variable penultimate that will eventually set to the penultimate item.
[03:28] Now while we have a current node, we need to check if that current's next property is equal to the tail. That's how we know we have our penultimate item.
[03:38] Then we want to break our loop once we have our penultimate item. Otherwise, if we're not at that penultimate item, we set the item current to the current.next property to move on.
[03:50] At this point, we should have our penultimate item, the one before the tail. We need to set its next property to null because it's going to become our tail. Now, because we're going to return a node, we need to decrement the length. Now we can return the node we stored before.
[04:06] Now we can move on to our get method. Our get method receives an index as an argument. If the index that we're giving is less than zero, or greater than our length, then we can return null, as we know that there's no item in those bounds. If our index happens to be zero, we can just return the head.
[04:25] For other scenarios, it's going to take considerably longer to get to the item in our list. Just like in our pop method, we're going to have to loop through each item, calling next on each one until we find the one we're looking for.
[04:39] Similar to before, I'm going to create a variable current that we'll start by setting it to the head. We're also going to keep track of an iterator. When that iterator matches the index passed in, we know that we've gotten to the item that we need to retrieve.
[04:51] We can use a while loop again to go through each of our items. Each loop through, we increment our iterator, and we set the current value to the next value. Once our loop is done, and we've got into the right index, we know we have the right item, so we can just return what current is currently set to.
[05:09] Now we can implement delete, which is very similar to get. The delete method also receives an index as an argument. Just like get, if the index is less than zero, or greater than our length, we're just going to return null.
[05:21] Now if index equals zero, we're going to return the head of our list. Because I need to make some small modifications, I'm going to store it in a variable.
[05:31] We need to reset the head of our list to be the next item of our current head. We also need to decrement the length of our list. In this scenario, we can return our deleted node right away.
[05:43] In all other scenarios, similar to the pop method and the get method, we're going to have to start from the beginning of our list and loop through each item until we find the item that we need to delete. I'll create a current variable and set it to the head, but I'll also need to store a previous node.
[05:58] We do this because a deletion in a linked list is simply taking a previous' next property and pointing it to the current node's next property, effectively, slicing out the current node from the list. We also need to store an iterator to check against the index passed in to make sure we've gotten to the current node. We'll use a while loop just like we did in the get method.
[06:23] We need to increment our iterator. We'll set the previous value to the current value and our current value to the current's next property. When our while loop is complete, we know that our current value is the value that we're going to delete, so I'm going to store that in a variable.
[06:40] Now we do the work of setting our previous' next property to our current's next property. This slices out the deleted node. Because we've now effectively deleted our node, we need to decrement the length. Finally, we return our deleted node.
[06:57] Now I actually want to add one more method really quickly to our list. I want to add a print method so we can visualize it. For our print method, we'll create an array of values.
[07:07] Just like all the other loops that we've done in our linked list, we'll need to start at the head and loop through, so I'll store a current variable set to the head.
[07:15] While we have a current item, we're going to push it's value into our value's array. Then we'll set our current variable to our current's next property.
[07:23] When this loop is done, we know we've gone through our entire list. We're going to call join on our values array. We're going to pass in an arrow symbol that will return us a string that looks like our values are linked together.
[07:35] Now that we've created our linked list, let's actually try it out. I'm going to create some values, and we're going to push them onto our new list. Now let's verify that our linked list is not empty. It came back false because our list is full of items.
[07:55] Now let's pop off the last item in our list and see that we get E back. We can verify that after E was popped that our tail is now set to D. Let's try our get method on the item at Index One.
[08:09] We can see that we got the node with the value B -- which was the second value we passed in, which would be the first index -- and we can see all the connected nodes to B. Instead of getting it, let's delete it and then look at our list.
[08:23] We'll do this by printing out our list. We see when we called delete that we got back that same node that we called with get. Then when we print it out, we see that we only have three nodes remaining and the values A is connected to C, which is connected to D.
[08:37] This is a linked list. There are some modifications that you can make. There are doubly-linked lists where each node also points to the node previous to it. There's also lists that are cyclical in which the tail points to the head.
[08:51] I leave these to you to work out on your own and try and make them yourself.
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
deleteandgetmethod, besides conditions ofindex === 0,index === this.length - 1should 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
nextproperty 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.
Love the series so far! I think you could take a second to explain how setting the tail in the
pushfunction 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 theheadgets mutated when you mutatetail.I'm also curious if you learned this specific technique from another resource? When I was doing this by hand I saw that
headis what is really holding all the links, while I expectedtailto. I don't have a CS degree either so maybe I'm just missing something.