Linked List: prepend, insertAt, & append

[00:00:00]
>> So we do have time to implement the linked list. So, let's actually implement it, I'm gonna add here to this interface right here. And so we are gonna actually do all of these, some of them are a bit trickier actually did take the Java interface. I know no one likes Java anymore.

[00:00:15]
It's not that cool to like Java. But hey, Netflix uses a lot Java, so it is cool to like Java. That's what I told myself as we did this. So let's go over here, let's go to our coding machine. And let's open up linked list. If you wish to join in, we will be doing a doubly linked lists because they are doubly, a singly.

[00:00:34]
It's true, mathematically checks out. No one can argue that. All right, so I actually nicely have everything kind of generated for you right here, I believe. I think maybe we may have written this at some point but there we go. So here's the doubly linked list. Let's go through this and actually fill in all these operations.

[00:00:52]
All right, just a side note, I did at one point implement this right here, this get. So I'm just gonna remove that right now, just so that way we implement it continuously. You know what I mean?
>> I just wanna say Java is cool if you like money.

[00:01:07]
>> Java is cool if you like money. I like money. You like money too? We should be friends. That is a shout out, of course, to everyone's favorite movie Idiocracy. So, here we go. So often whenever I'm doing constructor, I like to explicitly set things, so let's do head undefined, even though we don't actually need to do this.

[00:01:24]
So now if you remember when it comes to link lists. All right, so to be able to do prepending, you may remember the operations. Let's jump back over to our diagram right here, and let's just kind of walk through just one more time. So a prepending does involve the head in which we're gonna need to be able to set in a new node at the heads position.

[00:01:41]
Which means, let's just call it G and what we're gonna wanna do is we're gonna want G to point to A first. Then we're gonna want A to point to G. Then we're gonna want the head to point to G. We're gonna kinda wanna do these in this operation.

[00:01:59]
We don't want to lose A in our memory. We don't want to lose any of these things. We wanna keep these operations in order as much as possible. So, let's do that right now. So if we're gonna prepend something, we can start off by first creating the node, right?

[00:02:12]
The node, of course, is gonna be a value item as Node T, great. So now we have the node and there's always is technically two conditionings to a prepend or any of these, which is if there is no head, right? There's nothing here, we don't have anything, we can just set this as the head, right?

[00:02:30]
We don't need to do anything fantastic. So this .head = node, perfect. And before we do that, bookkeeping, see I just forgot too. It's so easy to forget bookkeeping, this.length++, right? Cuz we want to be able to know how many items are in this list. Okay, so if that's not the case let's do those exact steps again.

[00:02:50]
Remember, G points to A, A points the G, head points to G, we'll just do those three ones. So, let's go like this, node next points to our head or in this case it was A, in that case, right? This.head.previous points to node. There we go, we've done the two directions.

[00:03:13]
Now this.head = node. There you go, we've now just officially prepended. There are ways to make some of these operations a bit easier in which we're not going to do. Let's just remember that that there's this circular linked list that will make some of these operations a bit easier.

[00:03:31]
But I'm just not gonna worry too much about that, we'll just kinda do it the old fashioned way if you will. All right, so now we gotta do insert at. Insert at is the exact same thing except for now, we're gonna be doing it within the middle. We'll be doing the F operation right here, which is gonna involve us pointing to the node we want to insert at.

[00:03:51]
Then that node, then we gotta make sure we point to the other node and do all that. So let's write this out, it's way too confusing. I realize I don't have hands for four points, and there's just no possible way I can actually get that done. So let's just write this thing out.

[00:04:05]
So, we'll rewrite it out as C, B and D. And these are two way links. And we want to insert at C with F, awesome. So F needs to point to C as the next, F needs to point to B as the previous. Then C's previous needs to point to F and B's next needs to point to F, there we go.

[00:04:37]
We have broken the chain in that order. First, attach the new node, second, break the old links. So long as you do it in that order, you're not gonna goof anything up. It's pretty easy to tell when you've goofed something up cuz as you program you'll realize, crap, that's not gonna work out at all.

[00:04:52]
So long as you keep that in your mind, it's pretty easy. But remember, this is insertAt which means we also need to traverse the list. So that does make it a bit harder. So we can go like this, let curr = this.head. Well, technically, since we're building our own list, we can actually add a better interface.

[00:05:10]
So, if our index is greater than our length, we kind of have a problem, right? We can't really insert at that point, can we? So, what would be a good move here? I would probably just throw an error, right? No, right? You can't really do it at this point.

[00:05:30]
I don't know what else to do, right? Your are two nodes off. Should we create two dummy nodes with no values in them? No, we're probably gonna screw that up. It's gonna make our logic a lot more complex, probably the right move to do. Well, there's actually something else that makes this a little bit interesting.

[00:05:45]
What if our index is the length? Well, we're really just appending to the list, right? So I mean, we can technically just call append, right? Yeah, why not? What if our index is zero? Well, we're just really just, oopsies, just prepending it, right? We've already written those too, all right, fantastic.

