Linked List: Remove Tail

[00:00:00]
>> Bianca Gandolfo: All right, now we're gonna delete a node.
>> Bianca Gandolfo: And let's kind of reason about how we might delete a node.
>> Bianca Gandolfo: So when I'm thinking about deleting a null, there are few things that I am thinking about. Like is this the head, is the tail, are we deleting a specific node?

[00:00:23]
Like are you gonna give me a value? And then I have to search this list for a value and delete it or you give me a reference to node. And I need to delete it. Cuz that's different than a value.
>> Speaker 2: This value. That's gonna take forever. Cuz you gotta go one step at a time.

[00:00:38]
>> Bianca Gandolfo: Yeah you have to loop through it. Exactly. But maybe that's just what the requirement is, so I'm gonna read what is written. It just says delete a node. Let's say, deletes a node,
>> Bianca Gandolfo: Actually let's do removeTail. I see, so this one, you give it a node.

[00:01:04]
You give it a reference to a node and then it returns the value. But let's removeTail, it's a little bit easier.
>> Bianca Gandolfo: Okay so let's do
>> Bianca Gandolfo: removeTail. Not gonna take anything. And when I run this, I expect for a couple of things to happen. I expect for the tail to be updated to the last reference, which is the 2.

[00:01:48]
>> Bianca Gandolfo: So I'm gonna update that and then I expect this next to no longer point to 3. So I would take this
>> Bianca Gandolfo: And point it to null, which would thendDo the same thing here. So these are the same, they're the same object. I just draw them out separately for visualization purposes, okay.

[00:02:16]
>> Bianca Gandolfo: So that's what I'm expecting to happen. So reassign the tail and then give that tail's next the value null. Any questions about that, Why we would do it that way? Okay. So, I'm going to bring this up with this so, we can have our notes.
>> Bianca Gandolfo: And I would do this in an interview.

[00:02:44]
I would take my notes. Whatever I needed to like solve it, I would just take it. Whatever I'm doing here in front of you right now is exactly what I would do in an interview. Including, explaining everything that I'm doing, all the considerations I'm making as I'm reasoning about this, okay.

[00:02:59]
So we're gonna remove the tail. So the first thing I wanted to do is I wanted to update the tail, so this.tail.,
>> Bianca Gandolfo: So then, I need to get the thing for the tail actually. So if I wanna get the thing before the tail, without a reference to the tail.

[00:03:24]
That might be tough because. So basically since what I wanna do is I need to figure out what.
>> Speaker 2: Previous values.
>> Bianca Gandolfo: The previous values.
>> Speaker 2: Original.
>> Bianca Gandolfo: Of this one. And you can't really figure that out based on the data that we have right here, right? So, the only thing that we know about this value of this node is that it has the value of 2 and it has next pointer of null.

[00:03:56]
We don't know that this then belongs to the next of value 1. We don't know that from this information. So there are a few ways we can go about it. The most straightforward way is what I was saying before we have to loop through it. And so.
>> Bianca Gandolfo: We can loop through it, and then once we get to the one right before the tail, we'll have the node that we will need.

[00:04:32]
We need to find the node right before the tail. So let's remove the tail
>> Bianca Gandolfo: So the first thing I wanna do is loop and find the node before the tail. So how do I know it's the node before the tail? Because I think the node.next would equal this.tail.

[00:04:58]
They would be the same node, and we can do the === because we're using objects, and we wanna make sure they're actually the same object, not necessarily the same value. Our link list could have multiple objects with the same value. So we're just gonna check on the node, and in general it's kind of a best practice unless you're actually Interested in dealing with the values like maybe you're finding duplicates or something like that but in this case we're dealing with nodes, a whole node.

[00:05:28]
Okay, so we can say while,
>> Bianca Gandolfo: So this is actually a
>> Bianca Gandolfo: Traversing a link list is a thing that you should pay attention to. So what I'm about to do is what you're gonna have to do a lot for link list questions, which is traverse them forward, traverse them backwards, traverse them with two pointers, traverse them with one pointer.

[00:05:52]
So all of these traversing things, you can't just for loop through a link list. It's not like an iterable data structure or anything like that, no for each, for real this time, so while, so we're gonna say currentNode = this.head.
>> Bianca Gandolfo: Okay, so we're gonna say, while we have a current node, because it's either gonna be ideally, if we implement it correctly, it's either gonna be a node or it'll be null.

[00:06:29]
Once it's null, we know that we're at the end or we could say, while or we could say when. So while currentNode is not equal to that, that actually is probably better for what we need. So while currentNode does not equal, so while currentNode.Next. So while does not equal this.tail.

[00:07:02]
So once
>> Bianca Gandolfo: Once this condition is met where our current nodes.next is the same as the tail. We know it's the second to last node. Does that make sense?
>> Bianca Gandolfo: So this so that we don't have an infinite loop, so every time we loop we're gonna set current node to currentNode.next, so then it will just keep going and going through all the next properties.

[00:07:38]
And once we are out of that, then we know where we need to be. And this is when we can do the deletions. So we know our currentNode, we wanna be our tail. So then we can say this.tail = currentNode. Is that everything? I feel like I'm missing something.

[00:08:02]
>> Bianca Gandolfo: So, and we wanna make our currentNode.next at null.
>> Bianca Gandolfo: Right, we need to make sure we remove that pointer
>> Bianca Gandolfo: All right. Questions?
>> Speaker 2: So, line 38 is really looking for the penultimate node. One right before the tail.
>> Bianca Gandolfo: Yeah, exactly. So it's gonna keep looping when this breaks out.

[00:08:39]
That means that the currentNode's next is the tail.
>> Bianca Gandolfo: Does that make sense?
>> Speaker 2: Just not much.
>> Bianca Gandolfo: Okay. Yeah that's kind of a wierd one. So while it's not that, keep looping, once that condition is met we won't enter that loop anymore and it will continue down here.

[00:09:04]
The other thing is what if the currentNode.next is never the tail. Is there a case where this condition is never met? Let's noodle on that. So current node is gonna be the head. No, it should always exist. That's a condition that you would consider because that would give us an infinite loop if we're not meeting that.

[00:09:30]
But it seems like the way that we implement it that we wouldn't run into that. What else might we think about?
>> Bianca Gandolfo: All right ready for checking some bugs? Let's see what happens. So we want we're expecting it to look like this. This is still true yeah. So let's move our console log down.

[00:09:58]
>> Bianca Gandolfo: Moment of truth, uh-oh, I think we deleted everything.
>> Bianca Gandolfo: Let's see. I think we're exiting one too soon perhaps. So hold on, we have our 1 and then we insert our 2, insert our 3. Let's compare before and after and make sure. So we have 1, 3.

[00:10:26]
Are we?
>> Speaker 2: Missing two?
>> Bianca Gandolfo: Where did two go?
>> Speaker 3: Did we change the
>> Bianca Gandolfo: Did we change something?
>> Speaker 3: Because you added that pad plus one right?
>> Bianca Gandolfo: There we go. Yeah, no problem. That's why we were testing it early. Okay. Okay. All right. Great. So what was it, okay so this.

[00:11:04]
>> Speaker 2: So we have 1,2,3 and then we have 1 and 2 are pointers no. Cool, I'm surprised it did that on one pass. I was like this could go wrong in so many ways.