What is an array-list, and why is add usually $O(1)$ but occasionally $O(n)$?

An array-list wraps a plain array and resizes it automatically; an add into a free slot is $O(1)$, but an add into a full array first copies every element into a bigger one, which is $O(n)$.

* The fourth add fits; the fifth finds the array full and pays for copying all four first. *

A plain array has a fixed length that is decided when it is created. An array-list hides that limitation: it keeps an internal array that is usually a bit larger than needed, plus a counter of how many slots are actually used.

• Room left: add writes the element into the next free slot and bumps the counter. One write, independent of $n$ — $O(1)$.
• Array full: there is nowhere to write. The list allocates a new, larger array (typically double the size), copies all $n$ existing elements across, and only then writes the new one. The copy touches every element — $O(n)$.
• Shrinking: when many elements are removed, the array-list can also shrink its internal array again, so a list that was once huge does not hold on to the memory forever.

So the cost of a single add depends on when you call it, which is why the worst case of one operation and the typical cost differ so sharply.

Go deeper:

• Dynamic array — capacity vs. size, the growth factor, and the performance table against linked lists.
• java.util.ArrayList — the Java implementation; its class comment states the amortised constant-time add.