Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "Linked Lists" Lesson is part of the full, Data Structures and Algorithms in JavaScript course featured in this preview video. Here's what you'd learn in this lesson:

A Linked List is a tree structure with only one child per node. Each child in the list contains a node value and a link to the next item in the list. To illustrate how Linked Lists work, Bianca shares a couple diagrams of the adding and removing of nodes.

Get Unlimited Access Now

Transcript from the "Linked Lists" Lesson

[00:00:00]
>> Bianca Gandolfo: Before we get into creating our trees, though, let's talk about a simplified tree, which is a linked list. Have people used linked lists before? Okay, so a couple of people have heard of a linked list, maybe you don't use them in your day to day. It's more of a primitive data structure, it could be useful but we don't use it that much.

[00:00:24] So what is a linked list? A linked list is a tree that where each node only has one child. So as we can see here, this is a linked list of breakfast foods. We love eating here in this class, and food, and breakfast. So each node in our linked list has a value, so this value is coffee, and it has a link to its next, toast.

[00:00:55] Actually, this is backwards, let's start with bacon. We should always start with bacon, cuz you know why? If you die before you get to the egg, at least you had your bacon. You know what I mean? That's my life philosophy. So, [LAUGH] bacon points to egg, egg is next is toast, your next is the coffee.

[00:01:15] And so that's a linked list.
>> Bianca Gandolfo: Any questions about linking our lists to a happy breakfast list family?
>> Bianca Gandolfo: Cool.
>> MJ: So the link is the only thing that makes it a structure, I guess? They're individuals and then they know about the next one and the next one knows about the next one but other than that, they're not conscious.

[00:01:43]
>> Bianca Gandolfo: Yeah, they're not aware of other people on the list.
>> MJ: Okay.
>> MJ: I can't picture it but I'm thinking of subarrays and an array. Is it similar?
>> Bianca Gandolfo: Not quite.
>> MJ: Because there's a link.
>> Bianca Gandolfo: So the link would just be a reference to the next node.

[00:02:04] And so it doesn't need to all be in the same array or data structure. And actually that's the beauty of a linked list, is because they're not all in the same data structure. We could do some operations a lot faster.
>> MJ: Okay.
>> Bianca Gandolfo: Yeah, cool. Here's some pictures.

[00:02:19] And I found this bacon conga line, which is perfect.
>> Bianca Gandolfo: So here's an example of our linked list. We have a pointer to our head. And then each node. Here's each node, right? This one has a bunch of nodes, has data, and then a pointer to the next node.

[00:02:41]
>> Bianca Gandolfo: How do we make a pointer in JavaScript? If we want to point to another object, how would we do that?
>> MJ: In the object?
>> Bianca Gandolfo: Hm?
>> MJ: Put in the object?
>> MJ: Never mind.
>> Bianca Gandolfo: Okay. Anyone know?
>> MJ: Can't you just reference the object, like he was saying?

[00:03:03]
>> Bianca Gandolfo: Yeah, you just set it, you set the next variable to the object. Again, it's not gonna be copying an object. It's just a reference to it.
>> Bianca Gandolfo: Cool? So that's what we're doing here. We have our data, that could be its own object. The node itself is absolutely some sort of object, right, because we have to have a reference to it.

[00:03:28] We can't have a primitive value there like a string. I know we were doing stacks with strings. This wouldn't work in this case. All the way to the end, the tail of our linked list, its pointer is null,
>> Bianca Gandolfo: Cool?
>> Bianca Gandolfo: Linked list, linked list, any questions about our linked list?

[00:03:53] Anyone else have a song about linked list that they just made up?
>> MJ: [LAUGH].
>> Bianca Gandolfo: Okay, cool. So let's talk about some operations, and what that might look like. Adding an item, so we have our node A. And for A, our node.next is C.
>> Bianca Gandolfo: Cool, because our node is an object.

[00:04:18] Perhaps we have a property called next that's pointing to our next node. That's how a linked list is operating under the hood. Does that make sense? Cool, now we wanna add a new node. How might we do that?
>> Bianca Gandolfo: An important note is that A has a link to C but C does not have a link to A,

[00:04:47]
>> Bianca Gandolfo: That would be called a doubly linked list. We're only talking about singly linked lists at this point.
>> MJ: Could you just change A's link to B and add I think to C on B?
>> Bianca Gandolfo: Mm-hm.
>> Bianca Gandolfo: So, A dot next is B, B dot next equals C.

[00:05:02] Probably need a temporary variable on there,
>> Bianca Gandolfo: But otherwise, pretty straightforward. Cool, where do we think the time complexity of an operation like that might be?
>> MJ: Constant?
>> Bianca Gandolfo: Constant, yeah. So if we were to add a node into a middle of an array for example,
>> Bianca Gandolfo: What would be the constant tie in there?

[00:05:34]
>> Bianca Gandolfo: MJ, what would be time complexity there?
>> MJ: Add it to the middle of an array?
>> Bianca Gandolfo: Mm-hm.
>> Bianca Gandolfo: Or just add a node, not to the end.
>> MJ: Isn't it linear cuz you have to shift the other ones?
>> Bianca Gandolfo: Yeah, yup. So adding an item to an array in the middle or the beginning is gonna be a linear time operation, right, because we have to shift everything over one index.

[00:06:13] And so here we see a linked list, because it's not in an array, is actually faster for the use case when we wanna add an item to the middle.
>> Bianca Gandolfo: Do you have a question?
>> MJ: No, I'm not sure. I guess it depends on what exactly you mean, right?

[00:06:32] That if you said I wanted to add this to the end of the linked list, you'd have to search for the end. But yeah, if you're at say, insert at the current position. Yeah, if you have a reference to the node.
>> Bianca Gandolfo: Absolutely, yep.
>> Bianca Gandolfo: Cool.
>> Bianca Gandolfo: All right, what about deleting?

[00:06:56]
>> Bianca Gandolfo: How might we delete an item from a linked list?
>> Bianca Gandolfo: Could just be one operation, right, you just change A's reference from B to C.
>> MJ: Mm-hm.
>> Bianca Gandolfo: Yep, and it all will just be garbage collected, totally.
>> MJ: I guess, so if you just, like I said, change the reference on A from B to C, and B would still have its reference to C.

[00:07:28] Do you have to null out the reference on B in order to make it not part of the list? Or is it just enough that A skips over it?
>> Bianca Gandolfo: That's a good question. So the question is, will it be garbage collected if there's a pointer to something else but not a pointer to itself?

[00:07:45] Is that a good summary of your question?
>> MJ: Yes.
>> Bianca Gandolfo: Once there's no reference to an object, it gets deleted, yeah. Even if it holds a reference to something else, yeah.
>> Bianca Gandolfo: Cool.
>> Bianca Gandolfo: All right, okay, so here's our interface. We have a storage, we have a head.

[00:08:09] We might even have a reference to the tail depending on the operations that you want. Some methods, addToTail, remove, you can search it, as well. And that's sort of the basics for our linked lists.