![Introduction to Data Structures for Interviews](https://static.frontendmasters.com/assets/courses/2018-08-09-data-structures-interviews/thumb.webp)
Check out a free preview of the full Introduction to Data Structures for Interviews course
The "Linked List: Insert Q&A" Lesson is part of the full, Introduction to Data Structures for Interviews course featured in this preview video. Here's what you'd learn in this lesson:
Taking questions from students, Bianca clarifies how the linked list is structured using an interactive diagram and reviews alternative ways that the linked list might be implemented.
Transcript from the "Linked List: Insert Q&A" Lesson
[00:00:01]
>> Speaker 1: Here's a guess, can you go back to the counter.
>> Bianca Gandolfo: Yeah, sure.
>> Speaker 1: Scroll up to the insert.
>> Speaker 1: The method itself. So line 16 we're saying that this.tail.next is node. But if we're looking at the node, the pointer is null. But now we're updating that pointer to the next object, so that's what's not kind of clicking.
[00:00:27]
>> Bianca Gandolfo: So this .tail, so this .tail looks like
>> Speaker 1: Because it's, got it, because it's always gonna be null. We're adding the next to the tail, not, [CROSSTALK]
>> Bianca Gandolfo: Yep, so this node, [CROSSTALK]
>> Speaker 1: Got it.
>> Bianca Gandolfo: Is a separate object.
>> Speaker 1: Just meant for the tail.
>> Bianca Gandolfo: Mm-hm.
[00:00:47]
>> Speaker 1: Got it from [INAUDIBLE].
>> Bianca Gandolfo: And then we set the current tails next to that node. So we do that, but then, we then what we have our, our current tail is no longer our current tail. So then we need to make it the correct tail. And so we do that by adding it here.
[00:01:08]
If we'd skipped this, this line, what would happen?
>> Tom: This input to the [INAUDIBLE] was the same.
>> Speaker 1: Break the linkage.
>> Bianca Gandolfo: What were you saying, Tom?
>> Tom: Was it the same points of the same node?
>> Bianca Gandolfo: Yeah, so every time we insert, the tail will just be updated and we won't have our next set to the next value.
[00:01:34]
So this line, it may seem kinda, it looks a little bit repetitive, but they're doing both very important thing. So first thing is setting the next value of the current tail to our new node. And the next one is updating our tail to be the real tail, which is our new node.
[00:01:53]
So doing two very important things.
>> Bianca Gandolfo: Deceptively powerful right?
>> Speaker 4: Could you do this .head.next=node then visually show us, I can do it on my own too.
>> Bianca Gandolfo: Yeah, so no that is a good thing. So if we did this.head=next here?
>> Speaker 4: Mm-hm.
>> Bianca Gandolfo: And then update the tail?
[00:02:20]
>> Speaker 4: Yeah, and keep that [INAUDIBLE].
>> Bianca Gandolfo: Okay, so I'll run it.
>> Speaker 1: Then the point is next and null.
>> Bianca Gandolfo: So you see that the next would be three and not two. Because we need to make sure, so as we grow our list, the head is always put into the first one.
[00:02:41]
So if we look at this visualizer. If we said on the answer we said this .head.next, you would be setting this every time. So let's say that you,
>> Bianca Gandolfo: Okay, let's create an empty. So we're going to insert a head at 85. So this is our first one, it's the head, it's also the tail, okay?
[00:03:10]
And then we can insert after the tail, let's say 13. So now our head is pointing to the next one. This is head.next is 13. Now, if we insert to the head, this here is gonna insert to the head, which is not what we necessarily wanna do. But what would happen is that it would go here, or actually that one goes before the head, so that's a little bit different.
[00:03:41]
So this one is inserting before the head, but I wish I could drag this around. Lets remove head, okay. If we set this .head.next to the next value,
>> Bianca Gandolfo: Let's say it's 91, 13 would then become 91. But really, we want head.next.next to be 91.
>> Speaker 1: Like we're chaining to the head?
[00:04:11]
>> Bianca Gandolfo: Yeah, but that next.next.next, so, you need to know how many .next you need to traverse. And you don't really know that from the head, the only way you can do that is really loop through it. So that's why if we keep a reference to the tail, so here's the tail, let's say, tail.next and we add it there.
[00:04:33]
So tail.next, we can insert 46, and it just inserts it there. Versus .next that's always going to keep adding just one next to the head.
>> Tom: But you could add it to the head? You know what I mean like you could add to the front of the list instead of that?
[00:04:59]
>> Bianca Gandolfo: Yeah.
>> Tom: Isn't that how the Hash Table kinda worked? We're adding in front of the lest all the time?
>> Bianca Gandolfo: It really depends.
>> Tom: Depends?
>> Bianca Gandolfo: Yeah, you can add, so that's the nice thing about a link list you can do content time add insertions, anywhere in the list.
[00:05:15]
So you can do it before, you can do it in the middle, you can do it at the end, so that's nice. And like what you choose to do with it? It really depends on what you're trying to do, appending to the tail is pretty standard.
Learn Straight from the Experts Who Shape the Modern Web
- In-depth Courses
- Industry Leading Experts
- Learning Paths
- Live Interactive Workshops