P-4.1 Arrays and Dynamic Arrays

Work through these

• Reading by index is constant time because it is arithmetic

  The address of an element is the start plus the index times the element size, so reaching any element costs the same. Everything attractive about arrays follows from this one property.

• Inserting or deleting in the middle costs a shift

  Keeping elements contiguous means everything after the change has to move. For a large collection with frequent middle insertions this is the wrong structure entirely.

• Growing by doubling, and why appends are cheap on average

  When storage runs out, a new larger block is allocated and everything is copied over. Doubling the size makes those copies rare enough that the average cost per append stays constant.

  Algorithms, 4th Edition — companion site · Reference

• Amortised cost, and how it differs from average case

  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.

• Implement a growable array yourself, with the doubling

  Writing one, including the reallocation and the copy, makes the cost model concrete. It also explains why the standard library version keeps capacity and size as two separate numbers.