Wednesday, April 21, 2021

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 - 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-

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.
    As 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:
     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<? 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) {
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  elementData[size++] = e;
  return true;
}
private void ensureCapacityInternal(int minCapacity) {
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  ensureExplicitCapacity(minCapacity);
}

Where DEFAULT_CAPACITY is defined as-

private static final int DEFAULT_CAPACITY = 10;
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
       grow(minCapacity);
}

You can see here it is determined if there is a need to increase the size of the array, if yes then grow method is called.

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Note that till Java 6 the new capacity calculation used to be like this-

int newCapacity = (oldCapacity * 3)/2 + 1;

Which is changed in Java 7 to use right shift operator. With right shift operator also it will grow by 50% of old capacity.
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.

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 it first 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!


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

10 comments:

  1. it is nice to explain about ArrayList in Java but could you please put some Examples to understand how it works ?

    thanks alot
    Java Developer

    ReplyDelete
  2. How is that i can iterate and remove an element at the same time from an LinkedList using the remove() method, but i cannot do it for an ArrayList.

    ReplyDelete
    Replies
    1. it's because array elements are stored in contiguous memory locations, whereas the nodes of linked lists can be stored anywhere in memory. if you delete an item from an array, all the later items in the array must be moved down to fill the gap. if you delete an item n from a linked list, you only need to update the 'next node' pointer of n-1 to point to n+1.

      Delete
  3. where the elementData variable is declared....?

    ReplyDelete
  4. Nice post. 5th and 6th are duplicate points in point to note section.

    ReplyDelete
  5. Hi,

    Nice tutorial about ArrayList. one small update, From Java8 onwards the ensureCapacityInternal() method in the add() the capacity calculation code has changed slightly.

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
    }

    private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    ReplyDelete