ArrayList

ArrayList is the most commonly used List implementation in Java, providing dynamic arrays that grow as needed.

Source Code #

Core Implementation #

ArrayList uses an object array to store elements and provides automatic resizing:

transient Object[] elementData; // non-private to simplify nested class access
private int size;

Implementation Details #

Construction #

// Default constructor - empty elementData
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// Capacity constructor
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);
    }
}

// Collection constructor
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

Growth Strategy #

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

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

The growth strategy:

First expansion: Grows to DEFAULT_CAPACITY (10)
Subsequent expansions: Grows by 50% (oldCapacity » 1)
Uses ArraysSupport.newLength() for bounds checking

Add Operations #

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

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

public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index,
                    elementData, index + 1,
                    s - index);
    elementData[index] = element;
    size = s + 1;
}

Remove Operations #

public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;
    
    @SuppressWarnings("unchecked")
    E oldValue = (E) es[index];
    
    fastRemove(es, index);
    return oldValue;
}

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null; // Clear reference for GC
}

public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
    found: {
        if (o == null) {
            for (; i < size; i++)
                if (es[i] == null)
                    break found;
        } else {
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        return false;
    }
    fastRemove(es, i);
    return true;
}

Bulk Operations #

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    modCount++;
    int numNew = a.length;
    if (numNew == 0)
        return false;
    
    final int s;
    Object[] elementData;
    if (numNew > (elementData = this.elementData).length - (s = this.size))
        elementData = grow(s + numNew);
    
    System.arraycopy(a, 0, elementData, s, numNew);
    size = s + numNew;
    return true;
}

Trim to Size #

public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
            ? EMPTY_ELEMENTDATA
            : Arrays.copyOf(elementData, size);
    }
}

Iteration Support #

public Iterator<E> iterator() {
    return new Itr();
}

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;
    
    Itr() {}
    
    public boolean hasNext() {
        return cursor != size;
    }
    
    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }
    
    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();
        
        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

Fail-Fast Mechanism #

protected transient int modCount = 0;

The modCount is incremented on every structural modification and checked by iterators to detect concurrent modification.

Serialization #

private void writeObject(java.io.ObjectOutputStream s) throws IOException {
    int expectedModCount = modCount;
    s.defaultWriteObject();
    
    s.writeInt(size);
    
    for (int i = 0; i < size; i++) {
        s.writeObject(elementData[i]);
    }
    
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

private void readObject(java.io.ObjectInputStream s)
    throws IOException, ClassNotFoundException {
    s.defaultReadObject();
    
    s.readInt(); // Read and ignore size
    
    if (size > 0) {
        int capacity = calculateCapacity(elementData, size);
        SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
        ensureCapacityInternal(size);
        
        Object[] a = elementData;
        for (int i = 0; i < size; i++) {
            a[i] = s.readObject();
        }
    }
}

Performance Characteristics #

Time Complexity:
- get(int index): O(1)
- add(E e): O(1) amortized, O(n) when resizing
- add(int index, E e): O(n) due to array copying
- remove(int index): O(n) due to array copying
- contains(Object o): O(n)
Space Complexity: O(n) where n is the number of elements
Memory Overhead: ~12 bytes (object header) + array overhead + element references

Best Practices #

Pre-size when possible: Use constructor with initial capacity to avoid early resizing
Use trimToSize(): When ArrayList won’t grow further to reclaim memory
Prefer forEach(): Over traditional for-loops for cleaner iteration
Consider alternatives: For frequent insertions/removals in middle, consider LinkedList
Thread safety: ArrayList is not thread-safe; use Collections.synchronizedList() or CopyOnWriteArrayList for concurrent access

Common Pitfalls #

ConcurrentModificationException: Modifying list while iterating without using iterator’s remove()
Memory bloat: Empty ArrayLists still consume ~40 bytes (header + empty array reference)
IndexOutOfBoundsException: Not checking bounds before access
Performance issues: Frequent insertions/removals in middle cause O(n) array copies