Arrays vs Linked List

[00:00:00]
>> All right, so we're gonna keep on going here. And this is the part of the list or a part of the class where we're gonna do a little bit of comparing and contrasting. So let's think about the usability of an array versus a linked list. Something that's really nice about an array is you get in to see accessing, right?

[00:00:14]
0,1, 2, it's fast, right? You're able to just set any value. The understanding of what is actually happening underneath the hood is also pretty straightforward, right, you just allocate the memory, however you do it. And then you can just access that and you set those values. The memory is understood based on the type that you have casted to.

[00:00:32]
There you go, very simple. Obviously, some of the problems with it is that there is no literal insert, there's only right. And so that causes problems. You can't really insert a value into an array without actually writing the four loops manually to shift everything over, then put in your value or unshift everything and write over your value if you were to delete.

[00:00:52]
And so it does cause it to be a bit more difficult. At timelines, arrays are really nice. It's O(1), everything, right? If you want to write over a value, it's O(1). If you want to get a value, it's O(1). It's fantastic, but, again, there's a bit of a problem just with the usability of it all.

[00:01:10]
So I did wanna kind of point this out which is it which is interesting. So one thing that's unique about an array is that you obviously allocate this all upfront. Meaning that if you want to potentially to store up to 1000 items you're gonna have to allocate all that memory upfront, right?

[00:01:28]
Yeah, so you're gonna have to have 1000 items worth of memory created and then you may use however much you are going to use. Maybe you'll use all thousand, maybe you'll only use a few of them, right? It's a little bit different. Whereas a linked list, if you do allocate, or if you create a length list, it has nothing to begin with.

[00:01:46]
When you insert something, it only creates a single containing node. If you insert two things it has to containing nodes and that's it, so the memory usage is more optimized, but there is a difference of runtime cost there, right? With an array the memory has already been retrieved, it is already there, so you can easily use what you have.

[00:02:04]
So it tends to have really great performance, the constancy that is there, just as smaller now, you could obviously create some sort of object pool, hold on to all the deleted nodes. So that way you're not creating a bunch of new ones ways to speed up a list.

[00:02:17]
But still, you are creating a containing node, you're setting up links, it's a little bit more cumbersome than say an array. One thing that's nice about an array or a linked list, though, is just always will use less memory, but the usability of a list is a little bit different, right?

[00:02:31]
If you wanted to get an item out of the list, you have to traverse each item in the list until a you find it. So it's like always a linear search. There is no such thing as a binary search on a linked list. You can't hop into the middle, you have to walk the whole thing.

[00:02:46]
So linear search is really your only option on the linked list, which does make it a bit unfortunate of a data structure when it comes to that type of operation. So typically, if you need to scan a list or hop into a list of random access, you'd want to use something more like an array.

[00:03:00]
If you want to be able to just push and pop from either the head or the tail, you tend to want to be able to use something like a list. There's a trade off, there's an intentional trade off you should make when deciding this. So a good example of this is say like an a sync request queue.

[00:03:13]
Say on your front end, you don't want to have more than five network operations happening at one point. For whatever reason, you've decided this is the case, well, then you're gonna have these promises that are generated. They go off, but you only want five of them active at any one point, that means you're gonna have to pull off the front and you're able to push onto the back as new ones come in and as old ones complete.

[00:03:31]
So you have this whole problem of a queue, but you don't want to be using an array if it's a really highly used one because now you're shifting all these indices around using a JavaScript array. It's not gonna perform very good, it seems like it's a bad idea.

[00:03:44]
So it's good to know what you have and when you want to use some something. Always play that over in your head. Is there any questions on usability of these two maybe in JavaScript land it's a little bit less apparent just because it's just you just have brackets?

[00:03:56]
>> How would you traverse a linked list or would you just not even try? [LAUGH]
>> So how would you traverse a linked list here? I'm gonna go back to the code and we'll just, oopsies, I'm gonna go back to the code and let's go to doubly linked list.

[00:04:08]
So if I were to create this thing, right, I'm just gonna go fast, you don't have to follow along on this one. Let's just pretend we have this beautiful thing right here that has a value T, do that and preve. What am I doing? There we go, awesome.

[00:04:28]
So we have this thing that would be our node, right? I hate that, I always hated that. And let's pretend we wanted to do like say a get, right? Let's go like this, a private head is a node team. So I won't implement all these operations we'll just do you know we'll just do this right just odd length = 0.

[00:04:54]
Why not do all that stuff? So if we were wanna do a let's just say a get operation on a linked list, well, what do we have to do? We'd have to first go, let curr = this.head, right? We are now at our head, right? We have this item, then we could go for (let i = 0.

[00:05:12]
I have to be less than index, and there has to be something there, right. So in case we tried to grab outside of the array, we could do a length check right here if we really wanted to, but again, it just makes it, it's just it completes goofy for TypeScript, right.

[00:05:27]
So now that we're here, we can just go current=current.next, right? So we literally walk forward one at a time. So there is no simple way to get there. We just literally have to walk it. That is why it's considered a linear operation cuz you have to walk it.

[00:05:43]
Then at that point, we can just do the old curr value, right? Awesome, we have now successfully just wrote get() at a specific index for a linked list. So not too hard, but at the same time, you can see why this is like a very inefficient operation. If you had a big list that would obviously just destroy performance.