Java ArrayList Capacity and Performance

“How does ArrayList work internally, and what is the time complexity of add?” is one of the first collection questions in a Java interview. It sounds like trivia, but the interviewer is checking whether you understand the difference between a list’s size and its capacity, why a resizing array still gives constant-time appends on average, and which operations quietly become linear.

A good answer moves from the data structure (a plain array plus a counter) to the cost model (amortized constant append, linear middle insert) to a practical decision (when presizing helps and when LinkedList is the wrong fix).

Before you start

You should be comfortable with Java arrays, generics and the List interface, and know what Big-O notation means. It helps to remember that a Java array has a fixed length once created: you can never grow an array in place, only allocate a larger one and copy. Everything about ArrayList follows from that one restriction.

The short answer

ArrayList keeps its elements in an Object[] called elementData and a size field. When an add finds the array full, it allocates a new array roughly 1.5 times larger (old + old >> 1) and copies the elements across with System.arraycopy. Because each resize doubles the work it postpones, the copying cost averages out, so add(e) is amortized O(1), get(i) is O(1), and add(0, e) or remove(0) are O(n) because every later element shifts.

How it works

Strip away the bounds checks and modification counting and the OpenJDK implementation looks like this:

import java.util.Arrays;

public class TinyArrayList<E> {
    private static final Object[] EMPTY = {};
    private Object[] elementData = EMPTY;
    private int size;

    public boolean add(E e) {
        if (size == elementData.length) {
            grow(size + 1);
        }
        elementData[size++] = e;
        return true;
    }

    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = (oldCapacity == 0)
                ? Math.max(10, minCapacity)          // first add allocates 10 slots
                : oldCapacity + (oldCapacity >> 1);  // then grow by about 50 percent
        if (newCapacity < minCapacity) {
            newCapacity = minCapacity;
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    @SuppressWarnings("unchecked")
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException(index);
        }
        return (E) elementData[index];
    }

    public int size() {
        return size;
    }
}

Three details matter in an interview. First, new ArrayList<>() does not allocate ten slots up front. Since Java 8 it points at a shared empty array and allocates the default capacity of 10 on the first add, so empty lists are cheap. Second, size is how many elements you stored and capacity is elementData.length. The public API exposes size() but no capacity(), so you can influence capacity but not read it. Third, the array holds references, not objects. Growing a list of a million String references copies a million pointers, not the strings.

The amortized argument goes like this. Starting from 10 and growing by 1.5x, the capacities are 10, 15, 22, 33, 49 and so on. To reach n elements, the total number of copied references across all resizes is a geometric series bounded by a small constant times n. Spread over n adds, that is a constant per add. Any individual add can still cost O(n) when it triggers a resize, which is why latency-sensitive code sometimes presizes.

Step-by-step walkthrough

Step 1: Trace the growth sequence

Write out what happens as you add elements one by one to a default list:

List<Integer> list = new ArrayList<>();
for (int i = 0; i < 50; i++) {
    list.add(i);
}
// capacity history: 0 -> 10 -> 15 -> 22 -> 33 -> 49 -> 73
// resizes happen on the adds that make size 1, 11, 16, 23, 34 and 50

Five copies were needed to grow past 49 elements. The 50th add triggered a sixth resize to 73, and the 23 spare slots are wasted until more elements arrive. Saying this out loud shows the interviewer you know the growth factor is a trade-off between copy frequency and slack memory.

Step 2: Separate cheap and expensive operations

Not every list operation benefits from the array layout:

list.get(25);        // O(1): direct index into elementData
list.set(25, -1);    // O(1)
list.add(99);        // amortized O(1): append at size
list.add(0, 99);     // O(n): System.arraycopy shifts every element right
list.remove(0);      // O(n): shifts every element left
list.remove(list.size() - 1); // O(1): nothing to shift
list.contains(42);   // O(n): linear scan using equals

The pattern is simple: work at the end is cheap, work at the front or middle shifts the tail. contains and indexOf are linear because the list has no hashing or ordering to exploit.

Step 3: Presize when you know the count

If you are converting 100,000 database rows into objects, you know the final size before the loop starts:

List<Order> orders = new ArrayList<>(rows.size());
for (Row row : rows) {
    orders.add(Order.from(row));
}

The constructor argument sets the initial capacity, so the loop never resizes. For a list that already exists, ensureCapacity(n) does the same before a bulk insert, and addAll(collection) grows once to fit the whole batch. After building a large, long-lived list that will not grow again, trimToSize() drops the unused slack.

Step 4: Decide whether a different structure is the real fix

If profiling shows time spent in add(0, e) or remove(0), the answer is usually ArrayDeque, not LinkedList. ArrayDeque is a circular array with O(1) operations at both ends and the same cache-friendly layout. LinkedList allocates a node per element, chases pointers on every traversal and has O(n) indexed access, so it loses to ArrayList in most real benchmarks even for workloads people expect it to win.

Worked scenario

A reporting job builds a list of the most recent events and keeps only the latest 10,000. The first version looks reasonable:

List<Event> recent = new ArrayList<>();

