ArrayList Internal Implementation in Java

ArrayList internal implementation in Java or how does ArrayList work internally in Java is a very important interview question. Some of the questions that may come up are-

  1. Where does ArrayList store its element?
  2. What is the initial or default capacity of ArrayList and how ArrayList of that capacity is created?
  3. How does add method in ArrayList work?
  4. How does remove method work in ArrayList?
  5. How does ArrayList grow and shrink automatically?

In this post let’s try to answer these questions by looking into the internal implementation of ArrayList in Java.

Where does ArrayList store its element

Internally ArrayList in Java uses array to store its element. It’s an Object array which is defined as follows.

Capacity of ArrayList

Initial capacity of the created ArrayList depends on the constructor used. There are 3 constructors.

ArrayList(int initialCapacity)– If initial capacity is explicitly specified while constructing an ArrayList then it is ensured that the elementData array is created with that length.

As you can see from this code from the ArrayList class in Java, if initialCapacity > 0 then elementData array is crated using that initial capacity.

ArrayList()– If no initial capacity is specified then the ArrayList is created with the default capacity.

Here is the code from the ArrayList class in Java.

If you see in the code DEFAULTCAPACITY_EMPTY_ELEMENTDATA is defined as an empty array.

It’s only when the element is added to the ArrayList that the array is created with default capacity. Default capacity in the ArrayList class is defined as follows.

ArrayList(Collection<? extends E> c)– If ArrayList is constructed using an existing collection then elements of the passed collection are copied to the elementData array.

As you can see from the code, in this statement elementData = c.toArray(); elements of the collection are returned as array.

elementData = Arrays.copyOf(elementData, size, Object[].class);
This line ensures that elementData array is converted to array of type Object.

How does add method work in ArrayList

That is where the resizable-array implementation feature of the ArrayList is covered. If you see the ArrayList internal implementation in Java, everytime add() method is called it is ensured that ArrayList has required capacity. If the capacity is exhausted a new array is created with 50% more capacity than the previous one. All the elements are also copied from previous array to new array.

When add() method is called initially there is a check to ensure the capacity.

As you can see if default capacity ArrayList has to be created it’s here that the capacity is actually initialized as 10.

From this code, if required, grow() method is called to increase the capacity of the ArrayList.

As you can see right shift operator is used to increase the capacity by 50% in the following statement.

Also the elementData array is changed to have the new capacity, elements from the old array are also copied to the new array.

So that’s how internally ArrayList keeps on growing dynamically.

How does remove method work in ArrayList

If you remove any element from an array then all the subsequent elements are to be shifted to fill the gap created by the removed element. That’s what remove method does internally in the ArrayList class in Java.

This is the statement which is actually shuffling the elements of the array.

So that’s how ArrayList shrinks dynamically.

How does ArrayList grow and shrink automatically

This point is already covered in the section how add and remove methods work in ArrayList.

That’s all for the topic ArrayList Internal Implementation in Java. If something is missing or you have something to share about the topic please write a comment.


You may also like

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.