Array lists are created from directly interacting with the allocated memory. They are simple in the way they are constructed; however, inserting and removing values can be costly since the entire list must be collapsed or expanded to accommodate the updated value.
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, and I allocate like this much memory, right? Right? And I start sticking things in here, so I'm just gonna say, I don't know, foo, bar, baz.
I don't know what actually comes after that, so other things. And then these all have indexes, right? Like 'cause this is an array. Basically, that index is descriptive of where it is in memory, right? So like we have an array, and we know where the array is in memory because we have, you know, like, varx equals array, right? So we know where this exists in memory. And then when we give it an index, it says, okay, in the second, or not the second, but the two index, the third place in memory, that's the thing that I want, right? So that's what an array list is is your index is descriptive of where to go get the thing that you're looking for.
Does that makes sense? Ish? Okay. Let's get out of that. So then you, yeah, you interact with it that way. And you just basically treat it like a normal array. 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 going to be d here, right? I have a,b,c,(blank),e,f,g and now my index is no longer descriptive of where the thing is.
So now I have to go shift everything over. And if you have an array of 10 million objects and you delete number two, that's actually hugely expensive, because you have to shift you know, 9,999,998 objects over, right? So that's the trade-off that you're making here, is you're saying that I'm okay with, like, this implementation but when I do delete, and also insert into, right? So if I have, where am I? So if I try to insert into, like, right here, right? And I try to insert, like, capital A, or something like that, now I have to shove everything over and that's super expensive.
Or it can be really expensive because you want your data structures to be really, really, really fast. But lookups, when is say, like, I want element four, I know exactly where that is, right? It can just go straight there in memory and just grab it. And that's super fast. 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 deletes and insert intos, right? That's the trade-off being made here.
Note: This course was created by Frontend Masters. It was originally released on 07/12/2016. We're pleased to host this training in our library.
- Big O
- Sort: Bubble, insertion, and merge,
- Median values
- Set, map, stack, and queue
- Array lists and linked lists
- Binary search tree
- AVL tree
- Single rotation and double rotation
- Hash table
- Functional programming
- Map, reduce, and filter