Detailed Analysis of ArrayList

ArrayList is essentially a class that maintains an internal array to store elements, and a size variable to record how many elements are actually in use.

You can abstract it like this:

Java

        public class ArrayList<E> {
    transient Object[] elementData;
    private int size;
}

The two key fields are:

elementData: the underlying array that really stores data
size: the number of valid elements currently in the list

Note that elementData.length is not equal to size.

For example:

elementData.length = 10 means the underlying capacity is 10
size = 3 means only 3 slots are currently used

That means the first 3 positions contain data, while the remaining 7 may still be empty.

Why does it use Object internally?

In source code, you normally won't see E[]; you usually see Object[].

The reason is Java generics use type erasure. At runtime, the JVM does not know what concrete type E is, so many generic collections use Object[] for storage and cast when reading values out.

In other words:

On write: values are stored in Object[]
On read: values are cast back to E

That is why ArrayList can hold many object types, but you should still use generics to keep type safety.

How initialization works

Common constructors:

Java

        new ArrayList<>();
new ArrayList<>(20);
new ArrayList<>(collection);

At source level, the first two are the most important.

No-arg constructor
It does not immediately allocate an array of length 10. It first points to an empty array.
Similar to:
Java
```
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

    
```
This means:
- When new ArrayList<>() runs, default capacity is not allocated yet.
- It expands to the default capacity only on the first add.
This saves memory because many lists are created but never used.

Constructor with initial capacity
If you write: new ArrayList<>(20);
It directly creates an array with length 20.
Similar to:

Java

        public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
       this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
       this.elementData = EMPTY_ELEMENTDATA;
    } else {
       throw new IllegalArgumentException(...);
    }
}

This is useful when you already know the approximate data size, because it can reduce reallocation.

What add actually does

The most common call is: list.add(e);

The source idea is roughly:

Java

        public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

You can split it into two steps:

Step 1: ensure enough capacity ensureCapacityInternal(size + 1) checks:
- one new element is about to be inserted
- after insertion, at least size + 1 slots are needed
- if capacity is insufficient, trigger growth
Step 2: append to the tail

Java

        elementData[size] = e;
size++;

Or:

Java

        elementData[size++] = e;

This is why append is fast:

no index lookup
no element shifting
most of the time it is just writing one value at the end

So tail insertion is usually amortized O(1).

Why first add changes capacity to 10

This is a common confusion.

With the no-arg constructor, no length-10 array is created immediately. The first element insertion triggers default-capacity initialization.

Logic is roughly:

Java

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

Default capacity is usually: private static final int DEFAULT_CAPACITY = 10;

So:

new ArrayList<>(): still points to an empty array
first add: capacity becomes 10

This is lazy allocation.

How growth is implemented

This is one of the core parts.

If current capacity is not enough, grow() runs. Typical logic:

Java

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

// JDK 17
private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(
                oldCapacity,
                minCapacity - oldCapacity, // minimum required increment
                oldCapacity >> 1             // preferred increment: still 1.5x
        );
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        // first expansion: directly to 10
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

The key line is: int newCapacity = oldCapacity + (oldCapacity >> 1);

oldCapacity >> 1 means divide by 2, so new capacity is about 1.5 times the old one.

Examples:

10 grows to 15
15 grows to 22
22 grows to 33

Why 1.5x instead of 2x or +1? It is a balance between memory and performance.

If growth is +1 each time:

too many reallocations
every growth copies the array
performance becomes poor

If growth is 2x each time:

fewer reallocations
but potentially more wasted memory

So 1.5x is a practical compromise.

The expensive part is Arrays.copyOf(elementData, newCapacity);

It does:

allocate a larger new array
copy old elements into it
repoint elementData to the new array

So growth is not stretching the old array. It is allocate + copy.

That is the main cost source of ArrayList resizing.

Why insertion by index is slow

If you call list.add(index, element);, it is no longer a simple append. The source idea is:

Java

        public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

The key is System.arraycopy(...)

It shifts all elements after index one slot to the right.

Example: [A, B, C, D]

Insert X at position 1:

B, C, D all move right
then X is placed at position 1

