Linked List Data Structures

[00:00:00]
>> All right so we're actually on to the second data structure is everyone filled with exuberance, joy, happiness, okay good so I did say something weird earlier of course with it which is this statement in JavaScript Is not an array. Now we have a pretty solid definition and understanding of an array, let's see is this thing an array?

[00:00:27]
It's not an array, right? We can tell it's not an array because you got push you can grow it, right? It can grow at infinitum, right? So something's happening on top of an array minimally, right? Can we at least say that, there may be an array underneath the hood somewhere, but somehow we have the ability to add, we have the ability to insert, we have the ability to delete from, in which all the indices are actually being adjusted.

[00:00:52]
Because if I shift, an array, the first element in the array becomes the zeroeth element and so therefore something had to happen because surely arrays don't offer that if you delete the zeroeth element you know it out you zero it out And one is still one, correct? So something is happening.

[00:01:10]
Something more than just an array is happening. Some sort of organizational structure around this happening. All right, so I'm sure some of you are getting pretty offended by all this talk. Yes, I wanna say HTML is not a programming language. Neovim is the greatest editor. Rust is the greatest language.

[00:01:24]
And Linux is the only machine you should develop on. Hot takes for everybody, but let's keep on going. Go to our first real data structure. The reason why I'm calling it the first real one, is because, arrays just don't feel real in some sense, right? They're so raw they almost feel like a primitive of computing, right?

[00:01:41]
They don't necessarily feel like they're something, but I mean there is a lot of things happening underneath the hood. Nonetheless it still feels very wrong. So, let's keep on let's go I did have this funny joke in here which is it's available on pretty much every language except for JavaScript.

[00:01:58]
Anyway, so what sucks about an array? Deletion, well, you can't really delete right? You can zero out something. Insertion, well, you can't really insert you can, right? It's ungrowable, why? Remember Fred EFS and chat for Fred because F went away. So, let's talk about linked lists. Okay, so this is really, our first real data structure, they often call this a node based data structure.

[00:02:21]
No not node, as in the runtime for JavaScript, node as in the type of container that will wrap our data. So let's talk about this. This is pretty fun, this is where things I think get really fun, cause now we're actually getting into really the heart of the beginning like the very the first ventricle if you will of data structures.

[00:02:44]
Wow what an analogy, of a doctor practically all right. So, in a linked list how you can think of it, is that, if you have a series of values, Oops this B, nice writing. What you're going to see, is that you're going to see data organized in such a way that, you will not only be able to visit say this node it will point to the next node.

[00:03:09]
Which means that, things like get I, obviously work a lot differently, right? You can't just get the eighth structure. What would you have to do? Well, if you start here if this is our head our first element, we literally have to go okay, 1,2,3 all right we wanted the fourth item or the third index there we go we just got it we can return out this value.

[00:03:34]
And the reason why I draw circles around this, is that, it's often a container item. Meaning that you hand me a value T, and I put something around it. So, that's why I called a node based one. So imagine you have a type definition and type script, which is generic over T.

[00:03:50]
What you'd see is a value, which is going to be of type T, and say a next, which could be an undefined value of another node. My goodness. So this was the first algorithm that blew my mind. You can see us allocating and walking memory. I thought this was just like the coolest thing, I hope you feel the same way.

[00:04:13]
This is like the coolest moment in all of my programming career that I can really tangibly remember, is being able to see this in my head and how it worked. And yes I did see in Java at that point please don't make fun of me, but that's just how it was, everyone first language is sometimes unimpressive.

[00:04:28]
So, there we go. So this is how a linked list fundamentally works. Is that you have a node that contains a value and a reference to another value or to another node. And so that way you can walk this daisy chain, if you will, of nodes which contain values.

[00:04:46]
So, A double if this is to be considered a single link list. Why is it considered a single link list? Cause A point to B, B points to C, C points to D, you can't walk backwards, right? The moment you go forwards, if you don't have a reference to what is behind you, you've lost it forever, right?

[00:05:02]
It's gone. If I take head, and just pointed to here, no one's gonna be able to access A, right? It's just gone, right? Hopefully I believe JavaScript garbage collection is so super advanced it actually even collect A because it can tell that though it references data that still is alive Live it itself has no references left therefore dead, right?

[00:05:23]
Now a doubly linked lists, usually comes with an additional property, previous node. Which means, we start getting bi directional arrows, right? With this we get the bi directional nature of a node which means we can go from A to B and from B back to A, right? We can keep on walking back and forth because we have these links right here, you are referencing the next item.

[00:05:47]
And so often they call this a container, right? Because you, the linked list owner, is going to say handed a series of numbers, but it needs the ability to store and organize these numbers within the linked list. So creates a container to put them into and then be able to manage it that way, does that make sense?

[00:06:05]
So instead of using an array, it uses a heap allocated objects, and puts them. Heap allocated objects of course mean objects that are stored in some magical memory place, which is usually more expensive than stack. That's a terrible definition but go with it. All right, so now let's talk about deletion and insertion.

[00:06:22]
So, one cool property about length lists is that deletion insertion can be very very fast. So let's just say we wanted to insert into here F. What do we need to do to insert F? Well, remember, A points to B. So, let's make A point to F. F needs to point to A.

[00:06:43]
Remember because we have a previous and next we're doing a doubly linked list. This would obviously be less operations in a singly linked list, but you get the idea. Now we have another problem. B, where does it point to? Points to A. Can A point to A? Just can't.

[00:06:56]
Right? We have broken off this link but we still have this one. So B, needs to point to F and F needs to point to B. At this point, what has happened? We have effectively moved everything over and inserted F. But here's the cool part. What did we have to do?

