How ArrayList Works Internally in Java

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.

Because of all these side questions it is also a very important Java Collections interview question.

Note that the code of ArrayList used here for reference is from Java 17

Table of contents

1. Where does ArrayList internally store elements
2. What happens when ArrayList is created
3. How does ArrayList grow dynamically
4. What happens when an element is removed from ArrayList

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-

transient Object[] elementData;

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. For example-
  

  List<String> myList = new ArrayList<String>(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:

  List<String> myList = new ArrayList<String>();
  

  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 grows only when the first element is added to the list.

• public ArrayList(Collection<? extends E> c)- If we want to construct a list containing the elements of the specified collection we can use this constructor. In this constructor implementation checks for the length of the collection passed as parameter, if length is greater than zero then Arrays.copyOf method is used to copy the collection to the elementData array.

  elementData = Arrays.copyOf(elementData, size, Object[].class);
  

How does ArrayList grow dynamically

When we add an element to an ArrayList it first verifies whether it has that much capacity in the array to store new element or not, in case there is not then the new capacity is calculated which is 50% more than the old capacity and the array is increased by that much capacity (Actually uses Arrays.copyOf which returns the original array increased to the new length).

Code in the Java ArrayList implementation is like this-

public boolean add(E e) {
  modCount++;
  add(e, elementData, size);
  return true;
}

This is the overloaded add() method which is called.

private void add(E e, Object[] elementData, int s) {
  if (s == elementData.length)
    elementData = grow();
  elementData[s] = e;
  size = s + 1;
}

You can see here it is determined if there is a need to increase the size of the array

  if (s == elementData.length)

if yes then grow() method is called.

private Object[] grow() {
  return grow(size + 1);
} 

private Object[] grow(int minCapacity) {
  int oldCapacity = elementData.length;
  if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    int newCapacity = ArraysSupport.newLength(oldCapacity,
          minCapacity - oldCapacity, /* minimum growth */
          oldCapacity >> 1           /* preferred growth */);
    return elementData = Arrays.copyOf(elementData, newCapacity);
  } else {
    return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
  }
}

As you can see first it is checked whether ArrayList is already created or it is the first addition to a new ArrayList.

if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)

If it's a List which is already in use then attempt is made to increase the capacity of ArrayList by 50% by using right shift operator.

oldCapacity >> 1

Let's see it with the help of a small program

public class Test {
    public static void main(String args[])  {
       int a = 10;
       System.out.println(a>>1);   
    }    
}

Output

5

If the default capacity was 10 then

 
int newCapacity = oldCapacity + (oldCapacity >> 1);

will return 15.

Otherwise (if first addition) create an ArrayList with default capacity.

Where DEFAULT_CAPACITY is defined as-

private static final int DEFAULT_CAPACITY = 10;

What happens when an element is removed from ArrayList

When elements are removed from an ArrayList in Java using either remove(int i) (i.e using index) or remove(Object o), gap created by the removal of an element has to be filled in the underlying array. That is done by Shifting any subsequent elements to the left (subtracts one from their indices). System.arrayCopy method is used for that.

System.arraycopy(elementData, index+1, elementData, index, numMoved);

Here index+1 is the source position and index is the destination position. Since element at the position index is removed so elements starting from index+1 are copied to destination starting from index.

Points to note

1. ArrayList in Java is a Resizable-array implementation of the List interface.
2. Internally ArrayList class uses an array of Object class to store its elements.
3. When initializing an ArrayList you can provide initial capacity then the array would be of the size provided as initial capacity.
4. If initial capacity is not specified then default capacity is used to create an array. Default capacity is 10.
5. When an element is added to an ArrayList, initially it verifies whether it can accommodate the new element or it needs to grow, in case capacity has to be increased then the new capacity is calculated which is 50% more than the old capacity and the array is increased by that much capacity.
6. When elements are removed from an ArrayList, space created by the removal of an element has to be filled in the underlying array. That is done by Shifting any subsequent elements to the left.

That's all for this topic How ArrayList Works Internally in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Advanced Tutorial Page | Return to Java Collections Framework Tutorial Page>>>

---

Related Topics

1. How HashMap Internally Works in Java
2. How LinkedList Class Works Internally in Java
3. How HashSet Works Internally in Java
4. How to Sort ArrayList of Custom Objects in Java
5. Java Collections Interview Questions And Answers

You may also like-

1. CopyOnWriteArrayList in Java With Examples
2. Fail-Fast Vs Fail-Safe Iterator in Java
3. strictfp in Java
4. Interface Static Methods in Java
5. Method Reference in Java 8
6. Synchronization in Java - Synchronized Method And Block
7. Difference Between Checked And Unchecked Exceptions in Java
8. How to Create Password Protected Zip File in Java