Dynamic Arrays, aka ArrayLists - YouTube

This video is on dynamic, or growable, or resizable arrays, also known as

ArrayLists in java or vectors in C++. It is part of a playlist, linked

here. To understand ArrayLists, first you have to know how arrays work.

We build ArrayLists using arrays, analyze them, go over their operations,

and finish with a playlist including advanced optimization issues.

So an array is something that holds a fixed number of elements. For notation, an array has some

variable name, and then has an index position inside of some square brackets,

so this would be the 4th position within the array. Some languages

use this same notation but allow you to index by anything, like a string, but I'm

not talking about that. I don't know what the freaking "cat"th position of an

array is. A real array is implemented as a continuous block of computer memory.

You could start numbering at 1, but for this video, I start at 0, so an

array of size 8 has items indexed from 0 to 7.

No fancy-smancy number skipping.

We can store whatever we like in the array,

but the size of each item is the same. So, we can have an array of integers,

or characters, or object references, or even fixed sized objects.

Some of that is language dependent, but abstractly, just imagine a bunch

of items lined up in some fixed amount of memory that has been

allocated to your program. So the great thing about arrays is that they give

direct access to any location. Like any variable, the array name is

associated with a memory location, and then the index just gives an offset

from that location to a new memory location. If we want the fourth item,

we just move forwards by four times the size of each item in the array.

I will use integers here, so we just move forwards to get the fourth

integer after the one that starts the array. This is a very quick operation.

Because arrays map directly to your computer memory, you need to

specify how large the array will be when you allocate memory for it,

which is their weakness: sometimes you don't know how many spaces you need.

If you don't allocate enough space, you will run out of room, but if you allocate too much space, you

waste memory. The big idea behind a dynamic array is that if you want to add

something to an array that is already full, just allocate a bigger array,

copy over all of the items from the old array, and now you have space for more elements.

Freakin' genius, right?

No, it's really simple, but, you need to do it the right

way to get good performance. A bad way to go would be to just allocate

exactly the space you know you need right now. So from my example,

if I need room for a 9th element, I could copy over everything into an

array with 9 spaces, but later if I want to add a 10th item,

I would then need to move to an array of size 10.

With this approach, I can really hose myself. To add the ith item

takes time proportional to i, so if I add n total items, it takes

order n squared time. A better way is to make the new

array proportionally bigger than its current size, even if that's

more than you immediately need. Starting with this size 10 array, when we

run out of space, we could double the array size. So, once you realize

that you have an 11th item and your array only has 10 spaces, you allocate a

new size 20 array, copy over the first 10 items, and then add

the 11th. We keep track of the fact that our data structure has size 11,

but capacity 20. Now,

there's still more room in the array, and if we want to insert a 12th item to the end of the data structure,

just stick it there, and increment the size. For this data structure,

by default, always add new elements to the first

unfilled location. We don't allow skipping,

and if you add it to an earlier location, you have to shift

items over to make room for it, and it kills your performance.

While inserting only to the end is a bit of a limitation,

the underlying array structure does let us

directly access any item in constant time.

If the size is less than our capacity, we can also add to

or delete from the end of the list in constant time too.

Of course, if you really want to insert

to somewhere in the middle of the array, you can, but it takes time

proportional to the number of items after the position you are inserting to,

because we will shift all of those items over to make room.

Deletion from the middle also forces a shift to fill the blank space.

Insertion and deletion from the middle of the array aren't really

natural operations, they force us to loop over everything after

the changed location. The ArrayList class in java has methods

for indexed insertion or deletion, but it is internally

implemented with a loop. They may have optimized that loop to try

to make it fast, but you shouldn't forget it's there. The default position

for insertion or deletion is the end of the list. Okay, what happens

when we want to insert to the end, but the array is full? We can't just

stick the item in place and increment the size anymore. Instead, we need to

allocate new space, copy all of the items over, taking linear time

in the total size. Can we fix that? Well, it turns out that we don't