[00:07:17]
Well, we had to set a bunch of nexts and previouses, right? Like that's it. Or any of those operations based on how many nodes are inside the linked list? No, are they constant time? Setting next is that constant effectively, right? We can assume that it's constant. You could argue that in TypeScript or in JavaScript, looking up a property on a value could be this under these conditions.

[00:07:42]
Let's just forget all about that and just assume that this is a more traditional style. If you set a piece of memory on an object, it is constant time, right? It's an offset into the objects that's the memory boom, there we go. So if we set 2 nexts, right?

[00:07:59]
Because we set As next to be F. Let me write it down here. We say it As to be Fs, we said F to be B, then, we have to do the two previouses. We do B, has to be set to F and F, has to be set to A.

[00:08:17]
All those operations are performed constantly, right? It's just setting a property, therefore to insert inside of a linked list at a given position is of 1, right? Nothing, is based on input, no matter how big the value you give me, no matter how many items are in the list, none of that matters.

[00:08:37]
It only matters that at the break for links, and yes, those each can take some amount of time. That's why like I said there's always a constant we dropped the constant it does not matter that there is a constant practically speaking constants can matter. But in this case, it doesn't matter.

[00:08:51]
So there we go. We actually created a doubly linked list, and we were able to insert. So, let's think about being able to do the opposite. If we wanted the delete C, what would we have to do? Okay, we have C, we have C the node. Let's pretend we got C in some constant time, or we just had access to C.

[00:09:11]
So, we're not considering how we got C. We have C and we want to be able to, delete it. So what we're gonna have to do, is the first thing we're gonna need to do is we're going to go from C, to B, back to C and break that link, all right?

[00:09:28]
We don't want to do that, we now have access to B. We're gonna have to break the link from B and we're gonna have to point it to C which points to D, right? We're gonna actually have to point through C's next to D, right? So we're gonna have to go back, take its next and point to my current ones next.

[00:09:46]
Do you see I know linkless are terribly hard to implement and you often get it wrong your first try, right? So if you think about that, practically speaking in more kind of code, since if you had access to C, I'd say C previous, equals B, right? B next, equals C next.

[00:10:09]
Does that make sense? Like what I just did there, is I broke the link from B that points to C and now pointed to D. That makes sense, right? I think that makes sense,
>> Would you put C next? And why not just put D?
>> Well, the thing is you have to first get access to D, right?

[00:10:28]
So I first have to go like this, D equals C dot next, right? Then, I could replace that with D, so that is equally valid as well. But remember, we're now using memory and we're now playing around with these linked lists, so it does require us to be a lot more specific at all points.

[00:10:44]
So hopefully that sort of makes sense. I mean, this is obviously a very hard concept the first time you see it, but you can see that these nexts and previouses, you have to be able to manage the links yourself and that really is just setting where they're pointing to.

[00:10:56]
>> So, linked list, there's no index, you can't?
>> Question was, in linked list there's no index, correct. There is no index you have access to a node in which you can traverse to get to the node you desire. Now there's ways to do fast traversal and things like that.

[00:11:10]
We will get to that at some point. But in the current moment, we're just looking at it in a traditional kind of sense. Just a linked list, as is doubly linked to make it kinda obvious, singly linked are really easy to implement, in comparison to W. Because W have to do this whole back and forth business.

[00:11:27]
Alright, so there we go. We just set B, to point to D, right? So now, we have D, point to B, right? So now notice that these operations, the operational order is extremely important, because if I said As, see that next year undefined, could we ever access D again?

[00:11:47]
No, D is gone, we can no longer ever access it again so it. Operation ordering of operations is extremely important. All right, so then the next thing that you have to do, is D dot previous would have to be C dot previous, right? So now C or D now points to B, right?

[00:12:05]
We just did B to D, D to B, I wish i should have chosen different letters because they're so close. Bravo to delta, delta to bravo, there we go we now have them together and so now we need to take Charlie over here, I guess. Wow, DCB, they're terrible letter names here now that I think about it.

[00:12:21]
Alright, we're gonna take Charlie here and we can go previous, equals next, equals null, right? It's, we've taken it out of the graph, right? We're deleting C out, so yes D and B now point to each other, therefore C needs to be taken out and no longer pointing to anything and at this point if we want to return the value we could just simply return you C dot value, right?

[00:12:47]
So there we go, does this make sense? I tried to kind of break this down into this most fundamental operations, this is a deletion. We can also go over it again with insertion and actually do the writing of the values, we will code this no matter what at some point but this is, the fundamental value right now.

[00:13:04]
Are the fundamental operation. Does this all make sense? Is everyone on the same page? For the most part, awesome. Alright, so that is a linked list. So again, let's think about the running time of a deletion. Is any of the deleting part right here based on how big your input is?

[00:13:24]
Now, is it based on how big the value of the notice? No, it's not based on anything, it's based on four links. Is four a variable or a constant?
>> Constant.
>> Confidence right there. Yes, it is a constant and not only that is setting next and previous is that a variable length operation or is that a constant operation?

[00:13:47]
It's constant operation, right? Because setting something to undefined requires going to the memory and setting it to undefined computer super fast going to memory, we can just assume it's a constant operation though it's very, very complex. It's nonetheless, very, very constant. And so therefore, the leading is constant time.

[00:14:03]
Just like insertion is constant time. We do the same amount of operations no matter how big or small the list is. Awesome? Hopefully, now obviously if you're really actually programming this you'd have to put some like guards around this like right if you know B is real then you do the whole next thing if D is real then you have to do the previous thing.

[00:14:25]
But in our sweet pseudocode I will always be dropping undefined checks and things like that just because it's super hard to be able to write pseudocode and actually write really concrete correct code. So just be okay with things that are like that. Does this all make sense? Are we good with this one?

[00:14:43]
So there we go. This is a linked list.