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.

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.