need to. Because we double the array size when growing, those

expensive insertions can't happen very often. Inserting to the end is

expensive when going from size 10 to 11, but then we get a whole bunch of

constant time insertions to go all the way up to 20. Then we get another expensive

insertion, twice as expensive as the previous one, but then we get cheap

insertions all the way up to size 40. Some insertions are expensive,

but on average they take constant time each. This is called

amortized analysis: instead of looking at the cost of each operation

individually, we consider the total runtime for an entire sequence

of operations, and use this to get the average performance per operation.

For this data structure, the average performance of inserting

to the back of the list is constant time. You can look at best

case average performance per insertion, or the worst case average

performance, or even the average case average performance, they are all

constant time. How do we prove that insertion takes on average constant

time per operation? Imagination and incense. No,

going back to our half-full array of capacity 20, imagine that every time

we insert into the array, if we have space, we not only pay for

insertion, but also prepay to copy 2 values

to a new location sometime in the future.

Including this extra imagined payment, insertion still takes constant

time, even if it is a few times larger than the real time insertion takes.

Clearly, adding that extra time to my

time analysis isn't going to let me undercount how much real time

is used to insert items. When we go to insert the 21st

item, we first allocate the new array, size 40, and copy

over 20 items to it. But, for those last 10 insertions

I did, I have already included the cost of 2 copies each in my

time analysis. In our analysis, we withdraw against our

prepayed copy operations, and we have already deposited enough to copy

over all 20 items. The actual copying doesn't

happen until now, but if I am analyzing all of the time spent from the beginning,

we see that we have already accounted for the time of these

copies, during the last 10 insertions. For the 21st item,

I only still need to pay for its insertion, and with it

I will also prepay for two copy operations for the next

time the array grows. This is called the accounting method for

amortized analysis. Your analysis overcharges for some operations,

and uses those prepayed overages to pay for

expensive operations which may come later. As long as the

analysis for any sequence from the start charges at least the real life

amount, you can use it to get valid average upperbounds.

Okay, how about deletion? If you want to delete from the end of the list, clearly

you can do that in constant time, but is there any reason to shrink the

size of the underlying array, if it is too empty? Before figuring

out how to do that, is it worth doing? It is.

Imagine that we are simulating a set of a billion items moving around between

a thousand lists. On average, the lists have a million items each,

but occasionally, maybe most of the items end up being in one list. When that

happens, that list size will grow to hold a billion items. If

different lists are crowded at different times, and you never shrink any of them,

eventually, you end up trying to allocate a thousand arrays of

size a billion each, even though you only have a billion items.

More generally, if you never shrink,

m lists holding n items total can take

order nm space, instead of n + m space.

So when should we shrink the arrays? First of all,

it depends on your growth factor

when you grow your arrays. We have been using growth factor

2, so you can't shrink them if they just go under half full,

or you could end up with a bunch of expensive operations if you ever alternated

between inserting and deleting right near a boundary, like between sizes

19 and 21 here, it would be slow. But, if you

double when growing, but only shrink when you go under, let's say, one quarter

full, you will be safe. Maybe have some minimum size too.

Using similar analysis to the insertion, where every deletion deletes

one item from the end of the list, but we also prepay for a

copy operation, we can prove that each deletion also

takes amortized constant time. If we implement shrinking,

ArrayLists use only linear space in their size.

Now that we know how ArrayLists are implemented, it is easy to see what

operations they give, and also how to make an iterator for them.

They support constant average time insertion and deletion from the

last position, as well as constant time indexed

item retrieval. Because of that quick retrieval, to make an

iterator, the only information you need to store is an index, but

that iterator shouldn't really be used to mess around with the middle of the list by

inserting or deleting there. If you want to get into boss level

topics like how to optimize your ArrayList growth factor, I will cover that in

a separate video in the playlist, but that's it for this one.

I've got to go work on my pirate accent.

ArrrrrayList.