P-4.1 Arrays and Dynamic Arrays

What this is and why it exists

The array is the structure everything else gets measured against. The growable array built on top of it is the default container in nearly every modern language, which means you are already using one.

There is one idea here worth genuinely understanding rather than memorising: the doubling argument. An append is occasionally very expensive, and cheap on average.

That sentence hides a different *kind* of reasoning. Averaging over a sequence of operations is not the same as talking about a typical input, and confusing the two is common.

The vocabulary

• Index — a position, used as arithmetic rather than as a search.
• Contiguous — elements stored one after another with no gaps.
• Capacity — how much storage the array currently has.
• Size — how much of that storage is in use.
• Reallocation — getting a larger block and copying everything into it.
• Amortised cost — the cost of an operation averaged across a sequence.

The mental model

Reading by index costs the same whatever the index is. The address is the start plus the index times the element size. That is arithmetic, not searching, and every attractive property of arrays follows from it.

The same contiguity that makes reading cheap makes middle insertion expensive. Everything after the change has to move. For a large collection with frequent insertions in the middle, this is the wrong structure, and no amount of tuning fixes it.

Growing is where it gets interesting. When storage runs out, a new larger block is allocated and everything is copied. If you grew by one element each time, every append would copy everything, and appending a thousand items would cost about half a million copies. Instead, implementations double. Now the copies are rare, and they get rarer as the array grows.

Work out what that costs across a sequence and you find something pleasing. Each element is copied a small number of times on average, no matter how many appends you do. The average cost per append stays constant.

That is amortised cost, and here is the distinction that matters. Amortised analysis spreads the cost of an occasional expensive operation across the cheap ones that made it necessary. It is a worst-case statement about a sequence, not a statement about typical inputs. Nobody is assuming your data is average. The guarantee holds for any sequence of appends at all.

Write one yourself, including the reallocation and the copy. It makes the cost model concrete. It also explains something you have seen without asking about: why the standard library keeps capacity and size apart.

What you should now be able to explain or do

State the cost of reading, inserting and deleting in an array, and say why reading is constant. Explain why middle insertion costs a shift and when that rules the structure out. Explain the doubling strategy and why it makes appends cheap on average. State the difference between amortised cost and average case. Implement a growable array with its reallocation, and say why capacity and size are separate.

Check yourself