Dynamic arrays
Appending is cheap on average because the expensive step gets rarer at exactly the rate it gets dearer. Growth multiplies the capacity instead of adding to it, which spreads one copy of everything across all the appends that follow.
Every time you run out of room you move to a bigger flat, much as a growing array does. Moving is a whole day's work, but each new place is twice the size, so you do it half as often as last time. Any single move is just as tiring; spread across everything you own, the cost keeps shrinking.
A dynamic array has to solve a problem that sounds unsolvable: give the caller a block of memory whose size was fixed when it was allocated, and let them keep adding to it anyway. The way out is to lie convincingly — allocate more room than the caller asked for, and when that runs out, allocate a bigger block and copy everything across. What makes this a good idea rather than an obvious waste is how much bigger the next block is.
Why doubling and not adding#
Suppose growth added a fixed amount — room for ten more elements each time the array filled. Appending a million elements then means a hundred thousand reallocations, and each one copies everything that came before it. The copies get steadily more expensive while staying just as frequent, and the total work lands proportional to n squared. That is the version people picture when they hear that a growable array copies on resize, and it is why the operation sounds worse than it is.
Now suppose growth multiplies instead — the new block is some fixed factor larger than the old one. Appending a million elements takes about twenty reallocations rather than a hundred thousand, because each one buys twice the headroom the last one did. The copies still get more expensive every time. They also get rarer at exactly the same rate, and those two effects cancel: the total copying across n appends comes out proportional to n, not to n squared.
That cancellation is the whole trick, and it is why the cost is quoted as an average over a run of operations rather than a promise about any one of them. Java’s ArrayList documentation states it in the form that keeps the distinction visible — the add operation runs in amortized constant time, that is, adding n elements requires O(n) time. It is a claim about n appends together. Any individual append may still be the one that copies a million elements, which matters if you care about the slowest response rather than the average one.
What the library refuses to promise#
The obvious follow-up question is what the factor actually is, and the answer from the documentation is a deliberate refusal. Java’s ArrayList says the details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost. It commits to the property and withholds the mechanism.
That is not evasiveness, it is the interface being drawn in the right place. The factor is a trade between wasted memory and copy frequency, it interacts with how the underlying allocator reuses freed blocks, and implementations tune it. Naming a number in the specification would freeze a tuning decision into the contract, and every caller who measured capacity after a known number of appends would become a reason not to change it.
What the documentation does hand you is a lever, and it is honest about what the lever does. ensureCapacity exists to raise the capacity before a bulk insert, described as a way to reduce the amount of incremental reallocation. Note what that fixes and what it does not: it removes repeated copying, not the per-append bookkeeping, so it is worth reaching for when the count is large and known and worth ignoring otherwise.
Where it goes wrong#
The first trap is treating an average as a guarantee where the worst case is what is being measured. A request that happens to trigger the reallocation of a large array wears the cost of copying every element in it, and no amount of averaging helps the one caller waiting on that. On a service reporting its slowest percentiles, growth shows up as occasional spikes with no corresponding change in input — the same reading that separates a latency number from a throughput number, arriving from a structure nobody thought of as a source of variance.
The second is expecting the memory back. Growth is automatic and shrinking generally is not: remove most of the elements and the capacity usually stays where it was, because releasing it would mean another copy and the structure has no way to know whether the space is about to be needed again. This is the trade a linked list opts out of entirely, by never holding a block bigger than one element. A collection that briefly held a peak load can keep holding that peak’s worth of memory for the life of the process, which reads exactly like a leak to whoever is looking at the graph — and is not one, because it is bounded by the peak rather than by uptime.
The third is capacity arithmetic in application code. Because the growth policy is unspecified, any code that computes how much room exists after a known number of appends is depending on something the library reserved the right to change, and it will keep working until a runtime upgrade quietly retunes the factor. Ask for the size, ask for capacity if the API offers it, and let the structure decide the rest.
IF YOU REMEMBER ONE THING
Multiplying the capacity rather than adding to it is what turns an occasional full copy into a cost you can ignore per append — and the reason the guarantee is stated across n operations instead of one.
Questions people also ask
5 QUESTIONSWhy is appending called constant time if it sometimes copies everything?
Because the copies get rarer at the same rate they get more expensive, so the total work across n appends stays proportional to n. Java's ArrayList documentation states it as a total rather than a per-call claim: the add operation runs in amortized constant time, that is, adding n elements requires O(n) time. Any one append can still be the unlucky one that copies the whole array.
What growth factor do real implementations use?
They mostly decline to say, which is the interesting part. Java's ArrayList documentation states outright that the details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost. That leaves implementations free to tune it — and it tells you not to write code that depends on a particular capacity after a particular number of appends.
Does growth ever shrink the array again?
Usually not automatically. Removing elements normally leaves the capacity where it was, so a list that briefly held a million items can keep holding a million items' worth of memory afterwards. Where that matters, the fix is an explicit call — trimming to size, or building a fresh collection from the survivors — rather than an expectation that the structure will notice.
Should I pre-size an array if I know how many elements are coming?
It is worth it when the count is large and known, and not worth thinking about otherwise. Java exposes ensureCapacity for exactly this and describes it as a way to reduce the amount of incremental reallocation. What it saves is the repeated copying, not the per-append bookkeeping, so the win grows with the size of the array rather than with the number of calls.
Why not use a linked list if resizing is the problem?
Because the resize is rare and the linked list's costs are constant. A dynamic array copies everything occasionally and reads sequentially the rest of the time; a linked list never copies and pays a pointer hop on every single element. In practice the second bill is the larger one, which is why the growable array is the default sequence type in almost every standard library.