Resizable arrays: account for growth and shifting

Last updated: 5 Oct 20269 min read

tutorial

A resizable array keeps elements in indexed order and reserves capacity beyond its current length. Reading an existing index costs O(1). Appending is O(1) amortized when capacity grows geometrically, although an individual growth operation copies O(n) references. Inserting at index zero or in the middle shifts a suffix and costs O(n). The interface promises a sequence, not a stable pointer to every element after mutation. Python lists implement this family of behavior; their exact allocation policy is an implementation detail, so do not base an API contract on a particular spare-capacity count.

Operational case

A dispatch board records shipment IDs in arrival order. The operator appends S-47, S-52, and S-61, then inserts an urgent S-58 at position one. The urgent item is visible immediately, but the two later IDs must move. A separate index keyed by shipment ID would help repeated lookup; it would not remove the shifting cost when display order changes. If the board needs constant-time inserts at arbitrary positions, first ask whether those positions are already known as node references and whether indexed reads can be surrendered.

Working Python program

shipment_order = ["S-47", "S-52", "S-61"]
shipment_order.insert(1, "S-58")
print(shipment_order[2])
print(shipment_order)

Output

S-52
['S-47', 'S-58', 'S-52', 'S-61']

Time, space, and tradeoff

The shown insertion shifts two entries, but its asymptotic worst case is O(n) time and O(1) additional application space. The backing list may already have spare capacity or may allocate a larger block. Repeated insertion at the front of a growing list costs O(n²) total movement; append then sort or use a different representation when the workload permits. A short list often still wins through locality and low pointer overhead, so measure realistic sizes before replacing it.

Common Mistakes

Do not call every append worst-case O(1).
Do not assume inserting at the front avoids moving existing entries.
Do not confuse list capacity with its visible length.

Connected lessons

Piece tables: edit text through source spans adds a related operation contract.

Generational slots: reject stale handles after reuse adds a related lifecycle choice.

Reservoir sampling: keep a uniform fixed-size sample adds a bounded stream contract.

Gap buffers: pay when the edit cursor crosses text adds a related sequence operation contract.

Segmented arrays: locate blocks through cumulative lengths adds a related sequence operation contract.

Checkpoint arenas: reclaim a region by lifetime extends the storage ownership comparison.

Eytzinger arrays: store a search tree in breadth-first order adds a distinct structure contract to compare.

Persistent radix vectors: copy one indexed path per revision adds a related structure with a different operation boundary.

data structures

array-data-structure-guide