Why Does an Array Middle Edit Shift Elements?
A contiguous array keeps indexes adjacent, so insertion or deletion in the middle must copy the tail while direct indexed access remains constant-time.
An array stores values in index order with no gaps. Reading values[index] is O(1), but changing the middle while preserving that order moves every later value. A non-mutating implementation makes those writes visible.
Implementation and index convention
Press Run to execute this example. Use console.log to print a value.
Before source index s, result contains the new value if its insertion boundary has been reached, plus every original value before s in order. The loop preserves that invariant and the final branch handles the half-open boundary at values.length.
For insertAt([1, 2, 4], 2, 3), copy 1 and 2, write 3 when the source reaches 2, then copy 4. A negative index is clamped to 0; an index past the end is clamped to length.
Complexity and edge cases
Insertion and deletion each copy O(n) values into O(n) result space. A middle mutation with splice also shifts O(n) values even though it is one method call.
- Empty insertion produces a one-value array.
- Removing an out-of-range index should return a copy when that is the contract.
- Decide whether negative indexes are rejected, clamped, or interpreted from the end.
- Preserve the input when the signature accepts a
readonlyarray. - Do not confuse the O(1) index calculation with the O(n) data movement.
Optional enrichment
Implement removal into a preallocated array of length n - 1. Explain why preallocation changes constants but not the O(n) bound.