Class Inheritance Structure

The ArrayList class definition is as follows:

public class ArrayList<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}

The interfaces implemented by ArrayList have been covered in previous sections, so they won't be elaborated on here.

Key Member Variables

// Default initial capacity when created via new ArrayList()
private static final int DEFAULT_INITIAL_CAPACITY = 10;

// Empty array used when initial capacity is set to 0
private static final Object[] EMPTY_ARR = {};

// Empty array used in no-arg constructor; expands to DEFAULT_INITIAL_CAPACITY upon first element addition
private static final Object[] DEFAULT_EMPTY_ARR = {};

// Array for storing elements
transient Object[] itemStorage;

// Number of actual elements in the list (not the length of itemStorage)
private int elementCount;

Internally, ArrayList wraps a standard object array (itemStorage) and tracks the number of stored elements (elementCount), similar to how String uses a char[] for storage.

Constructors

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.itemStorage = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.itemStorage = EMPTY_ARR;
    } else {
        throw new IllegalArgumentException("Invalid Capacity: " + initialCapacity);
    }
}

public ArrayList() {
    this.itemStorage = DEFAULT_EMPTY_ARR;
}

public ArrayList(Collection<? extends E> source) {
    Object[] arr = source.toArray();
    if ((elementCount = arr.length) != 0) {
        if (arr.getClass() != Object[].class)
            itemStorage = Arrays.copyOf(arr, elementCount, Object[].class);
        else
            itemStorage = arr;
    } else {
        this.itemStorage = EMPTY_ARR;
    }
}

ArrayList supports three constructors:

• No-arg constructor: Enitializes itemStorage to DEFAULT_EMPTY_ARR, which automatically expands to DEFAULT_INITIAL_CAPACITY (10) when the first element is added.
• Capacity-based constructor: Validates the input capacity and initializes itemStorage accordingly.
• Collection-based constructor: Converts the input collection to an array and uses it to initialize itemStorage.

Core Instance Methods

Adding Elements

ArrayList provides four methods to add elements:

1. Add single element to the end: add(E item)
2. Add all elements from a collection to the end: addAll(Collection<? extends E> source)
3. Add single element at specified position: add(int index, E item)
4. Add all elements from a collection at specified position: addAll(int index, Collection<? extends E> source)

Add single element to end:

public boolean add(E item) {
    ensureCapacity(elementCount + 1);
    itemStorage[elementCount++] = item;
    return true;
}