[00:06:14]
We don't really have to concern ourselves with the edge bookkeeping. This is where a circular linked list would actually avoid this kind of conditioning. But we're not gonna worry ourselves with that, there we go. So now, we have our current and now we need to simply just walk, right?

[00:06:29]
We're gonna just simply walk until we get to the index, and then at that point, we will have the node in which we need to replace. And there's things that we know that TypeScript doesn't know, so we'll have to do a bit of casting. So let i = 0, i has to be less than index, ++i.

[00:06:44]
Curr = curr.next. And of course, we also have to make sure current is actually a thing as we get there, or else we're gonna get mull exceptions. I mean, technically we won't cuz we actually pre prepared for this by using our link to do all that. But TypeScript knows nonetheless.

[00:07:03]
So now that we've done that, we can go curr = curr as Node<T>, little, TypeScript magic right there, I guess. I'm not very good at TypeScript, so for all the TypeScript ninjas out there that are probably laughing at how I'm doing this. There we go. So, we now have current, it is a node.

[00:07:22]
Now we need to insert our new one. Remember, the first thing we do, is create a node and attach it to the positions we want it to be at. So, node = {value: item} as Node<T>. By the way, if you don't, I find this thing right here, this little plug in, I can't use my mouse.

[00:07:41]
Sorry, I didn't realize I can't, this little one right up here, that says insert, it's kinda nice, little, fun plugin. I think VS code now just finally got this, which is you get context of where you're at. So if you're zoomed in, you can see your function signature.

[00:07:53]
It's pretty, pretty nice. Highly recommend using it, it's good time. So we can actually, I'm not gonna put it inside the constructor or inside the node creation. I'll put it right here. But node.next, now needs to equal the current we're going to be inserting at, right? Because in our diagram, we actually put F before C, correct?

[00:08:13]
We didn't put it after C, we put it before C. So let's go node.next = curr, node.prev = curr.prev, right? So we've now attached our new node. So now we need to break the previous links and point them correctly at our node. So we can say this, curr.prev = node.

[00:08:38]
And then the last one which is a bit more confusing, we have like this. If (node.prev), if that actually exists, which we do know it exists, but we'll just say if it doesn't. Based on our little looping or based on these little condition up here it has to exist, but for TypeScript's sake, we'll go like this.

[00:08:55]
We'll now say, hey, that one, we need to make sure also does the correct thing. I think we have to do it this way, curr, there we go. If the current's previous is there, we need to do something with it. So curr.prev.next = curr. So, do you see what we did there?

[00:09:13]
So it's a little much. It's current's previous, next, needs to point to F instead. Current, previous, next, you just have to kind of run that triangle there for a second. And so that is a one way to do this. You can see that we have a lot of options.

[00:09:33]
We have a lot of links. There's different ways we can do this. We could have even created a previous node and just do it that way. But this seems to be pretty straightforward one for me, I guess. Hopefully that all makes sense mostly. All right, so let's do append.

[00:09:47]
Append is also pretty easy. Hold on, I guess did I take care of bookkeeping? We didn't take care of bookkeeping classic, right? There we go, we've taken care of bookkeeping, we make sure that we increment the length as we walk. Actually, we need to put that down here, don't we?

[00:10:08]
Yeah, because append and prepend should do their own stuff. There we go, sorry. Bookkeeping, always just the worst, never liked it. All right, so appending, it's pretty much identical to prepending. We're gonna go in here and we're gonna go to the end. And as always, attach the node, update the links, right?

[00:10:25]
So if we did, let's do Z over here. We would, of course, attach to D, D would then attach to the Z. And then the tail would be updated to point to Z, correct? Now one thing we don't have in here I just realized is I completely forgot to put in tail.

[00:10:44]
So we do need to do something with tail at this point, correct? So let's go tail, we now add that thing in by putting a tail right there. And that means our prepend also needs to have the same logic in it as well. Might add on that one, there we go.

[00:10:58]
If there's nothing in it, we are an empty place, then let's set everything to the first node that comes in. And we have to do the same thing on prepend as well or append. That's the first one, we need to make sure our tail and our head both gets set at the same time.

[00:11:11]
All right, so we'll go back down to append. So what are the conditions? First, bookkeeping, bookkeeping, bookkeeping, bookkeeping. I told you this one is like, it's really lengthy to implement, right? There's a lot of little conditions in linked list that is shocking because they're very easy to use.

[00:11:29]
They're very uneasy to implement. All right, so now we need to simply do those operations. First, create the node, attach it to the tail. Then tail to the node, there you go, right? Just kinda do the two ways. So let's go, const node = {value: item } as node T, most excellent.

[00:11:54]
If there is no tail, well, same condition, this.head = this.tail = node, return, right? It's the first item to be put into this list. Awesome, we got it, everything's good. Else, we need to do something now. We need to take our tail and we need to point to it.

[00:12:13]
So, node.prev = this.tail. We have now pointed to the tail. Now the tail needs to point to the node. This.tail.next needs to equal node. Now we need to update the tail to point to our newly added node, this.tail = node. Everything's good? It's a lot of links here, people, a lot of links.