How ArrayList works internally in java

How ArrayList works internally in java

ArrayList internally uses array data structure and ArrayList grows dynamically when the elements are added in the ArrayList.

When we create ArrayList object using its default constructor i.e.

new ArrayList(); then default capacity of ArrayList is 10.

private static final int DEFAULT_CAPACITY = 10;

public ArrayList() {

        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}

Also we can create ArrayList object with user defined initial capacity

ArrayList(int initialCapacity) So internally it will create the array with size which is equivalent to the integer value argument passed in the ArrayList object.

ArrayList list = new ArrayList(20);

transient Object[] elementData;

private static final Object[] EMPTY_ELEMENTDATA = {};

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

        }

 }

How the size of ArrayList grows dynamically?

The capacity of the ArrayList will be checked before us adding the element, ensureCapacityInternal ()  determines what is the current size of occupied elements and what is the maximum size of the array. If size of the filled elements is greater than the maximum size of the array then increase the size of array.

So internally new Array is created with capacity new capacity and internally java copy data from old array to newly created array.

How add method works internally in ArrayList

Below is the implementation of the add(E e) method in jdk 8.

1] add(E e) - Appends the specified element to the end of this list.

    public boolean add(E e) {

        ensureCapacityInternal(size + 1);  // Increments modCount!!

        elementData[size++] = e;

        return true;

    }

2] add(int index, E element) - Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right.

This add() method also throws IndexOutOfBoundsException  if the index position is out of range with existing array.

    public void add(int index, E element) {

        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!

        System.arraycopy(elementData, index, elementData, index + 1,

                         size - index);

        elementData[index] = element;

        size++;

    }

3] ensureCapacity (int  minCapacity) -  Increases the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.

   

 public void ensureCapacity(int minCapacity) {

        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)

            // any size if not default element table

            ? 0

            // larger than default for default empty table. It's already

            // supposed to be at default size.

            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {

            ensureExplicitCapacity(minCapacity);

        }

    }

MAX_ARRAY_SIZE – The maximum size of array to allocate.

     * Some VMs reserve some header words in an array.

     * Attempts to allocate larger arrays may result in

     * OutOfMemoryError: Requested array size exceeds VM limit

    

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

grow(int minCapacity) - Increases the capacity to ensure that it can hold at least the number of elements specified by the minimum capacity argument.

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

    }

Till Java 6 ArrayList capacity

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

After Java 8 onwards ArrayList capacity

The grow method in ArrayList class ensure the new size of the underlying array:

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

Performance of ArrayList

The add operation runs in constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time.

The  size, isEmpty, get, set, iterator, and listIterator operations run in constant time O(1).