private void ensureCapacity(int minCapacity) {
    if (itemStorage == DEFAULT_EMPTY_ARR) {
        minCapacity = Math.max(DEFAULT_INITIAL_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - itemStorage.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    int oldCap = itemStorage.length;
    int newCap = oldCap + (oldCap >> 1);
    if (newCap - minCapacity < 0)
        newCap = minCapacity;
    if (newCap - MAX_ARRAY_SIZE > 0)
        newCap = hugeCapacity(minCapacity);
    itemStorage = Arrays.copyOf(itemStorage, newCap);
}

The method first checks for expansion. If needed, the internal array is resized to 1.5 times the old capacity. The new element is then added to the index elementCount, which is incremented afterward.

Add all elements from a collection to end:

public boolean addAll(Collection<? extends E> source) {
    Object[] arr = source.toArray();
    int numNew = arr.length;
    ensureCapacity(elementCount + numNew);
    System.arraycopy(arr, 0, itemStorage, elementCount, numNew);
    elementCount += numNew;
    return numNew != 0;
}

This method works similarly to adding a single element but uses System.arraycopy to bulk copy elements from the source collection to the end of itemStorage.

Add single element at specified position:

public void add(int index, E item) {
    rangeCheckForAdd(index);
    ensureCapacity(elementCount + 1);
    System.arraycopy(itemStorage, index, itemStorage, index + 1, elementCount - index);
    itemStorage[index] = item;
    elementCount++;
}

private void rangeCheckForAdd(int index) {
    if (index > elementCount || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMessage(index));
}

Elements from index onwards are shifted right by one position using System.arraycopy to make space for the new element.

Add all elements from a collection at specified position:

public boolean addAll(int index, Collection<? extends E> source) {
    rangeCheckForAdd(index);
    Object[] arr = source.toArray();
    int numNew = arr.length;
    ensureCapacity(elementCount + numNew);
    int numMoved = elementCount - index;
    if (numMoved > 0)
        System.arraycopy(itemStorage, index, itemStorage, index + numNew, numMoved);
    System.arraycopy(arr, 0, itemStorage, index, numNew);
    elementCount += numNew;
    return numNew != 0;
}

Similar to adding a single element at a position, but shifts elements right by numNew positions and uses bulk copy for the source collection.

Removing Elements

ArrayList supports removal by index or element value.

Remove by index:

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = getElementAt(index);
    int numMoved = elementCount - index - 1;
    if (numMoved > 0)
        System.arraycopy(itemStorage, index + 1, itemStorage, index, numMoved);
    itemStorage[--elementCount] = null;
    return oldValue;
}

After validating the index, elements from index+1 onwards are shifted left by one position. The last element is set to null to aid GC.

Remove by element:

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < elementCount; index++)
            if (itemStorage[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < elementCount; index++)
            if (o.equals(itemStorage[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

private void fastRemove(int index) {
    modCount++;
    int numMoved = elementCount - index - 1;
    if (numMoved > 0)
        System.arraycopy(itemStorage, index + 1, itemStorage, index, numMoved);
    itemStorage[--elementCount] = null;
}

The method first finds the index of the target element using either == (for null) or equals() (for non-null) comparisons, then calls fastRemove to perform the shift and GC optimization.

Modifying Elements

Update element at index:

public E set(int index, E item) {
    rangeCheck(index);
    E oldValue = getElementAt(index);
    itemStorage[index] = item;
    return oldValue;
}

Querying Elements

Get element by index:

public E get(int index) {
    rangeCheck(index);
    return getElementAt(index);
}

private void rangeCheck(int index) {
    if (index >= elementCount)
        throw new IndexOutOfBoundsException(outOfBoundsMessage(index));
}

E getElementAt(int index) {
    return (E) itemStorage[index];
}

Find first occurrence of element:

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < elementCount; i++)
            if (itemStorage[i] == null)
                return i;
    } else {
        for (int i = 0; i < elementCount; i++)
            if (o.equals(itemStorage[i]))
                return i;
    }
    return -1;
}

Find last occurrence of element:

public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = elementCount - 1; i >= 0; i--)
            if (itemStorage[i] == null)
                return i;
    } else {
        for (int i = elementCount - 1; i >= 0; i--)
            if (o.equals(itemStorage[i]))
                return i;
    }
    return -1;
}

Set Operations

Intersection (Retain Elements in Both Collections)

public boolean retainAll(Collection<?> target) {
    Objects.requireNonNull(target);
    return batchRemove(target, true);
}

private boolean batchRemove(Collection<?> target, boolean complement) {
    final Object[] storage = this.itemStorage;
    int readPtr = 0, writePtr = 0;
    boolean modified = false;
    try {
        for (; readPtr < elementCount; readPtr++)
            if (target.contains(storage[readPtr]) == complement)
                storage[writePtr++] = storage[readPtr];
    } finally {
        if (readPtr != elementCount) {
            System.arraycopy(storage, readPtr, storage, writePtr, elementCount - readPtr);
            writePtr += elementCount - readPtr;
        }
        if (writePtr != elementCount) {
            for (int i = writePtr; i < elementCount; i++)
                storage[i] = null;
            modCount += elementCount - writePtr;
            elementCount = writePtr;
            modified = true;
        }
    }
    return modified;
}

Difference (Remove Elements in Target Collection)

public boolean removeAll(Collection<?> target) {
    Objects.requireNonNull(target);
    return batchRemove(target, false);
}