Introduction to Data Structures for Interviews

Check out a free preview of the full Introduction to Data Structures for Interviews course:
The "Linked List: Insert Method" 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:

## Bianca illustrates the insert() method for a linked list.

Get Unlimited Access Now

Transcript from the "Linked List: Insert Method" Lesson

[00:00:00]
>> Bianca Gandolfo: So now let's try our insert. So somethings I want to keep in mind is we need to update head and tail as needed, like they gave out when we need to do that. It seems like we don't really need to update the head when we insert, because we already initialized the very first one.

[00:00:21] That's the only time when I would think like, okay we need to update the head on the insert is if head is null. So we don't really need to do that. So I'll just delete that for now. And then we can say update tail. And then as needed I think every time we insert we're gonna need to update that tail reference, okay.

[00:00:44]
>> Bianca Gandolfo: Okay, so then we want to say something like this dot tail. This dot tail, so we can say
>> Bianca Gandolfo: So we can initialize our node. We can also do things like, make a little baby node constructor here where we can construct these nodes.
>> Bianca Gandolfo: That's okay. The reason that would be nice is for example, what if you wanted to make this a doubly linked list?

[00:01:17] If our node constructor was just in one place we'd only need to change, we'd only need to add the previous to that node constructor versus here we would have to change it in both places and we'd just have to remember that. So that's another thing that you can bring up as you're coding just kind of the implications of the decisions that you're making the pros and cons.

[00:01:38] In this case I'm just trying to save time. But I'm aware, I want you guys to be aware that maybe there is a better way of doing that. Okay, so now we need to update the tail. So we need to say this dot tail dot next equals node, okay?

[00:02:02] And then-
>> Speaker 2: That's what the updating the null, so then you know it, the reference.
>> Bianca Gandolfo: Yep, so what we're doing there is-
>> Bianca Gandolfo: When we look at our little guy right here. So we start off.
>> Bianca Gandolfo: Like this.
>> Bianca Gandolfo: This is not the right one. We start off like this.

[00:02:35]
>> Bianca Gandolfo: So we start off with the head and the tail, the reason I'm doing it on the tail is because the head and the tail aren't always gonna be the same. So while I'm updating this to our next one which really is going to update both, because of our bi-reference.

[00:03:01] The property of bi-reference. It's going to update both. So when I say this dot next dot node. I'm adding this node to the next and since it's both we don't need to update both. Because it's the same object that we're mutating.
>> Speaker 3: But the tail is no longer the same node anymore.

[00:03:28]
>> Bianca Gandolfo: Right.
>> Speaker 3: Is that what we are going to do?
>> Bianca Gandolfo: Yep, so that is the next step.
>> Speaker 3: Okay.
>> Bianca Gandolfo: So now, our tail is pointing to the wrong thing and we need to update the tail.
>> Bianca Gandolfo: To the node. So now, what we did is we, so we updated what was the tail happens to also be the head.

[00:03:54] So we updated both because of bi-reference. Then we updated this to the new value I guess probably wasn't three, but let's say it was. And so now the new tail is three, but our heads stays the same so when we're traversing through this we start with the head it has a value and it has a next that points to the next one that happens to be the tail.

[00:04:28] But as we grow this right, the next might not be the tail anymore and you know, you can keep traversing through it.
>> Speaker 3: So why do you do the this dot tail dot next equals node as opposed to the this dot head dot next equals node? What is the benefit?

[00:04:49]
>> Bianca Gandolfo: So just here it says it inserts a new value to the end of the link list. So this method is always gonna insert to the end and the head is at the beginning. So that's why we're doing it that way.
>> Speaker 3: Okay.
>> Bianca Gandolfo: So when you're implementing this kind of thing, that's something to ask your interviewer.

[00:05:11] Like when you insert there are different ways you could do an insert. You can insert it like before the head, you can insert it at the end you can insert it. You can pass a node and insert it after that node, so there are all these different ways you can go about it.

[00:05:25] So you can ask specifically what they expect when you insert.
>> Bianca Gandolfo: Okay, so some other things validate the input or stuff like that. Okay, so let's we wanna test our handy work. So we expect it to look something like this, let's run it of course I'm gonna consul logging in.

[00:06:03]
>> Bianca Gandolfo: Okay, so our next is pointing to the second one and our tail is now on the second one. So that's what we want. Any questions about how we arrived here?
>> Speaker 2: I wanna see the next one cuz I'm still-
>> Bianca Gandolfo: Yeah.
>> Speaker 2: That whole next pointing to node is not quite clicking.

[00:06:23]
>> Bianca Gandolfo: Yeah. So now we have our third value. Starting to get pretty nasty here let me make it a little bigger. So we have our head push through our value 1. Our next is the 2 and the next next is a 3, but it is not printing out.

[00:06:46] Then our tail is 3, which points nothing because it is the tail. The tail will always point to null. If we wanted to look at a picture, so here's our head, here's our value that's always gonna point to the next node. And then if you wanna go even more in depth we can look at our,

[00:07:11]
>> Bianca Gandolfo: This visualizer, so when you insert, so here's an insert after tale and so we're expecting to insert after 89. So you see it created the node. It changed the pointer here. This is going to point to null still.
>> Speaker 2: So that's what we're doing. We're adding a [INAUDIBLE].