How Java ArrayList Works Internally: Building a Dynamic Array from Scratch

During a high-traffic Black Friday checkout event, thousands of order items are appended to a shared list every second. As order volumes spike, processing latency jumps unexpectedly every time the list reaches capacity. But standard Java arrays have a rigid constraint: once created with a size of 10, their length is permanently locked.

If a user tries to add an 11th item to a 10-element array, Java throws an ArrayIndexOutOfBoundsException and crashes the user’s checkout session.

To avoid hard limits, you could create an array of size 1,000,000 upfront. But doing that for 100,000 active users consumes gigabytes of memory for unused array slots.

This dilemma is why ArrayList exists. It wraps a standard fixed array and automatically resizes itself when full.

Why You Need This in Real Life

If dynamic arrays resize automatically, why should you care how they work under the hood?

Because naive usage creates hidden performance bottlenecks:

Resizing Latency Spikes: When a dynamic array fills up, appending an item forces the JVM to allocate a brand new array and copy every single existing element over. If this happens mid-request, response latency spikes.
Memory Waste: If an array expands right before an operation stops, up to 33% of the allocated memory sits empty.
Loitering Objects: Removing an element without clearing its array slot traps object references in memory, creating memory leaks.

Understanding resizing mechanics helps you choose smart initial capacities and prevent GC pressure.

A Hypothetical Production Horror Story: The Default Capacity Trap

Suppose your microservice processes 500,000 incoming webhooks per batch.

A developer writes this code:

List<WebhookEvent> events = new ArrayList<>(); // Default capacity = 10!
for (WebhookEvent e : incomingPayload) {
    events.add(e);
}

Because the list starts with a default capacity of 10, adding 500,000 events forces ArrayList to resize 28 consecutive times.

Every resize allocates a new array, copies hundreds of thousands of elements, and leaves the old array for garbage collection. The batch job takes 14 seconds instead of 300 milliseconds.

If the developer had specified new ArrayList<>(500_000), zero resizes would occur.

Core Fields and Internal Memory State

A custom dynamic list wraps a flat array and maintains a size counter:

Object[] elementData: The internal array holding elements.
int size: The counter tracking how many items the user has added.

State after adding 2 items ("A", "B") to an initial capacity 4 array:

elementData:  [ "A" | "B" | null | null ]
size:         2
capacity:     4 (elementData.length)

elementData.length represents total buffer capacity. size represents actual element count.

The Resizing Strategy

When size == elementData.length, the internal buffer is full. Adding another item triggers three steps:

Allocate a larger array in memory.
Copy existing elements from the old array into the new array using System.arraycopy().
Point the internal array reference to the new array.

BEFORE RESIZE (Full at capacity 4):
[ 10 | 20 | 30 | 40 ]

ALLOCATE & COPY (New capacity 6 = 4 + 4/2):
[ 10 | 20 | 30 | 40 | null | null ]
                      ^
                      Insert element 50 here

Java’s standard library uses a $1.5\times$ growth formula:

$\text{newCapacity} = \text{oldCapacity} + (\text{oldCapacity} \gg 1)$

Bit-shifting right by 1 divides by 2 efficiently. A $1.5\times$ growth factor balances memory overhead against copy frequency.

Step-by-Step Implementation

Here is our functional MyArrayList<T> implementation:

import java.util.Arrays;

public class MyArrayList<T> {
    private static final int DEFAULT_CAPACITY = 10;
    private Object[] elementData;
    private int size;

    public MyArrayList() {
        this.elementData = new Object[DEFAULT_CAPACITY];
        this.size = 0;
    }

    public MyArrayList(int initialCapacity) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Capacity cannot be negative: " + initialCapacity);
        }
        this.elementData = new Object[initialCapacity];
        this.size = 0;
    }

    public void add(T element) {
        ensureCapacity(size + 1);
        elementData[size++] = element;
    }

    @SuppressWarnings("unchecked")
    public T get(int index) {
        checkBounds(index);
        return (T) elementData[index];
    }

    @SuppressWarnings("unchecked")
    public T remove(int index) {
        checkBounds(index);
        T oldValue = (T) elementData[index];

        int numMoved = size - index - 1;
        if (numMoved > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        }

        elementData[--size] = null; // Clear reference to prevent memory leaks!
        return oldValue;
    }

    public int size() {
        return size;
    }

    private void ensureCapacity(int minCapacity) {
        if (minCapacity > elementData.length) {
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5x growth
            if (newCapacity < minCapacity) {
                newCapacity = minCapacity;
            }
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }

    private void checkBounds(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }
}

Why Nulling Out Removed Slots Prevents Memory Leaks

Notice line 39 in the remove() method:

elementData[--size] = null;

If you decrement size without assigning null to the vacated array slot, the internal array retains an object reference pointing into the heap.

Even if application code cannot access that element through public methods, the Java Garbage Collector considers the reference active. This causes a memory leak known as loitering objects.

Amortized $O(1)$ Time Complexity Explained

Copying an array takes $O(N)$ linear time. Why do we claim add() takes $O(1)$ constant time?

Consider inserting 17 items starting with capacity 1. Resizing occurs at size 1, 2, 4, 8, 16.

$\text{Total Copies} = 1 + 2 + 4 + 8 + 16 = 31 \text{ operations for 17 inserts}$

On average, each insertion causes fewer than 2 element copies.

The expensive $O(N)$ resize cost gets spread across $N$ single $O(1)$ appends. This mathematical averaging is called amortized constant time.

Quick Summary

MyArrayList wraps a standard array and tracks element count with a size field.
Full arrays trigger a $1.5\times$ expansion via Arrays.copyOf().
Removing an item requires shifting remaining elements left with System.arraycopy() and clearing the trailing slot to avoid GC leaks.

References & Further Reading

OpenJDK Repository. OpenJDK 21 Source Code: java.util.ArrayList. GitHub.
Oracle Corporation. Java SE 21 API Documentation: java.util.ArrayList. Oracle Docs.
Bloch, J. (2018). Effective Java (3rd Edition) — Item 64: Refer to Objects by Their Interfaces. Addison-Wesley.