In‑Depth Analysis of Java ArrayList Implementation

ArrayList is a dynamically resizable array in Java, optimized for read‑heavy scenarios, and is not thread‑safe by default. The article begins with a brief introduction and then details the inheritance hierarchy, highlighting interfaces such as RandomAccess, Serializable, Cloneable, Iterable, Collection, and abstract classes like AbstractCollection and AbstractList.

Fields

/**
 * Serial version UID for serialization.
 */
private static final long serialVersionUID = 8683452581122892189L;

/** Default capacity */
private static final int DEFAULT_CAPACITY = 10;

/** Shared empty array for empty instances */
private static final Object[] EMPTY_ELEMENTDATA = {};

/** Shared empty array for default‑capacity empty instances */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/** The element storage array (transient for serialization) */
transient Object[] elementData;

/** Number of elements stored */
private int size;

Constructors

/** Create ArrayList with specified initial capacity */
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);
    }
}

/** Create ArrayList with default capacity */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/** Create ArrayList from another collection */
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;
    }
}

Add Operations

/** Append element at the end */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

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

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

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

Remove Operations

/** Remove first occurrence of the specified element */
public boolean remove(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i] == null) {
                fastRemove(i);
                return true;
            }
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i])) {
                fastRemove(i);
                return true;
            }
    }
    return false;
}

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    elementData[--size] = null; // avoid memory leak
}

Modification, Search, and Traversal

// Set element at a specific index
public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

// Find first index of an element
public int indexOf(Object o) { /* implementation omitted for brevity */ }

// Iterate using for‑loop, foreach, lambda, Iterator, ListIterator, and Spliterator (code examples omitted for brevity)

Serialization

private void writeObject(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(ObjectInputStream s) throws IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;
    s.defaultReadObject();
    s.readInt(); // ignore stored size value
    if (size > 0) {
        ensureCapacityInternal(size);
        Object[] a = elementData;
        for (int i = 0; i < size; i++)
            a[i] = s.readObject();
    }
}

Thread‑Safety Strategies

Replace ArrayList with Vector.

Wrap it with Collections.synchronizedList.

Use CopyOnWriteArrayList for read‑heavy concurrent scenarios.

Avoid manual synchronization on a plain ArrayList; prefer thread‑safe collections when concurrency is required.

The article concludes by encouraging readers to explore the source code further, noting that while ArrayList is suitable for read‑dominant workloads, other collection types may be more appropriate for heavy modification or concurrent use.

As an additional note, the author points out that ArrayList inherits from AbstractList which also implements List, prompting curiosity about the design rationale behind this double inheritance.