Walk through what happens when an ArrayList outgrows its backing array, and quantify the cost of building a large list from the default capacity versus pre-sizing.

## ArrayList internals An **ArrayList** is a resizable list backed by a single `Object[] elementData`. It tracks two numbers: - **size** — how many elements you've added (what `size()` returns), - **capacity** — the length of `elementData` (not exposed publicly). The default initial capacity is **10** (technically the array is allocated lazily on the first add). Reads and appends index directly into the array, giving O(1) access and amortized-O(1) append. ## The grow-and-copy cycle When you call `add` and `size == capacity` (the array is full), ArrayList must grow: 1. **Compute new capacity:** `newCapacity = oldCapacity + (oldCapacity >> 1)` — i.e. old plus half of old, **≈ 1.5x**. (From the default of 10, capacities go 10 → 15 → 22 → 33 → 49 → …) 2. **Allocate** a new `Object[]` of that length. 3. **Copy** all `size` existing references into it via `System.arraycopy` (a fast bulk memory copy, but still O(size)). 4. **Replace** the field with the new array; the old array becomes **garbage**. 5. Place the new element and increment size. Note it copies **references**, not deep copies of the objects — so the per-element cost is small, but it scales with the current size and happens repeatedly. ## Quantifying the cost Growth by a constant factor (1.5x) means the number of resizes for `n` elements is **logarithmic** — about `log_1.5(n / 10)`. For n = 1,000,000 that's roughly **30 resizes**. The total number of elements copied across all resizes is a geometric series that sums to roughly **2–3× n** (a few million reference copies for a million-element list). You also create ~30 intermediate arrays that immediately become garbage — extra work for the **garbage collector** (the JVM subsystem that reclaims unused memory). ### Why this is 'amortized O(1)' yet still worth avoiding **Amortized O(1)** means: averaged over all `n` appends, each costs a constant amount, because the expensive resizes get geometrically rarer. The *total* work is O(n) — you can't beat linear. So no individual add is slow, and you won't get an asymptotic blow-up. **But** that O(n) of copying is *avoidable overhead* when you already know `n`: it produces nothing you keep, and it generates GC garbage that can cause pauses on latency-sensitive paths. ## Pre-sizing If you know (or can bound) the final size, allocate it once: ```java List<Foo> list = new ArrayList<>(expectedSize); ``` Now appends never trigger a resize (assuming the estimate holds): one allocation, zero copies, zero intermediate garbage. If you're copying from a known source, `new ArrayList<>(sourceCollection)` sizes itself automatically. ## Related buffers The same principle applies to other array-backed structures: - **StringBuilder** grows its `char[]` similarly; `new StringBuilder(expectedLength)` avoids reallocations when concatenating many pieces. - **HashMap/HashSet** have an analogous but distinct concern (load factor + rehash — see the dedicated question). - Raw arrays/buffers on hot paths: allocate to the known size once rather than growing. ## Caveats - **Over-sizing** wastes memory (a large, partly-empty array) and hurts cache locality. ArrayList never auto-shrinks; call `trimToSize()` if you over-allocated and want the slack back. - **Unknown size:** if you genuinely can't estimate, default growth is fine — it's already efficient. Don't guess wildly. - This is a **micro-optimization**: apply it where size is known and the path is hot; don't litter every list with capacity arguments.