You have a bag of open orders and you will append, then look up by index, then maybe drop a cancelled one. new ArrayList<>() is the type you already type. It is also the type whose one expensive call copies every reference in the backing array.
ArrayList is the default List: an Object[] that grows. The series hub owns fail-fast, RandomAccess, and views vs copies. This post is the class: amortized append, O(1) get / set, ensureCapacity, and the moments growth or add(0) make you pick something else. Amortized growth as a layout lives on Dynamic Arrays — here we only care what java.util.ArrayList actually does.
The lab is the same checkout domain the hub uses: Order and LineItem. If records are new, Java Records is the shape.
The list you already type
An open-orders board is a list. Duplicates are allowed (two carts can hold the same SKU shape). Index 0 is the oldest open order. That is a List job, and ArrayList is how the JDK usually delivers it:
import java.util.ArrayList;
import java.util.List;
public final class OpenOrders {
public static List<Order> activeOnly(List<Order> source) {
List<Order> open = new ArrayList<>(source.size());
for (Order order : source) {
if (order.active()) {
open.add(order);
}
}
return open;
}
}source.size() is a known n. Passing it to the constructor is the first decision this post cares about: size the list when you already know how many adds you will do. The loop then stores into spare slots. No grow, no copy.
Index work is the reason this class exists:
Order oldest = open.get(0);
open.set(0, oldest);
LineItem firstSku = open.get(0).items().get(0);get and set are pointer arithmetic on a contiguous array. They stay O(1) whether the list holds three orders or thirty thousand. That is the contract you are buying.
API and cost: pick by the hot operation
Program to List. new ArrayList when the hot path is index or append-at-tail. Read the table as a shopping list, not as “fastest collection.”
| Method | Cost | When it is the reason you picked ArrayList |
|---|---|---|
get(i) / set(i, e) | O(1) | Random access; the hub RandomAccess marker |
add(e) (append) | amortized O(1) | The everyday growable list |
add(i, e) / remove(i) | O(n) | Later elements slide with System.arraycopy |
add(0, e) / remove(0) | O(n) | The whole used range slides |
addAll(c) | O(c + grow) | One grow to size + c.size(), then a block copy |
contains(e) / indexOf | O(n) | A scan — not a Set |
ensureCapacity(n) | O(n) if it grows | Pay the copy once, before a known bulk add |
trimToSize() | O(size) | Drop leftover capacity after a large load |
subList(from, to) | O(1) to wrap | A view — see List |
listIterator() | O(1) to create | Fail-fast; Iterator.remove is the safe in-flight delete |
add is not always O(1). The long run of appends is amortized constant. The call that fills the array allocates a larger Object[] and copies every live reference. That one call is O(n).
Nulls are legal. open.add(null) compiles and indexes like any other slot. That is a feature when a missing line item is a real value; it is a footgun when a later order.total() NPE is how you discover it.
ArrayList is not thread-safe. Another thread mutating while you get is a data race, not a ConcurrentModificationException you can “handle.” For many readers and rare writes, Copy-On-Write is the list with snapshot iterators. Collections.synchronizedList is a lock around each method — you still lock the iterator yourself; that wrapper lives in Collections and Arrays. Neither is a default for a request-scoped open-orders list.
The backing array: size is not capacity
The implementation is an Object[] named elementData, an int size, and a modCount for the iterator. Capacity is elementData.length. Size is how many slots currently hold an element. Callers never see the spare tail; the spare tail is how the next few adds stay a store.
List<LineItem> items = new ArrayList<>();
items.add(new LineItem("SKU-1", 2, new BigDecimal("9.99")));
items.add(new LineItem("SKU-2", 1, new BigDecimal("4.50")));After two adds from the default constructor, size is 2. Capacity is 10. get(1) is O(1). get(5) throws, even though slot 5 exists inside the array.
An empty new ArrayList<>() does not allocate ten slots. Since Java 8 (and 7u51) the no-arg constructor shares a zero-length DEFAULTCAPACITY_EMPTY_ELEMENTDATA. The first add allocates DEFAULT_CAPACITY, which is 10. Construction of a million empty lists is cheap; the first insert on each one is the allocation.
The sized constructor is the other empty:
List<Order> guessed = new ArrayList<>(0);
List<Order> known = new ArrayList<>(source.size());
List<Order> def = new ArrayList<>();new ArrayList<>(0) uses a different empty array (EMPTY_ELEMENTDATA). The first add grows to 1, then 2, then 3 — 1.5× integer math from a tiny start — instead of jumping to 10. That is a real cost if you then append a thousand orders in a loop. Prefer the no-arg constructor or a real n, not 0 as a cargo-cult “save memory” argument.
There is no public capacity() method. size() is the API. Capacity is a knob you turn with the constructor, ensureCapacity, and trimToSize.
Growth copies the whole array
When size == capacity, the next append cannot store. grow allocates a larger array and copies. Java 8+ prefers about 1.5×: oldCapacity + (oldCapacity >> 1). From the default 10 that is 10 → 15 → 22 → 33 → 49 → 73 → 109. Textbooks double; ArrayList does not. Both are geometric, which is the property that makes a sequence of appends amortized O(1). The layout argument is on Dynamic Arrays; do not re-derive Big-O here.
A faithful sketch of the Java 8+ path — the empty-array identity is the fork between “jump to 10” and “grow from 1”:
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private Object[] elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
return elementData = java.util.Arrays.copyOf(elementData, newCapacity);
}
int cap = Math.max(DEFAULT_CAPACITY, minCapacity);
return elementData = new Object[cap];
}The first add on a no-arg list is still the shared empty array, so it lands on 10 (or minCapacity if you addAll twenty items on that empty default list). new ArrayList<>(0) is a different empty array, so the same oldCapacity == 0 takes the 1.5× branch and copies to length 1. Every later overflow copies size references into a new Object[]. The old array becomes garbage.
That copy is the call that “bites.” A batch loader that appends a million orders without a sized constructor pays for a handful of full-array copies on the way up. If that copy lands on a request thread, amortized is not the SLA. The next add after a resize is not O(1). The long run still is.
addAll is kinder than a handwritten loop of add. It asks the source for toArray(), then grows once to size + newCount if needed, then System.arraycopys the block:
List<LineItem> items = new ArrayList<>();
items.addAll(order.items());A for of add on an unsized list can grow several times. addAll of a collection that knows its size grows once. Use addAll when you already have a Collection. Use ensureCapacity when you only have a count and a loop.
ensureCapacity and trimToSize
You know the warehouse feed is 50_000 active orders. Ask for the room before the loop:
List<Order> open = new ArrayList<>();
open.ensureCapacity(50_000);
for (Order order : feed) {
if (order.active()) {
open.add(order);
}
}ensureCapacity(50_000) on a default empty list allocates one array of at least 50_000 and copies nothing useful (size is still 0). Each later add is a store. The sized constructor new ArrayList<>(50_000) does the same allocation up front and is the clearer form when you have n at construction.
Note: ensureCapacity(n) on a still-empty default list is a no-op when n <= 10. The first add will still grow to 10. That only matters if you thought ensureCapacity(8) pre-allocated eight slots; it did not. For bulk work, pass a real n, not a number under the default.
trimToSize copies down to size so leftover capacity can be collected:
open.removeIf(order -> !order.active());
open.trimToSize();Reach for it after a one-time load that overshot, or after you ensureCapacity’d a worst case and then kept a tenth of the rows. Do not trim after every request. The copy costs the same shape as a grow, and the next add will grow again.
add(0) still slides everything
Growth is about the tail. Insert or delete at an index is a different bill: every later reference moves one slot. Prepend is the worst case — index 0 — because the whole used range slides:
static void rushToFront(List<Order> open, Order rush) {
open.add(0, rush);
}
static Order takeOldest(List<Order> open) {
return open.remove(0);
}Both are honest List methods. Neither is cheap on ArrayList. A loop that prepends n rush orders is O(n²). The JVM will not save you; System.arraycopy is fast per element and still linear in size.
That is why a queue of picks is not an ArrayList. remove(0) in a loop is a rotating array queue — the Queue post names the contract; ArrayDeque is the delivery. LinkedList.addFirst is O(1) pointers and still the wrong default for a queue; the next post is that argument.
Mid-list add(i, e) is the same slide of the tail. People quote it as a reason to switch to LinkedList. The splice on a linked node is O(1) only if you already hold the node. Finding index i on a LinkedList is a walk. An ArrayList slide is a tight copy over contiguous memory and often wins at real sizes. Measure, or keep the ArrayList.
The iterator you already use
A for-each on an ArrayList is a fail-fast iterator. Structural add / remove on the list during that iteration throws ConcurrentModificationException, except Iterator.remove. The hub owns that contract; here is the checkout shape that hits it:
List<Order> open = new ArrayList<>(orders);
for (Order order : open) {
if (!order.active()) {
open.remove(order);
}
}That remove is a structural change. The enhanced-for iterator notices modCount moved and throws. The fix is not “catch CME.” It is removeIf, or Iterator.remove on an explicit iterator:
open.removeIf(order -> !order.active());var it = open.iterator();
while (it.hasNext()) {
if (!it.next().active()) {
it.remove();
}
}set(i, e) is not structural. Replacing the order at index 2 during iteration does not bump modCount. Adding a new order does.
ArrayList allows null. A fail-fast iterator will happily yield it. order.active() on that slot is your NPE, not the collection’s.
subList is a view
subList does not copy. It is a window on the same elementData. The List post owns the API; the hub owns views vs copies. The decision that changes here: clearing a sub-range writes through.
List<LineItem> items = new ArrayList<>();
items.add(new LineItem("SKU-1", 1, new BigDecimal("9.99")));
items.add(new LineItem("SKU-2", 2, new BigDecimal("4.50")));
items.add(new LineItem("SKU-3", 1, new BigDecimal("1.25")));
items.subList(1, 3).clear();items is now one element, SKU-1. A new ArrayList<>(items.subList(1, 3)) would have been a copy. Pick the one you meant. Structural changes through the view are also structural changes on the parent — a parent iterator in flight will fail-fast the same way.
List.copyOf(open) and new ArrayList<>(open) allocate. open.subList(0, 2) does not. Java 9 factories (List.of, List.copyOf) are unmodifiable copies; they are a different post.
When not ArrayList
Skip this class when the hot operation is not “index i or append.”
- The hot path is a queue or stack.
remove(0)/add(0)in a loop is the rotating-array tax. ArrayDeque is the default for ends. LinkedList isListplusDequeon nodes — rarely what you wanted. - You needed uniqueness.
open.contains(order)on thousands of orders is a scan. That is aHashSet(or aHashMapby id), not a bigger list. - A single append must be bounded. Amortized
O(1)is a statement about a sequence. Pre-size, or do not put an unsized grow on a latency-critical path whennis already huge. - You already know
nand never grow. AT[]has no leftover capacity and noListceremony. KeepArrayListwhen you still want theListAPI (get,subList, streams). Useint[]when the payload is primitives —ArrayList<Integer>boxes every slot. - Another thread mutates the same list.
ArrayListis not the answer. Copy-On-Write for snapshot readers; a concurrent type or confinement otherwise. Vector is a synchronizedArrayListfrom 1998. It is not the thread-safe list you want in 2026.
Versus a raw array: fixed length, optional primitives, no grow. Versus LinkedList: you keep O(1) get, contiguous scans, and amortized append; you give up O(1) splice-at-a-held-node. For almost every ordinary Java list, that trade is the right one.
Interview lens
Interviewers want the backing store, the grow, and why prepend is linear. They do not want you to recite AbstractList.
Complexity they expect without a table: get / set O(1), append amortized O(1), add(0) / remove(0) O(n), contains O(n). The grow itself is O(n) when it runs.
What to draw. An Object[] with size short of capacity. Three appends that fill the last slots. A new, longer array and a copy of the live range. Then a separate sketch of add(0): every used slot slides right. Label leftover capacity at the tail. Say “Java 8+ grows about 1.5×, default first allocation 10.”
Typical questions:
| Question | Honest answer |
|---|---|
What is the initial capacity of new ArrayList<>()? | The no-arg list starts with a shared empty array. The first add allocates 10. |
| What happens on resize? | Allocate a larger Object[] (~1.5× in Java 8+), Arrays.copyOf the live elements, drop the old array. That call is O(n). |
Why is add(0) O(n)? | Every later element must slide one index. System.arraycopy on the used range. |
| What does fail-fast mean here? | Structural change during iteration → ConcurrentModificationException, except Iterator.remove. It is not a memory barrier. Hub definition. |
Vector vs ArrayList? | Same layout idea; Vector synchronizes every method and grows by doubling (unless you set capacityIncrement). Not the thread-safe list you want. |
Why ensureCapacity before a known bulk add? | One grow (or the sized constructor) instead of a chain of 1.5× copies inside a loop of add. |
Does ArrayList allow null? | Yes. So does LinkedList. ArrayDeque does not. |
| How do you get capacity? | You don’t, from the public API. You set it with the constructor / ensureCapacity and drop leftover with trimToSize. |
Wrong answer: “ArrayList.add is always O(1).” Append is amortized O(1). The resize call copies the whole array. Quote the long run, or quote the next call — not both as the same fact.
Cheat sheet
Backing Object[] elementData + size capacity = array.length
Default new ArrayList<>() → empty; first add allocates 10
Grow Java 8+: old + (old >> 1) ≈ 1.5×; copies the live range
get / set O(1) RandomAccess
append amortized O(1) next add may still be O(n)
add(0)/remove(0) O(n) the used range slides
addAll one grow to size+n, then block copy
ensureCapacity size when you know n; sized constructor is clearer
trimToSize copy down to size; rare
nulls yes
threads no — CopyOnWriteArrayList or don't share
iterator fail-fast (hub); use removeIf / Iterator.remove
subList view (List post); clear writes through
vs array array is fixed; ArrayList grows; int[] if primitives
vs LinkedList keep ArrayList unless you already hold a node and spliceDo:
new ArrayList<>(n)orensureCapacity(n)when the feed already told youn.- Append and index. That is this class.
removeIfinstead of removing from the list inside a for-each.
Don’t:
- Quote
addasO(1)without amortized. add(0)/remove(0)in a loop and call it a queue.- Reach for
Vectorbecause it says synchronized. - Use
new ArrayList<>(0)as a clever empty — it grows from 1, not 10.
Wrap-up
ArrayList is an Object[] with a size, a 1.5× grow, and O(1) indexes. It is the default List because most code appends and then asks for get(i). Growth copies the whole live array; that is why you size the list when you know n, and why “append is O(1)” needs the word amortized. Prepend is a slide. Another thread is a different type.
When the hot path is a node you already hold, or both List and Deque on the same object, the next class is the one that usually loses — and occasionally wins.