Result: [A, X, B, C, D]

So middle insertion is slow not because index lookup is hard, but because element shifting is required.

Time complexity is O(n).

Why remove is also slow

Deletion is the reverse of insertion.

For example: list.remove(index);

Source idea:

Java

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

Three steps:

get old value
shift trailing elements left
set the last slot to null

Why set null at the end? This is important: elementData[--size] = null;

Purpose is to remove the obsolete reference so GC can reclaim the object.

If not cleared, size gets smaller but the array may still hold old references, delaying memory release.

This is a typical memory-management detail in the source.

Why get is so fast

get(index) is roughly:

Java

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

This is essentially array index access.

Because storage is contiguous, index access is direct and does not require traversal, so it is O(1).

This is the biggest performance advantage of ArrayList.

Why set is also fast

set(index, element) just overwrites one position:

Java

        public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

No element shifting is needed, so it is also usually O(1).

Why null and duplicates are allowed

ArrayList does not deduplicate values and does not forbid null.

It behaves as an ordered container, not a uniqueness-enforcing set.

For example:

Java

        list.add(null);
list.add("A");
list.add("A");

All are valid.

This differs from Set. List focuses on order and index positions, not uniqueness.

Why ConcurrentModificationException appears during iteration

This is related to modCount in the source.

ArrayList hierarchy has: protected transient int modCount = 0;

Every structural modification (such as add, remove, clear, growth-related structure change) usually increments modCount. When an iterator is created, it records: int expectedModCount = modCount;

On every iteration step, it checks whether current modCount still equals expectedModCount.

If not equal, the collection was externally modified during iteration, so it throws ConcurrentModificationException.

This is the fail-fast mechanism. It is not for thread safety, but to detect incorrect usage as early as possible.

Example:

Java

        for (String s : list) {
    if (s.equals("A")) {
        list.remove(s);
    }
}

Enhanced for uses an iterator underneath. You iterate and directly modify the list itself, so version numbers diverge and the iterator fails immediately.

Why Iterator.remove works: Because iterator-managed remove updates its own state and expectedModCount together, so no conflict occurs.

This is a common interview topic from ArrayList internals.

Why ArrayList is not thread-safe

Most operations do not use locks.

Example: two threads execute at the same time:

Java

        list.add("A");
list.add("B");

Inside add, operations include:

read size
check capacity
write into array
size++

These steps are not atomic. With concurrent writes, you can get:

overwrite
wrong size value
array out-of-bounds
lost data

So ArrayList is unsafe for concurrent write scenarios.

Why toArray is meaningful

Although ArrayList uses an array internally, it does not expose that internal array directly because:

internal array capacity may exceed valid element count
exposing it directly would break encapsulation

So toArray() exists to:

return a new array copy containing only valid elements
prevent external code from mutating internal storage directly

This reflects the encapsulation principle in source design.

A simplified ArrayList for full understanding

Java

        class MyArrayList<E> {
    private Object[] data = new Object[10];
    private int size = 0;

    public void add(E e) {
        if (size == data.length) {
            grow();
        }
        data[size++] = e;
    }

    public E get(int index) {
        checkIndex(index);
        return (E) data[index];
    }

    public E remove(int index) {
        checkIndex(index);
        E oldValue = (E) data[index];
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }
        data[--size] = null;
        return oldValue;
    }

    private void grow() {
        int newCapacity = data.length + (data.length >> 1);
        Object[] newData = new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
    }
}

Collapse

Time complexity

This is the key part to understand ArrayList:

Index access: O(1) Reason: underlying structure is an array, so direct positioning is possible.
Tail add: amortized O(1) Most of the time, append directly to the end. If growth happens at that moment, it degrades to O(n) due to copying.
Middle insertion: O(n) Elements after the index must be shifted right.
Middle deletion: O(n) Elements after the index must be shifted left.
Search by value: O(n) Usually requires linear scan.

So ArrayList:

Advantages: Fast reads by index, and append is usually efficient.

Disadvantages: Middle insertion and deletion are slow.

Fonnpo

The Complete Spring Framework Guide

Detailed Analysis of HashMap

Detailed Analysis of LinkedList