ArrayList

the picture

you know how everyone says "arrays have a fixed size" and then uses ArrayList which... doesn't? it's the same array. it just moves house when it runs out of room.

think of a bookshelf with numbered slots. adding a book at the end is easy. when the shelf is full, you buy a shelf 1.5x longer, move every book across one by one, and throw the old shelf out. annoying, but you don't do it often. squeezing a book in at slot 0 though? every other book scoots one slot right. that's annoying every single time.

three things to notice in there:

1. new ArrayList<>() doesn't allocate anything. it points at one shared empty array, and the real 10-slot array shows up on the first add. lots of lists are created and never filled, so this saves real memory.
2. the growth is old + (old >> 1): half again. so 10 → 15 → 22 → 33 → 49.
3. capacity only goes up. remove everything and you still hold the big array (call trimToSize() if you care).

the growth, exactly

this is the actual line in jdk 25's ArrayList.grow (via ArraysSupport.newLength): the preferred growth is oldCapacity >> 1, and the new array is Arrays.copyOf(elementData, newCapacity). here's the sequence it produces:

void main() {
    int cap = 10;
    var seen = new StringBuilder("10");
    while (cap < 200) {
        cap = cap + (cap >> 1);
        seen.append(" → ").append(cap);
    }
    IO.println(seen);
}

10 → 15 → 22 → 33 → 49 → 73 → 109 → 163 → 244

(i also checked the real capacity with reflection on jdk 25 while adding 200 elements: same numbers, growing on the 11th, 16th, 23rd, 34th... add.)

why "amortized O(1)" isn't a lie

a single add that triggers a grow costs O(n): it copies every element. but after copying n elements, you get about n/2 cheap adds before the next copy. spread the copy over those adds and each one pays a constant. add up all the writes and copies over a long run and it settles at about 4 per element, however big the list gets. that's what "amortized" means: the average over a sequence, not the worst single call.

the price is the occasional slow add (a latency spike while a million references get copied) and up to a third of the array sitting empty right after a grow.

what it actually holds

an ArrayList<Integer> doesn't hold ints. generics only work with objects, so every element is a reference to an Integer on the heap. the list's array is an array of arrows.

so a million ints in an ArrayList<Integer> is about 20 MB (4 bytes per slot + 16 per Integer), while an int[] is 4 MB. if you have a lot of primitives and performance matters, use a primitive array (or a primitive collection library). more on boxing in wrappers and boxing.

the upside of the flat array: get(i) is one bounds check and one array read. elements sit next to each other in memory, so iterating is about as cache-friendly as java gets (well, the references are; the Integers they point at can be anywhere).

the cost of every operation

System.arraycopy is a fast native copy, so shifting a few thousand references is quick in absolute terms. it's still linear, and doing it in a loop (remove(0) until empty) is quadratic. if you keep taking from the front, you wanted a deque.

List<Integer> list = new ArrayList<>(List.of(10, 20, 30));
list.remove(1);
list.remove(Integer.valueOf(10));
IO.println(list);

why not just use an array?

you should, when the size is fixed and known (or you're storing primitives). ArrayList buys you growth, a List interface everything accepts, and helpers like sort, removeIf and subList. it costs one extra object and an extra hop. for most code that's free.