Arrays and positional operations

After this page, you should be able to:

• Trace indexed access, replacement, insertion and removal in an array.

• Separate shifting cost from resizing, locality and value lookup.

Builds on: Sequence contracts define positional operations; this page explains their storage movements.

Code languages: Python defines the explanations, figures and self-checks. Use the language guide for native conventions and dependencies. Complete runnable topic examples: Python · JavaScript · Julia.

Julia uses one-based positions and named functions such as enqueue! rather than Python-style instance methods. Endpoint adapters use the supplied linked DequeBuffer, so they do not hide linear array-front shifts. Empty operations reject the request; null/nothing remain valid payloads.

Operation mapping¶

The sequence interface calls indexed observation get, replacement set, insertion insert, and removal-and-return remove_at. The wrapper maps them to a[i], indexed assignment, list.insert and list.pop(i) after checking its stricter index policy. This page explains the movements behind that code; a raw array alone does not automatically grow.

Equal-sized slots give direct access¶

An array stores equal-sized slots consecutively. If the base address is $b$ and each slot occupies $w$ bytes, slot $i$ begins at

Computing this address does not require visiting slots 0 through $i-1$. In the usual constant-time machine-word model, accessing or replacing a valid indexed slot is $O(1)$.

An array of references is different from an array of numeric values. In CPython, a list uses an array of object references. Those slots are contiguous, but the referenced objects can live elsewhere and have different types and sizes. This connects to Topic 1’s object model.

The illustrated addresses and slot width are hypothetical. What matters is the fixed distance between slots. The object is reached through its reference; its complete contents are not necessarily stored inside the slot.

Insertion must preserve the later items¶

To insert X at position 1 in [A, B, C, D], with one spare slot available, move D right, then C, then B, and fill the gap with X. The order of shifting matters: moving B first would overwrite C before preserving it.

For a sequence of length $n$, insertion at position $i$ shifts $n-i$ references. Insertion near the front therefore takes $\Theta(n)$ work even if there is spare capacity. Insertion at the back shifts none, though it may require resizing.

Removal closes a gap¶

Removing position $i$ shifts the later $n-i-1$ references left. A simple fixed-buffer implementation clears the unused last slot so it no longer retains an unwanted reference. Removing the front is linear; removing the last occupied slot requires no shifting.

Replacing a value is different from inserting one. a[i] = x retains the same length and other positions. a.insert(i, x) increases the length and changes the positions of later items.

route = ["A", "B", "C", "D"]
route.insert(1, "X")
assert route == ["A", "X", "B", "C", "D"]
assert route.pop(1) == "X"
route[1] = "Y"
assert route == ["A", "Y", "C", "D"]

var route = ["A", "B", "C", "D"];
route.splice(1, 0, "X");
console.assert(JSON.stringify(route) === '["A","X","B","C","D"]');
console.assert(route.splice(1, 1)[0] === "X");
route[1] = "Y";
console.assert(JSON.stringify(route) === '["A","Y","C","D"]');

route = ["A", "B", "C", "D"]
insert!(route, 2, "X")
@assert route == ["A", "X", "B", "C", "D"]
removed = route[2]; deleteat!(route, 2)
@assert removed == "X"
route[2] = "Y"
@assert route == ["A", "Y", "C", "D"]

Locality and limitations¶

Sequential array slots favour memory locality: nearby references can be fetched together in cache. This can improve practical speed beyond what Big-O describes. An array of references does not, however, guarantee locality of all the referenced objects.

Direct indexing also does not mean a value can be found instantly. If only a value is given and its position is unknown, searching an unsorted array may still require a linear scan. The operation and information available determine the cost.

Representation reference: How lists are implemented in CPython. Next: Dynamic arrays.

Check your understanding¶

Predict the operation result and the resulting state before opening the explanation.

1. Insert X at position 1 in A,B,C,D with spare capacity. Which direction must shifts proceed?

2. Does set(1,X) increase length?

Next: Dynamic arrays.