LinkedList

[00:00:00]
>> So let's pop over here to LinkedList. LinkedList, instead of having everything co-located in memory, so it's all just one after each other. Basically, you kind of embrace a little bit of chaos and say, well, they're gonna be all over memory, but basically, we're gonna have nodes. Let's say, okay, this node holds 22, this one holds 2, this one holds 77.

[00:00:21]
And they just point to each other in memory, right? So, 22 doesn't know about the rest of the list, all it knows about is where the next thing is, right? 2 doesn't know about anything else besides where 77 is, right? And they just had these nodes that point to each other.

[00:00:38]
Now, this makes it hard for reads, right? Because if I wanna get index 10 over here, I have to follow the entire chain to get there, right? It's not necessarily ideal. But you can see here this is doing an add. And the adds are really great, cuz all you have to do is you add something.

[00:00:55]
Let me just step through here. So, yeah, here, this is doing a find, until it finds where it's supposed to go. And then it's going to land right here, right? So, we create this new node. All we have to do to add this between 43 and 76 is, move the pointer for next from 76 to 50, and then add 50's next pointer to 76.

[00:01:20]
And all of a sudden we've added something to the middle of the list, right? By the same token, if we wanted to do something like delete 43, all we'd have to do is go to 6, change its next pointer to be 76. And all of a sudden it's totally deleted from the array.

[00:01:35]
We don't have to do anything else, right? So that's the distinct advantage of LinkedLists, is that it becomes very easy to delete and add things in the middle. [INAUDIBLE]. All right, so with LinkedLists, we're gonna have two classes that we're going to implement. We're gonna have like a LinkedList class, right?

[00:02:02]
Like we had an ArrayList class. We're also going to have a node class, right? So, the node class is gonna have two things on it. All it's gonna have is next, and the value, right? So, again, this 2 node right here, has a value of 2 and a next of the 77 node, and that is it.

[00:02:23]
It doesn't know about what's before it, it doesn't know about what's after it. By the same token, the LinkedList class, all it has is the head, right? So 22 here is the head, which is the first note in the array, and then it doesn't know where everything else is, right?

[00:02:40]
So you have to follow it, to try and get that. So, let's dissect the delete really quick with a LinkedList, right? So we have these notes here, so [a] and these pointers, right? So let's say that we wanted to delete index 2, which is this one here, this one that says [c] in it.

[00:03:07]
We'd first seek or do a get till we get to the [b] here, right? Then we will change the [b] to be the next of the [c], right? So that [b] now points to [d], and then that's it. Decrement the length, return the deleted node, and that would be it.

[00:03:33]
Same things if this is doing an insertion up here between the 43 and the 76, you find 43, you point 43 to 50 and then you're done. And then, well, and you point 50 to 76. So, the lookups on a LinkedList are n, right? Because you have to loop through the entire list until you find the thing that you're looking for.

[00:04:04]
The gets and lookups are not great. However, the deletes and the insertions are constant time, right? Because all you have to do is change your pointers and you're done. So, again, if you're deleting and inserting into the middle of a list, LinkedLists are amazing. But if you're doing a lot of reads and not doing much modification of the list, then don't use LinkedLists.

[00:04:28]
There are variations of LinkedLists, as well. One of those is a doubly LinkedList, which will have a next, but it will also have a previous, right? So, if you can see that something is going to be closer to the end of the Linked List, you can start on the tail and then backtrack to find the thing that you're looking for.

[00:04:46]
So, it kinda helps a little bit with those, gets, right? You can never have to go more than half of the array. But, at the same time, instead of just having to change, next, you'll also have to change previous for the insertions and the deletions. Do I have any practical use cases for LinkedLists?

[00:05:10]
I think the answer for JavaScript, it's basically, never. You would almost never implement this yourself because JavaScript arrays are still probably gonna be faster than anything that you could implement. If I was writing something in C, or C++, or Java, or something like that, it can make a pretty big difference.

[00:05:36]
One of the nice things about LinkedLists is, you don't have to pre-declare how big they're gonna be, right? Because you can always just add something to the end. Because you can go anywhere you want in memory. With ArrayList you kinda have to pre-declare how much memory you wanna use, which means that can be inefficient.

[00:05:56]
I think the Java ones are actually smart enough to reallocate themselves, but nonetheless, that's a downfall, as well. In terms of a practical example, I'm struggling to think of a concrete necessarily example, at the moment. But the general idea is, if you need to insert into the middle or delete from some sort of array, which I'm sure you can fathom situations where you're doing a lot of deleting and modifying of arrays.

[00:06:29]
LinkedLists is where that's really gonna shine. But for the most part, ArrayLists kind of tend to be the default, because most of the time we tend to read more from arrays instead of modify them. So, that's the best general advice I'm gonna give you. It's not really super top of mind, again, cuz JavaScript, for the most part you don't really have to care about these.