How does ArrayList grow its backing array, and how does that differ from HashMap's growth and from other list types?
answer
- ArrayList grows ~1.5x (oldCap + oldCap>>1), bulk arraycopy, no rehash
- Default cap 10, allocated lazily on first add
- No load factor — capacity = array length directly
- HashMap doubles + rehashes; LinkedList never resizes
- Presize: new ArrayList<>(expectedSize)
basics
~20 sWhen an ArrayList fills up, it makes a new array about 1.5x bigger and copies the elements over with no load factor involved. HashMap instead doubles its array and re-buckets every entry. LinkedList never resizes because it has no backing array.
solid answer
~50 sArrayList holds elements in a contiguous Object[]. When add() would overflow it, ensureCapacity grows the array by roughly 1.5x (newCap = oldCap + (oldCap >> 1)), then System.arraycopy moves the elements; positions don't change, so it's a cheap bulk copy. There's no load factor — the capacity is exactly the array length. The default starting capacity is 10, but a list created empty actually allocates lazily on first add. HashMap differs in two ways: it grows by doubling (powers of two) and it must rehash, redistributing every entry across buckets, which is costlier per element. LinkedList is different again: it stores each element in its own node with prev/next pointers, so it never resizes or copies on add — but it has higher per-element memory overhead and O(n) random access. ArrayDeque, like ArrayList, uses a resizable array (doubling) for its ring buffer. As with maps, presizing an ArrayList via new ArrayList<>(expectedSize) avoids the resize cascade.
go deeper
Knows ArrayList grows by making a bigger array and copying, and that you can set initial capacity.
States the ~1.5x factor, the no-load-factor distinction from HashMap, lazy default-10 allocation, and contrasts with LinkedList.
Explains why 1.5x (amortized O(1), memory vs copy trade-off), the no-rehash bulk-copy nature, and compares ArrayDeque/CopyOnWriteArrayList; uses trimToSize.
Reasons about cache behaviour, allocation/GC at scale, and sets defaults (ArrayList-first, presize known sizes) backed by measurement rather than folklore.
## ArrayList: a growable array `ArrayList` stores its elements in a single contiguous backing array, `Object[] elementData`. Index access is a direct array read — O(1) and cache-friendly. The cost is growth: arrays can't be resized in place. ### Growth mechanics - **Default capacity 10**, but created lazily: `new ArrayList<>()` starts with an empty shared array and allocates the length-10 array on the **first** `add`. - When an `add` would exceed the current capacity, `grow()` computes a new capacity of about **1.5×** the old: `newCapacity = oldCapacity + (oldCapacity >> 1)` (`>> 1` is integer divide-by-two). So 10 → 15 → 22 → 33 → 49 → ... - It then copies the old elements into the new array with `System.arraycopy`, a fast bulk memory move. Crucially, **element positions are unchanged** — index i stays index i — so there is **no rehashing**, just a copy. ### Why 1.5× (not 2×)? Growing by a constant factor keeps the *amortized* cost of `add` at O(1) (total copying across all growths is O(n)). 1.5× is a compromise: it wastes less memory than doubling, and the freed old arrays can sometimes be reused to satisfy a later allocation. Doubling would copy fewer times but waste up to ~50% memory. ## HashMap growth — for contrast `HashMap` grows by **doubling** (capacity is always a power of two) and, critically, must **rehash**: because a key's bucket index is `hash & (capacity - 1)`, growing the table changes where entries belong, so every entry is redistributed across the new buckets. That makes a HashMap resize more expensive *per element* than an ArrayList resize (which is a plain bulk copy with no recomputation). Also, HashMap has a **load factor** (0.75) that triggers growth before the table is full; ArrayList has **no load factor** — it grows only when actually full, and its capacity argument is the array length directly. ## Other list/collection types - **LinkedList:** a doubly-linked list of nodes, each holding the element plus `prev`/`next` references. It **never resizes or copies** on add/remove at the ends (O(1)), but pays high per-element memory (two extra pointers + node object) and O(n) random access (must walk the chain). For most workloads `ArrayList` is faster despite resizing, because contiguous arrays are cache-friendly. - **ArrayDeque:** backed by a resizable circular array (ring buffer) that **doubles** when full; like ArrayList it's array-based and benefits from presizing. - **CopyOnWriteArrayList:** copies the *entire* backing array on every mutation — presizing the initial array helps little because each write reallocates; it's for read-heavy, rarely-written concurrent use. ## Practical guidance - Presize when you know the size: `new ArrayList<>(expectedSize)` — the argument is the array length directly (no /0.75 needed). - Prefer `ArrayList` over `LinkedList` by default; choose `LinkedList` only for frequent end-insertion with no indexing, and even then `ArrayDeque` is usually better for queue/stack use. - Call `trimToSize()` if a list grew large then shrank and you want to reclaim the slack. ## Summary table | Type | Storage | Growth | Rehash on grow? | Load factor | |---|---|---|---|---| | ArrayList | contiguous array | ~1.5× | no (bulk copy) | none | | HashMap | bucket array | 2× | yes | 0.75 | | ArrayDeque | ring buffer array | 2× | no | none | | LinkedList | linked nodes | n/a (no array) | n/a | n/a |
- Why is an ArrayList resize cheaper per element than a HashMap resize?ArrayList keeps element positions, so growth is a single System.arraycopy bulk move with no per-element computation. HashMap must rehash: each entry's bucket index depends on capacity, so growing the table redistributes every entry across new buckets — extra per-element work.
- If memory matters after a list shrinks dramatically, how do you reclaim the unused capacity?Call list.trimToSize(), which reallocates the backing array down to the current size, freeing the slack. (And presize on construction to avoid over-allocating in the first place.)
saying these in an interview costs you the question
- Saying ArrayList doubles like HashMap — it grows ~1.5x
- Claiming ArrayList has a load factor — it doesn't
- Thinking ArrayList rehashes on grow — it just bulk-copies, positions unchanged
- Saying LinkedList resizes a backing array — it has none; it's linked nodes
- Recommending LinkedList for general use over ArrayList for performance — usually the opposite