Linked List: remove, get, & removeAt

[00:00:00]
>> All right, so this is kind of an interesting one that Java did. I don't really love this one, but it's kind of a fun one in the sense that we have an item T in which we need to find list, then we need to remove it. So you'll see that this is this is available.

[00:00:18]
A lot of times when you're using a list operation, you may not realize how bad this performance could be. My guess is that Java's really, really smart, and they do something like also include HashMap as well underneath the hood. So when you look it up by item, it can instantly look up where this node is, and then delete it out.

[00:00:36]
To me, that seems to make most sense. But we'll see what happens here, all right. Maybe maybe not. Actually think about, maybe not. All right, so well, what was I doing? Yeah, so we'd need to do the same thing as get, or remove at, or an insert at.

[00:00:54]
We'll need to do the whole let curr = this.head, for (let i = 0, i <, We don't even have to do that at all, this outline. Nice, and of course we need the check for current being something. We're gonna keep on scrolling until we get to the end, or currents does not exist.

[00:01:14]
But I guess you don't really technically have to do that, but for the case of TypeScript, we have to do it. Because if i is less than length, current better be a real object, or we've completely screwed up our implementation. But again, TypeScript doesn't really like it. Next, right?

[00:01:27]
So if current does not, let's see, curr.value is not equal item, or I guess would be the other way around, right? If it does equal the item, we have found it, right? Yay, we're good. So we can break out of here. I guess we could put something in here.

[00:01:44]
We could do it like a current value and a current value of blah, blah, blah, blah, we'll just keep it like this, very easy to read. Awesome, so current value equals item, we break, else we're gonna keep on scrolling current until we go to the end of the list.

[00:01:57]
If there is no current, there is no item to remove, right? That makes sense, so we're done, we're out of here. But if there is one, well, now we have to actually do something about it. So how do we do it? Well, since we're not involving ourselves in this circular list item, what we really need to do is think about the three possible conditions, right?

[00:02:22]
Really, there's only one condition, we're just gonna have to do some IF guards around it. There is the node we want to remove, and possibilities of being pointed to, right? So we're gonna need to take whatever this is that's pointing, and point over. We're gonna need to take this one, whatever it is, whether it's undefined or not.

[00:02:41]
If it does exist we're gonna want to point through. Then at that point, we can break these links, and we got it. So this is really just deletion in the most general sense, so we can do that. So we'll go like this, const, or we already have current, which is the thing we're gonna want to delete.

[00:03:00]
We can now go like this. Let's go, this.length- -, do some book keeping, awesome. We can do kind of a shortcut if we really wanted to. If length = 0, then this.head = this.tail = undefined, awesome. Return, nothing left to do, we're good to go, this is great.

[00:03:22]
Still, lot of IF conditions are about to happen, so then let's just have some fun and do it. We're gonna break it up a little bit differently. So now that we have this, let's just do that general case. First, let's see if the things previous. If we have a previous, let's set our previous to our next.

[00:03:39]
If we have a previous, we need to set it to our next, right? We need to hop over, that's this top branch right here. So if (curr.prev), then curr.prev = curr.next. That makes sense, right? And again, the other direction, if (curr.next), then curr.next = curr.prev, so now we've officially removed our current from our linked list.

[00:04:08]
If we started our head now, we would not run into current, unless our current is currently our head, right? We need to do a little bit of extra updating at the very, very end here. So now, we're gonna take our curr.prev = curr.next = undefined, now we have broken current from the linked list.

[00:04:26]
So now we should theoretically have two separate lists going on right here, current, which is all by itself, and the rest of our linked list. So we can do couple extra checks, if curr === this.head, well, then that's bad, right? So we can't quite break that, can we?

[00:04:45]
No, we can't. See, operations become very obvious right way that you've done something wrong. this.head = curr.next, right? Move it up in the list. And then this, let's see it, all right, that's good. Or, if curr === this.tail, exact same thing except for the other way around, this.tail = curr.prev.

[00:05:10]
We'll walk it back one step, just to make sure our tail or our head are now pointing at the newest item. And then lastly, completely break it all off, you don't have to do this in the JavaScript land. JavaScript automatically clean this up for you. And then finally, current.value.

[00:05:26]
Awesome, I think did goof up one return right here. Yes, so const out = this.head.value, Awesome, there we go. There was that one that we goofed up. Did we goof up any other ones? Yes. There's that as well, right? Because we're supposed to return alpha value. So we're kind of chugging away at this point.

[00:05:52]
We've gotten pretty far out, and now you can pretty much imagine that we have made it to the last and final parts. It's feeling so close, we're really happy that we're almost done with this linked list. But there's a couple more loops we got to do. So instead of just doing this, we could probably generalize this, don't you think?

