You batch-load a million IDs into an ArrayList. Almost every add is a store into the next empty slot. One of them allocates a bigger array and copies the million. If that copy lands on a request thread, “usually constant time” is not the SLA.

A dynamic array is a contiguous backing store whose used length and allocated length are not the same number. Growth is geometric — doubling in the textbook, roughly 1.5× in Java — so a long sequence of appends is amortized O(1). The next call is still allowed to be O(n). Terms like ADT, amortized, and contiguous are defined once on the Data Structures Roadmap; this post is the layout.

Size is not capacity

The structure is an array plus two integers. Capacity is how many slots exist. Size is how many of those slots currently hold an element. Index i is still pointer arithmetic — same contiguous idea as a fixed array — as long as i < size.

A tiny sketch, not a JDK clone:

final class IntList {
    private int[] data;
    private int size;

    IntList(int capacity) {
        this.data = new int[capacity];
        this.size = 0;
    }

    int get(int i) {
        if (i < 0 || i >= size) {
            throw new IndexOutOfBoundsException(i);
        }
        return data[i];
    }

    int size() {
        return size;
    }

    int capacity() {
        return data.length;
    }
}

After three appends into a list that started with capacity 8, size is 3 and data.length is 8. get(2) is O(1). get(5) is an error, even though slot 5 exists. Callers never see the spare slots; the spare slots are how the next few appends stay cheap.

Note: An empty ArrayList in modern JDKs does not even allocate ten slots up front. The first add grows to the default capacity of 10. Capacity is an implementation detail until you ask for it with ensureCapacity or the sized constructor.

Append until the array is full, then copy

The cheap path is a store and a size bump. The expensive path is allocate, copy, then store:

void add(int value) {
    if (size == data.length) {
        grow();
    }
    data[size] = value;
    size++;
}

void grow() {
    int newCap = Math.max(1, data.length * 2);
    int[] next = new int[newCap];
    System.arraycopy(data, 0, next, 0, size);
    data = next;
}

Textbooks double. Java’s ArrayList grows by about one and a half: oldCapacity + (oldCapacity >> 1). Both are geometric. Geometric is the property that makes the amortized argument work.

A constant bump — always +10 — would copy too often. The total copy cost would grow with n², and “append is cheap on average” would be a lie.

After a grow, unused slots sit at the tail until size catches up. That leftover is the rent you pay for not copying on every append.

Why a sequence of appends is amortized O(1)

Take doubling, start at capacity 1, append n times. Copies happen at 1, 2, 4, 8, … up to n. The copies across all grows sum to less than 2n, so each of the n appends paid a constant on average.

append 1  -> grow 1 -> 2     copy 1
append 2  -> grow 2 -> 4     copy 2
append 4  -> grow 4 -> 8     copy 4
append 8  -> grow 8 -> 16    copy 8
...
total copies < 2n
n appends / 2n copies  ->  amortized O(1) per add

The same story holds for 1.5× with a worse constant: more grows, less idle capacity on average. Either way, amortized is not a guarantee on the next call — that sentence lives on the hub for a reason. One add in a million can still be O(n). Do not put that add on a latency-critical path if n is already huge and you refused to size the list.

Ask for the room you already know you need

If the batch job knows it will load a million IDs, paying for seven or eight full copies on the way up is a choice, not a law. ensureCapacity (or new ArrayList<>(n)) does the grow once:

List<String> ids = new ArrayList<>(1_000_000);

for (String id : source) {
    ids.add(id); // no grow, unless source lied
}

ensureCapacity on an existing list is the same idea after construction:

List<String> ids = new ArrayList<>();
ids.ensureCapacity(1_000_000);

Size the list when you know n. The geometric argument is for the case where you do not. Passing a guessed capacity that is only slightly low still grows once; passing nothing when you already have source.size() is the waste.

Insert at 0 still slides everything

Growth is about the tail. Insert or delete at an arbitrary index is a different bill: every later element moves one slot. Prepend is the worst of those — index 0 — because the whole used range slides:

void add(int index, int value) {
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException(index);
    }
    if (size == data.length) {
        grow();
    }
    System.arraycopy(data, index, data, index + 1, size - index);
    data[index] = value;
    size++;
}

