Four Semesters of Computer Science in 5 Hours Array List

[00:00:00]
>> [MUSIC]

[00:00:03]
>> Brian Holt: We're gonna be borrowing some Java terminology because I learned computer science with Java. We're gonna be talking about a ray list versus linked lists. And we're gonna be doing implementations, right. We're gonna be doing the things that implement sets, or cues, or things like that. In this case, we're gonna be implementing arrays, right.

[00:00:27] So, I guess the first thing that I should stress here is these are like not real implementations because we're not actually controlling memory, right. And that's where actually these make up big differences, if you have control over memory, which is why you would never do this stuff in JavaScript.

[00:00:42] We're gonna do it in JavaScript because it's a language that you already know and it's useful to understand what trade-offs are going on underneath the scenes. So anyway, we're gonna be talking about ArrayList. An ArrayList is basically what most of you probably think of when you think of an array or a list of some sort.

[00:01:01] And again it's not really that important because the JavaScript is a garbage collected language but if you're doing something that was not garbage collected these become actually hugely important to work which when you're doing. So ArrayList is done directly by interacting with an allocated piece of memory. So coming back here, if I have an array, so let's just do it like this.

[00:01:32]
>> Brian Holt: And I allocate this much memory, right?
>> Brian Holt: Right, and I start sticking things in here, so I'm just gonna say, I don't know, foo bar, as I don't know what actually comes after that, so other things. And then these all have indexes, right. Cuz this is an array.

[00:02:01]
>> Brian Holt: Basically that index this descriptive of where it is in memory, right. We have an array. And we know where the array is in memory because we have like var x = array right? So we know where this exists in memory. And then when we're given an index, it says okay, in the second, not the second but the 2 index, the third place in memory.

[00:02:26] That's the thing that I want, right? So that's what an ArrayList is. Your index is descriptive of where to go get the thing that you're looking for. That makes sense-ish? Okay. Let's get out of that. So yeah, you interact with it that way. And you just basically treat it like a normal array.

[00:02:49] However what's annoying about doing ArrayList implementations is now you have to worry about collapsing the array. So if I delete index 3 which is gonna be d here right, I now have a,b,c, blank, e, f, g. And now my index is no longer descriptive of where the thing is.

[00:03:10] So now I have to go shift everything over. And if you have an array of 10 million objects and you delete number 2, that's actually hugely expensive cuz you have to shift 9,999,998 objects over. So that's the trade-off that you're making here is, you're saying that I'm okay with.

[00:03:30] Like this implementation but when I do delete and also insert into. So, if I have, where am I? Pen, so if I try to insert into right here and I try to insert Capital A or something like that. Now I have to shove everything over and that's super expensive.

[00:03:56] Or it can be really expensive because you want your data structures to be really, really, really fast. But look ups, when I say like I want element 4, I know exactly where that is. It can just go straight there in memory and just grab it and that's super fast.

[00:04:13]
>> Brian Holt: So yeah that shifting becomes very, very expensive. So do we understand the trade-offs of what I'm making here? Basically I'm optimizing for gets and I'm de-optimizing Delete and insert into, right.
>> Brian Holt: That's the trade off being made here.