---
title: "Arrays & Indexing"
description: "Contiguous storage, indices, traversal, and what going out of bounds really means."
source: https://vizlearn.app/foundations/execution-model/arrays-indexing
---

# Arrays & Indexing

Arrays and indexing store an ordered sequence in numbered slots and retrieve a slot from its zero-based coordinate. An array of length `n` has exactly the non-negative indices `0` through `n - 1`. `range(len(values))` visits those slots; index `n` is the first coordinate with no slot.

Treat an index like a coordinate on a ruler. Slot 0 sits at displacement 0, slot 1 at displacement 1, and so on. That describes where the slot is, not how the computer travels there. An array computes the slot location directly; it does not begin at slot 0 and walk right.

## How arrays and indexing work

An array gives each element a position and a value. In `values = [12, 7, 25]`, 12 occupies index 0, 7 occupies index 1, and 25 occupies index 2. The values happen to be numbers, but indexing cares about position, not magnitude.

For a non-negative index `i`, the legal-bound test is `0 <= i < len(values)`. The strict upper bound does the important work. A length of 3 means that three slots exist, with indices 0, 1, and 2. Length counts slots; it is not the final index.

That is why `range(len(values))` is the standard traversal shape. `range(3)` produces 0, 1, and 2, then stops. It never assigns `i = 3`, so the loop body never tries `values[3]`.

One indexed read takes O(1) time in an array-like representation. The runtime combines the starting location with the index and the size of one reference slot to compute one target location. A full traversal still takes O(n): it performs n separate constant-time reads.

Python is blunt about a missing slot. Evaluating `values[3]` raises `IndexError`. It does not return `None` or invent an empty cell. If the expression is an argument to `print`, the exception occurs before `print` is called.

## Arrays and indexing step by step

The default run uses `values = [12, 7, 25]` and `probe = 3`.

1. Line 1 prepares `range(len(values))`. The length is 3, so the candidate indices are 0, 1, and 2.
2. The loop produces `i = 0`. Line 2 reads `values[0]`, gets 12, and prints `0 12`.
3. The loop produces `i = 1`. Line 2 reads `values[1]`, gets 7, and prints `1 7`.
4. The loop produces `i = 2`. Line 2 reads `values[2]`, gets 25, and prints `2 25`.
5. The iterator is exhausted. `i` remains 2; Python does not assign 3. Execution leaves the loop without a fourth read.
6. Line 3 evaluates the bound `0 <= 3 < 3`, which is false.
7. Evaluating `values[3]` raises `IndexError`. Argument evaluation stops, so `print("probe", ...)` never runs.

The animation keeps two adjacent events separate. First, a neutral boundary shows `range(3)` stopping safely before 3. Then the probe snaps to that same no-slot boundary and the real access turns red. The address cue says `base + 3 × one slot`: one direct calculation reaches the boundary, with no scan through slots 0, 1, and 2.

## Why array indexing is O(1)

Array indexing and array traversal have different costs because they perform different amounts of work.

| Operation              | Time | Extra space | Reason                                   |
| ---------------------- | ---: | ----------: | ---------------------------------------- |
| Read `values[i]`       | O(1) |        O(1) | Compute one slot location from the index |
| Traverse all `n` slots | O(n) |        O(1) | Perform one indexed read per slot        |
| Check `0 <= i < n`     | O(1) |        O(1) | Compare one index with two bounds        |

The O(1) claim assumes an array-like representation with fixed-width reference slots. A linked list cannot use the same trick: it must follow links from the head to position `i`, which costs O(i). Same bracket-shaped wish, very different bill.

## Edge cases

- **Empty array:** `len(values)` is 0, so `range(0)` produces no indices. Every non-negative probe is out of range.
- **First slot:** index 0 is legal whenever the array is non-empty. Its displacement from the start is zero.
- **Last slot:** for length `n > 0`, the last non-negative index is `n - 1`.
- **Past the end:** index `n` is the first illegal non-negative index. Python raises `IndexError`.
- **Negative Python indices:** Python accepts `-1` for the last element down through `-n` for the first. This lesson keeps the main diagram non-negative because most languages do not share that rule.

## Common mistakes

- Using `i <= len(values)` in a traversal condition. Equality admits index `n`, which is already past the final slot.
- Treating length as the last index. Subtract one to get the last non-negative index of a non-empty array.
- Assuming an out-of-range read returns `None`. Python raises before the surrounding call can run.
- Imagining that O(1) indexing walks from slot 0. The index is a coordinate; the runtime computes the target slot directly.
- Drawing an empty box at index `n`. That picture claims a slot exists. A boundary with no cell is the honest diagram.

## A note on simplification

The cells are logical Python-list slots, not a heap dump. A Python list keeps a contiguous array of references to objects; the integer objects themselves need not sit beside one another. The lesson omits byte addresses, spare capacity, resizing, object headers, and interpreter machinery. It also scopes the main diagram to non-negative indices while naming Python's separate negative-index rule. Other languages may trap, throw a different exception, or permit unsafe memory access, so `IndexError` is specifically Python behavior.