A loop that prepends n keystrokes into an ArrayList is O(n²). Random access stays O(1); the hot operation is the slide. If the hot path is “push on the left,” this is the wrong layout — the hub’s JDK map points at ArrayDeque for both ends.

Note: list.add(0, x) and list.remove(0) are honest APIs. They are not cheap APIs. The method name does not mention the copy.

Java’s ArrayList is this layout

java.util.ArrayList is a dynamic array of references: an Object[], a size, and a grow that prefers 1.5×. get / set are O(1). add at the end is amortized O(1). add(index, e) and remove(index) are O(n). contains walks.

Reach for ArrayList when you want a growable indexed list. Do not reach for Vector: it is the same layout with a lock on every get and a doubling grow (unless you set capacityIncrement). If you need a concurrent list, you want a concurrent type, not 1998’s synchronized wrapper.

Three construction shapes:

List<String> names = new ArrayList<>();          // growable, unsynchronized
List<String> named = new ArrayList<>(rows.size()); // sized when n is known
String[] fixed = new String[rows.size()];        // no grow, no leftover capacity

Vector belongs in the “avoid as a default” column of the roadmap JDK map. The name matches the textbook. The type does not match modern Java.

Complexity

Read this as a shopping list. There is no fastest structure — there is a structure whose expensive operations are ones you rarely perform.

OperationCostWhy
get(i) / set(i, e)O(1)Contiguous index
add(e) (append)amortized O(1)Store, or occasional grow+copy
add(i, e) / remove(i)O(n)Slide the tail
add(0, e) / remove(0)O(n)Slide everything
contains(e) / index scanO(n)No extra index
SpaceO(capacity)Capacity ≥ size; leftover after grow

The grow itself is O(n) when it runs. That is already folded into the amortized append row. Do not quote “append is O(1)” in a design review without the word amortized.

When not to use a dynamic array

Skip the growable list when:

  • You already know n — a T[] (or new ArrayList<>(n) if you still want the List API) avoids leftover capacity and the grow copies. Wrapping a known-size array in an ArrayList “just in case” is the waste the hub warns about.
  • The hot path is prepend or mid-list splice. Every insert at 0 copies size references. A deque (ArrayDeque) makes both ends cheap and gives up cheap index i. That trade is honest if you never ask for index i.
  • A single append must be bounded. Amortized O(1) is a statement about a sequence. A latency budget on the next call needs either a pre-sized list or a structure that does not copy the whole payload on grow.
  • You needed uniqueness or a key lookup. contains on an ArrayList is a scan. That is a set/map job, not a list job.

Huge n with a wild overestimate of capacity wastes RAM the same way a wild underestimate wastes copies. Size from a real count when you have one.

Cheat sheet

The layout in one block:

Backing:     T[] + size   (capacity = array.length)
get / set:   O(1)
append:      amortized O(1)  — next add may still be O(n)
insert(0):   O(n)            — the used range slides
grow:        geometric (2× textbook, ~1.5× ArrayList)
known n:     new ArrayList<>(n) or T[]
JDK:         ArrayList, not Vector
both ends:   ArrayDeque, not add(0) in a loop

Do:

  • Treat size and capacity as different numbers.
  • Call ensureCapacity / the sized constructor when you know n.
  • Pick this layout for index i and append-at-tail.

Don’t:

  • Quote append as O(1) without amortized.
  • Prepend in a loop and blame the JVM.
  • Default to Vector because the textbook said “vector.”

Wrap-up

A dynamic array is a fixed array that buys spare slots so most appends are a store. Geometric growth makes a sequence of those appends amortized O(1). It does not make the next add O(1), it does not make insert at 0 cheap, and it does not beat a T[] when you already know n.

In Java the type is ArrayList: 1.5× grow, unsynchronized, indexed. Size it when you can. Leave Vector in the archive. When the hot operation is not “index i or append,” pick a different row on the roadmap.

Next optional step in the series When splice is the hot path, nodes beat sliding a block. Linked Lists: Singly, Doubly, and Circular