void onEvent(Event e) {
    recent.add(0, e);              // newest first
    if (recent.size() > 10_000) {
        recent.remove(recent.size() - 1);
    }
}

Under load the CPU profile shows most time inside System.arraycopy. Each add(0, e) shifts up to 10,000 references, so a million events cost about ten billion reference moves. The data structure matches the access pattern badly: inserts happen at the front.

The fix keeps appends at the cheap end and uses a deque for bounded history:

private final ArrayDeque<Event> recent = new ArrayDeque<>(10_001);

void onEvent(Event e) {
    recent.addFirst(e);            // O(1) on a circular buffer
    if (recent.size() > 10_000) {
        recent.removeLast();       // O(1)
    }
}

If callers need a List snapshot, new ArrayList<>(recent) copies once per read instead of shifting on every write. The broader lesson: when an ArrayList is slow, check where in the list you are modifying before blaming the resize policy.

Common mistake

• Saying capacity doubles. That is true for some other languages and older textbooks, but ArrayList grows by about 1.5x. Vector is the class that doubles by default.
• Confusing capacity with size. new ArrayList<>(100) creates an empty list. Calling list.set(5, x) on it throws IndexOutOfBoundsException because size is still zero.
• Claiming add is always O(1). It is amortized O(1). A single add that triggers a resize is O(n), which matters for tail latency.
• Reaching for LinkedList for “fast inserts”. Finding the insertion point in a linked list is already O(n), and per-node allocation hurts. Use ArrayDeque for both ends, or rethink the algorithm.
• Presizing everything. Guessing a huge initial capacity for lists that usually stay small wastes memory on every instance. Presize when you know, not when you hope.

Verify the behavior

Capacity is private, but you can measure the effect of resizing with a simple timing harness. Use JMH for real numbers; this sketch is enough to see the shape:

import java.util.ArrayList;
import java.util.List;

public class GrowthDemo {
    public static void main(String[] args) {
        int n = 5_000_000;
        for (int round = 0; round < 5; round++) {
            long t0 = System.nanoTime();
            List<Integer> a = new ArrayList<>();
            for (int i = 0; i < n; i++) a.add(i);

            long t1 = System.nanoTime();
            List<Integer> b = new ArrayList<>(n);
            for (int i = 0; i < n; i++) b.add(i);

            long t2 = System.nanoTime();
            List<Integer> c = new ArrayList<>();
            for (int i = 0; i < 50_000; i++) c.add(0, i);
            long t3 = System.nanoTime();

            System.out.printf("default=%dms presized=%dms frontInsert50k=%dms%n",
                    (t1 - t0) / 1_000_000, (t2 - t1) / 1_000_000, (t3 - t2) / 1_000_000);
        }
    }
}

Run it with java GrowthDemo.java. Expect the presized loop to be modestly faster than the default one, and the front-insert loop to be dramatically slower per element even though it adds a hundred times fewer items. Ignore the first round, which includes JIT warm-up.

Follow-up questions

What is the default capacity, and when is it allocated? Ten, allocated lazily on the first add. A list created with new ArrayList<>() and never used holds no array of its own.

Why 1.5x and not 2x? A smaller factor wastes less memory after a resize and lets freed blocks be reused more easily by the allocator, at the cost of slightly more frequent copies. Both factors give amortized O(1).

Is ArrayList thread-safe? No. Concurrent adds can lose elements or throw ArrayIndexOutOfBoundsException during a resize. Use Collections.synchronizedList, CopyOnWriteArrayList for read-mostly data, or confine the list to one thread.

Does removing elements shrink the array? No. remove and clear null out slots so the garbage collector can reclaim the elements, but the array keeps its length until you call trimToSize().

What happens to an iterator if the list is modified during iteration? The iterator checks modCount and throws ConcurrentModificationException. Remove through iterator.remove() or removeIf instead.

Interview exercise

A service merges results from 20 shards, each returning about 5,000 items, into one ArrayList, then removes items flagged as duplicates by calling list.remove(i) inside an index loop. Explain the complexity of the current code and propose a better version.

Answer and reasoning

Merging with add in a loop is amortized O(n) for n = 100,000 total items, with around 25 resizes. That part is fine, though new ArrayList<>(expectedTotal) or addAll per shard avoids the resizes entirely. The real problem is removal: each remove(i) shifts every element after i, so removing k items is O(k * n), which approaches O(n squared) when many items are duplicates. Index loops that remove also skip the element that slides into position i unless they decrement the index.

The better version is list.removeIf(Item::isDuplicate). ArrayList.removeIf marks the survivors first and then compacts the array in a single pass, so the whole removal is O(n). Alternatively, filter while merging so duplicates never enter the list. The reasoning an interviewer wants is that the cost hides in the shifting, not in the growth.

Continue learning

Practise more collection questions in the Java interview questions and check yourself with the Java MCQs. Related notes: ConcurrentModificationException explained and HashMap collisions and key quality. The official contract, including the note that growth policy details are unspecified beyond amortized constant time, is in the ArrayList API documentation.