Transcript from the "ArrayList" Lesson
[00:00:00]
>> I bring these up ArrayList here and now linkless after this because, first of all I'm using Java terminology and I apologize for that. But I don't also know of any better terminology for this and I think it's important for you to know these two data structures. We're talking two different ways that you could implement an array, right?
[00:00:17] Like if I was gonna go write my own standard library with my own array types. These are kind of the two chief ways of doing it, this is really awkward for us to try. And model this in JavaScript because Java JavaScript doesn't really give you a choice, we have one array data type, and it's just called array, right?
[00:00:38] But if you're in a language like Java or other languages like that, they actually give you a choice of what type of array that you're going to use. And you choose one depending on what kind of operations you're going to be doing with your array. Again, JavaScript being the high level language that it is, doesn't give you a choice.
[00:00:58] So an ArrayList again, imagining in your head that you're implementing an array for yourself, right? An ArrayList is kind of how you would think of it, right like that's how most of us would conceptualize how to put something in memory. So, again, pretend for a second that JavaScript has no array tied, so for right now you can't say x equals square brackets.
[00:01:29] I want you to think about how would you implement an array yourself using just objects. So for an ArrayList basically, I think imagine most of you would say like, okay. Well if I'm going to be doing with objects, I can just say that let's just put it in here.
[00:01:49] You might have an object that looks like my array equals object, I could just say array 0 or .0 = 1. I guess it doesn't like dot, so you do array 0 = 1, array 1= 2, right? So I mean obviously at the end of the day this looks actually fairly similar to what would be implementing it as, right.
[00:02:18] But imagine this would be like sequentially allocated in memory, right. So basically all of the various different items in your array would be co located in memory. So that if you were asking for like hey I want index 4, basically we would hop into memory. We'd look for index 0 and then we will go four places over and we would arrive at our item in the array, right?
[00:02:40] So everything is just located right next to each other in memory, that makes sense? The advantage of this is it makes lookups super easy, right if I know the index and I know the object, I know exactly where it is in memory. Cuz you can think of memory is just like one super long array, right with various different addresses that we could look at.
[00:03:04] Yeah, so that makes lookups super easy because we can just say, okay, go to this place in memory and go seven places over. And then you have array index 6, while it's super advantageous for lookups it's kinda disadvantageous for like deletions. Possibly for additions, certainly for shifting things around, right?
[00:03:28] Because if I wanna delete, let's say I have an array of size 10, so let's even go like this. So now I have 2=3, right and I have an array that has 0,1, 2 and 3, if I delete index 0 what happens? I now have to go and shift everything up, right now I have to say array 1 is assigned array 0, other way around array 0 is assigned 1.
[00:04:10] And I have to say array 1 is assigned array 2. And now if I say array again, and then I have to finally say delete array 2. So now if I look at my array now, that's what I had to do to actually delete something out of the array.
[00:04:34] That's kind of burdensome, right [LAUGH] Now imagine if my array is of size 10,000 and I want to delete arrays 0. I don't have to go shift 9999 things in memory, that doesn't sound like fun, that actually sounds pretty computationally inefficient. So that's where ArrayList kind of falls apart because it makes these deletions, right.
[00:05:05] Or if I wanna insert something straight in the middle, that becomes really burdensome. So that's why ArrayList for arrays is really good for things you have to do a lot of lookups on, a lot of addition. And then adding things to the end typically isn't too bad as long as you have sufficient space in memory.
[00:05:22] All that kind of stuff is great, but as soon as you wanna do a lot of deletions and additions in the middle ArrayList is not a good thing. Yeah, keep in mind you do have to do a lookup in a deletion in order to do a deletion. This is true regardless, we kind of ignore that part of it but let's talk about the big O's of this.
[00:05:45] So, a big O of an ArrayList lookup in terms of like if I asked you for array one like this. This would be constant time, right because I'll have to do is find the object, hop over one space, there it is. That's considered constant time for a lookup, however if I wanna do a deletion, what is that?
[00:06:08] That actually ends up being N, right? Because I have to shift everything over in memory every single time that I do that.