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:
addwrites 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: some implementations also shrink the internal array when many elements are removed, so a list that was once huge does not hold on to the memory forever. Others never shrink on their own and leave that to an explicit call.
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.
Is this true in every language? The principle is, the numbers are not. Every mainstream growable array works this way: Java ArrayList, C# List<T>, C++ std::vector, Python list, Rust Vec, Go slices with append. What differs is the growth factor and the shrinking policy:
| Implementation | Grows by | Shrinks on its own? |
|---|---|---|
Java ArrayList |
×1.5 | no (trimToSize() by hand) |
C# List<T> |
×2 | no (TrimExcess() by hand) |
C++ std::vector |
×2 (GCC), ×1.5 (MSVC) | no (shrink_to_fit() is only a request) |
Python list |
about ×1.125 plus a constant | yes, when less than half full |
Any constant factor above 1 keeps add amortised $O(1)$; a smaller factor wastes less memory but copies more often. Plain fixed arrays (int[] in Java, C arrays) do not grow at all, and a linked list never copies but pays for it elsewhere.
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.