[00:06:12]
Don't you think that we don't need to keep doing this over and over again? Martin Fowler's rule of three is usually what I deal with. Since we have one here, and we have one, wherever insert is, here's insert. We have one right here, that means we can probably do something a bit smarter, don't you think?

[00:06:30]
So let's just take all of this out and use the old rule of three. I like the rule of three, it just makes me feel happy when I do it. All right, so do this thing. But we can't quite do it here, this one is kind of unique.

[00:06:42]
Now that I think about it, we can't actually do it here. I thought we can do it here, it's actually here that we can do it. So we'll just pull it out either way, private getAt, and so this will be an index number, awesome. And we can go const node = this.getAt, index.

[00:07:05]
If node does not exist, return undefined, actually we don't even need to do that. I'm just gonna go return node, my goodness, TypeScript. There you go, that's beautiful? Can do value, and really we don't even need to do that, we can actually just, there we go, beautiful, right?

[00:07:30]
We have this nice thing nicely done put it down, and then we can go back to our insert and just take that out as well, might as well, right? const curr = this.getAt index, and if, this should always work. So we can just take this last little bit right here, right?

[00:07:51]
That's what we're doing right there. Cuz we already know of course, we've already done all of our own personal bounce checking. We already know everything's good, so we can just rip it right out. Do that, awesome, awesome, awesome, we have now achieved full on, we will achieve at least full on rule of three, so here we go.

[00:08:07]
removeAt, exact same thing, we need to remove this thing at a specific index. So let's go like this, const node = this.getAt(idx), if not node, return undefined, right? There's nothing left to do, we've already found the node, or there's no node to be found, we don't need to return anything.

[00:08:29]
But again, this is where that inner software engineering me, like can't even do it. Even though it's not rule of three, it's only rule of two, I feel like this removal logic is just so awful. I'd rather kind of abstracted out, I don't know what it is inside of me.

[00:08:43]
This probably happens to you, too, where it's just like you can't even handle the fact that that exists, that's at least how feel. So we'll have removed node, node, node, T. Awesome, we know this thing exists. It's gonna return a T, fantastic. And this one's trying to claim, that's not going to return the T, we'll just go like this, went on.

[00:09:08]
There we go, and now we just need, the current needs to be replaced as, current node, awesome. So, there we go, we've just generalized this function really quickly, pulled it all out, I wasn't actually technically planning on doing this but it just feels right to do it. I can't actually not do it, sometimes it's how feel.

[00:09:28]
So there we go, we now have this removal of the node, which means that our remove at and are removed can now share the code. return this.remove node, curr, very great, and then of course remove at, we can do that as well. Awesome, so we pretty much have everything written except for one last little bit, which is our get function, which I deleted and didn't keep.

[00:09:52]
So we'll just write it really quickly, curr = this.head, for (let i = 0. If you guys were smarter than me and you actually kept it around, good on you, I don't do that. that.length, It's trouble sometimes. Curr = curr.next, there we go. return curr, there we go.

[00:10:20]
So we've actually gone through and we've implemented every last detail when it comes to this linked list. So I know that was a lot. I see faces of, my goodness why would you do this to us? I'm sorry I didn't, this is why I tend to want to skip this section cuz it's just so big, it's hard to see why it's so complicated.

[00:10:41]
But it's really not complicated at the same time as it is super complicated. And think this really goes to show you that if you have the wrong function interface, it can make things a lot more complicated. I chose the Java one just because I figured most people would be at least familiar with that, and yes, it causes some level of headaches.

[00:10:59]
So the JavaScript one would have been lot easier, cuz I would have had unshift, shift, push and pop, then we could have skipped splice and slice, and reverse and all the other fun stuff. All right, so there we go. So that is doubly linked list implemented in sweet, sweet, TypeScript.

[00:11:19]
Is there any questions?
>> Can you go to the Insert ads?
>> Yeah.
>> So line 17, I think?
>> 17 offset?
>> Yes.
>> Down here?
>> Yep, is that supposed to be-
>> I think you're right, hold on, insertAt, Now you got me all night, wait no, no, no.

[00:11:54]
>> I think you're right, hold on, did I just goof that one up on that? Now you got me all questioning though. Did do this one part wrong? Let's find out, node.next = curr, so we point to that one, node.prev = curr.prev. Awesome, so we have our two correctly attached ones.

[00:12:11]
So now we need to get the reverse out, right? So that means our current previous, the one that we are used to be pointing to, which was B I believe in the example, now needs to point to the node. Which also means the current previous next needs to point to the node.

[00:12:31]
>> Node, yeah.
>> Yep, and so we can also say it as nodes previous next needs to be node. Right? I think that's what I had. No, I didn't have it. I had it, you're right, so it should be node.prev, Nodes previous which is current previous, that previous' next need to point to the node.

[00:12:56]
So that way our two-way linking is correct. So our previous next. Right okay, you're right. Good eye, I can't believe you spotted that one, that's just so astute.