Ch. 7 · Java

Java ArrayList Capacity and Performance

How ArrayList grows its backing array by 1.5x, why add is amortized O(1), and when ensureCapacity or a different list actually helps.

~8 min readbeginnerupdated Nov 1, 2026

“How does ArrayList work internally, and what is the time complexity of add?” sounds like trivia, but a complete answer covers three ideas: 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). All of it follows from one fact about plain Java arrays: the length is fixed at creation, so growing one means allocating a bigger array and copying.

elementData, size and the 1.5x growth rule

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 makes the array 50 percent larger, resizes get rarer as the list grows and the total copying stays proportional to the number of elements, 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.

What add() and grow() do when the array fills up

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;
    }
}
java

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.

From a growth trace to a presizing decision

Fifty adds, six resizes

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
java

Five resizes (the first one only allocates the initial ten slots) bring the capacity to 49. The 50th add triggers 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.

Cheap at the end, linear at the front

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
java

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.

Presizing when the final count is known

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

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.

When ArrayDeque 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.

Timing default, presized and front-insert loops

Capacity is private, but you can measure the effect of resizing with a short timing program. 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);
        }
    }
}
java

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.

A newest-first event buffer stuck in System.arraycopy

Picture a reporting job that builds a list of the most recent events and keeps only the latest 10,000. A 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);
    }
}
java

Under load, a CPU profile of this code 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)
    }
}
java

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.

Capacity and cost claims that lose interview points

  • 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.

What interviewers ask after the growth question

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 right after a resize (about a third of the new array is empty, against half with doubling), 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 question: merge 20 shards, then drop duplicates

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.

A strong answer

Merging with add in a loop is amortized O(n) for n = 100,000 total items, with 24 resizes counting the first allocation. 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 first records which elements match in a bit set and then compacts the survivors 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.

More on Java collections

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.

More in Java

read ✓Java · mid

Java Comparators and Ordered Collections

Why TreeSet and TreeMap drop elements when a Comparator disagrees with equals, and how to write comparators that obey the full contract.

~6 min readread →
esc