ArrayList Internals

At some point in your Java journey you would have used an ArrayList. But do you know how it works? How can it store any number of elements? Let’s have a look at it.

ArrayList uses an Array to store it’s elements.

Screenshot from ArrayList’s code

When you create an instance of ArrayList, this elementData Array is initialised with either a size of zero or whatever initial capacity you provided. Depending on the constructor that you used for creation.

But yeah, you guessed it right, arrays are fixed in size. Then how is that an ArrayList is not fixed in size. It’s because of the following piece of code in ArrayList.

grow method of ArrayList

Head exploded🤯???

Let me make this simple for you

1. When the array is completely filled with elements, then ArrayList calls the above grow method to reinitialise the array with increased size and copies all the elements to this new array.
2. Let’s look at how the new capacity of the array is determined. That part is very cool.

newLength method of ArrayList

If you look at the above method’s signature, there are 3 arguments:

1. oldLength: which is the old capacity of the array
2. minGrowth: which is the minimum size that should be added to the array. It’s 1 incase you are adding 1 element to the ArrayList. And multiple when you are adding elements from another collection.
3. prefGrowth: It’s the preferred growth. It’s 50% increase in the old capacity if you are adding elements to the list. It’s achieved by the little >> bitwise operator which you can see in grow method in second image.

Note: If the preferred growth is greater Integer.MAX_VALUE — 8 then, minimum growth is chosen. If that is also going above Integer.MAX_VALUE — 8 then an OutOfMemoryError is thrown.

What about other operations? Let’s look at two major operations:

Inserting an element at a specific index

All the elements starting from that index are moved to the right and then the element is inserted at that index

Removing an element from a specific index

All the elements starting from the right of that index are moved to the left

Conclusion:

So what we got to know is that ArrayList uses an array to store the elements. Furthermore, when the array is filled, it reinitialises the array with increased size and copies all elements from previous array. This is an added CPU cost, which you should remember when making a choice to use an ArrayList