ArrayList arguably would be the most used collection along with the HashMap. Many of us programmers whip up code everyday which contains atleast one of these data structures to hold objects. I have already discussed how HashMap works internally in Java, in this post I'll try to explain how ArrayList internally works in Java.
As most of us would already be knowing that ArrayList is a Resizable-array implementation of the List interface i.e. ArrayList grows dynamically as the elements are added to it. So let's try to get clear idea about the following points-
- How ArrayList is internally implemented in Java.
- What is the backing data structure for an ArrayList.
- How it grows dynamically and ensures that there is always room to add elements.
Note - Code of ArrayList used here for reference is from Java 10.
Where does ArrayList internally store elements
Basic data structure used by Java ArrayList to store objects is an array of Object class, which is defined as follows-
I am sure many of you would be thinking why transient and how about serializing an ArrayList then?
ArrayList provides its own version of readObject and writeObject methods so no problem in serializing an ArrayList
and that is the reason, I think, of making this Object array as transient.
What happens when ArrayList is created
ArrayList class in Java provides 3 constructors to create an ArrayList.
- public ArrayList[int initialCapacity]- When this constructor is used we can provide some initial capacity rather than depending on the default capacity as defined in the ArrayList class.
As example-List myList = new ArrayList[7]; Code in the ArrayList class is as -public ArrayList[int initialCapacity] { if [initialCapacity > 0] { this.elementData = new Object[initialCapacity]; } else if [initialCapacity == 0] { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException["Illegal Capacity: "+ initialCapacity]; } }Where EMPTY_ELEMENTDATA is defined as-
private static final Object[] EMPTY_ELEMENTDATA = {};It is easy to see that, if provided capacity is greater than zero then the elementData array will be created with that capacity, in case provided capacity is zero then elementData array is initialized with an empty Object array. In that case ArrayList will grow when first element is added.
- public ArrayList[]- In case default constructor is used i.e. you will create an ArrayList as given below: myList = new ArrayList[];
Code in the ArrayList class for no-arg constructor is as given below-
public ArrayList[] { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }Where DEFAULTCAPACITY_EMPTY_ELEMENTDATA is defined as
/** * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * first element is added. */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};So you can see initially it will be initialized with an empty array, it will grow only when first element is added to the list.
- public ArrayList[Collection