Numbered slots in a row
Arrays as Bookshelves
The analogy
An array is a bookshelf with numbered slots. Because every slot is the same width and they sit in a row, you can jump straight to slot 7 without touching slots 0 to 6 — you just walk to it. But squeezing a book into the middle means shoving everything to the right.
Visualizer
Jumping straight to a slot
step 1 / 65
03
18
21
39
42
57
64
7A shelf of numbered slots, every slot exactly the same width. That uniformity is the whole trick.8 slots
📖 In depth — the full reference
Array operations and what they cost
| operation | cost | why |
|---|---|---|
| read arr[i] | O(1) | address = start + i × slot size — one multiplication, one jump |
| write arr[i] = x | O(1) | same arithmetic, then one store |
| search (unsorted) | O(n) | no shortcut — every slot may hide the value |
| insert at the END | O(1) amortized | drop into the next free slot (details next lesson) |
| insert at index i | O(n) | every element from i onward must shift right one slot |
| delete at index i | O(n) | every element after i shifts left to close the gap |
| length | O(1) | stored in the header — never counted |
Python lists — the full indexing toolkit
- Negative indexes count from the end: arr[-1] is the last element, arr[-2] second-to-last. arr[len(arr)] raises IndexError — Python never reads past the shelf.
- Slicing copies: arr[2:5] is a NEW list of slots 2,3,4 (half-open — the stop index is excluded). arr[:] is a full shallow copy; arr[::-1] a reversed copy.
- A Python list stores POINTERS to objects, not the objects themselves — so one list can mix types, and each slot costs 8 bytes regardless of what it points to.
- For a million plain numbers, array("d", ...) from the array module or a NumPy array stores raw values instead of pointers — ~8 bytes each with no per-object overhead.
See it yourself
arr = [12, 30, 21, 45, 9] print(arr[2], arr[-1]) # 21 9 — both O(1) print(arr[1:3]) # [30, 21] (a copy) arr[2] = 99 # O(1) write arr.insert(0, 7) # O(n) — everything shifts right del arr[0] # O(n) — everything shifts left
a = [12, 30, 21, 45, 9, 38, 27] a[6] # one multiply, one add, one read # address = base + 6 * itemsize # slots 0..5 are never touched — O(1) len(a) # also O(1), it is stored
Check yourself
Reading arr[500] on a 1000-element array costs…
Practice — write it yourself
grab_slots(arr, i) returns [arr[i], last element] — two O(1) jumps, zero walking. (Remember negative indexes.)
Python 3 · runs in your browser · your draft is saved locally
📝 My notessaved in this browser