Arrays: access versus insertion
An array gives direct indexed access, but making room in its middle usually means shifting later elements.
Learning objectives
- Relate contiguous order to O(1) indexed access.
- Explain why insertion in the middle is commonly O(n).
Trade-off
Given an index, array-style storage can calculate where the corresponding element lies, so access is O(1). To insert at index 1 in [10, 20, 30], the later elements must move right: [10, _, 20, 30], then the new value fills the gap. The number of moved elements grows with the array length.
Use it well
Arrays fit tables, indexed records, and data that is read frequently by position. Dynamic-array append is often amortized O(1), but a resize can occasionally copy elements.