Arrays — Direct Access by Position

What is it? #

An array stores items one after another in a single block of memory. Because the items are the same size and laid out in order, the computer can calculate exactly where item 500 sits and jump straight to it.

That is the defining property: if you know the position, you reach the item in one step. No searching involved.

The cost is at the edges. Inserting or removing at the front means shifting every item along to make room or close the gap. Adding at the end is cheap, as long as there is spare space.

In Python, a list is a dynamic array. It grows automatically, which hides the resizing work but not the shifting cost.

Think of it like this #

Think of a row of numbered seats in a cinema. Finding seat 23 takes no searching — you walk straight to it.

But if someone must be seated at position 1 and the row is full, everyone shuffles one seat along. Adding at the end is trivial; inserting at the front moves the whole row.

Simple example #

You keep a list of the last 1,000 temperature readings. Reading the most recent one, or the one from an hour ago, is instant. Dropping the oldest reading off the front, however, moves all 999 others.

Code #

readings = [31.2, 30.8, 32.4, 33.1, 29.9]

# O(1) — direct access by position
print(readings[0])        # 31.2
print(readings[-1])       # 29.9
readings[2] = 32.9        # also O(1)

# O(1) amortised — append at the end
readings.append(30.1)

# O(n) — everything after the insertion point shifts
readings.insert(0, 34.0)

# O(n) — the gap has to close
readings.pop(0)

# O(n) — finding a value means checking each item
print(32.9 in readings)

# O(n) — slicing copies the selected items
recent = readings[-3:]

# Two-dimensional arrays: a list of lists
grid = [[0] * 3 for _ in range(3)]
grid[1][2] = 7
print(grid)               # [[0, 0, 0], [0, 0, 7], [0, 0, 0]]

# The classic bug: this shares ONE inner list three times
broken = [[0] * 3] * 3
broken[0][0] = 9
print(broken)             # [[9, 0, 0], [9, 0, 0], [9, 0, 0]]

Array operation costs

read by index        O(1)
update by index      O(1)
append at end        O(1) amortised
insert at front      O(n)
delete from front    O(n)
search by value      O(n)

How it works #

readings[2] is computed, not searched. The runtime knows where the block starts and how big each slot is, so position 2 is a single calculation away. This is why index access does not get slower as the list grows.

append is "amortised O(1)". Usually there is spare capacity so it is instant. Occasionally the array is full and a bigger block is allocated and everything copied — an O(n) operation. Because that doubling happens rarely, the average cost per append stays constant.

insert(0, x) and pop(0) both touch every remaining item. Removing the first of a million readings moves 999,999 of them. If you need that pattern often, collections.deque does it in constant time at both ends.

32.9 in readings compares item by item, so it is O(n). This is the operation people underestimate most often.

Slicing copies. readings[-3:] builds a new list of three items — cheap here, expensive when you slice most of a large list inside a loop.

The 2D section shows a real trap. [[0] * 3] * 3 repeats a reference to the same inner list three times, so writing to one row writes to all three. The comprehension version creates three separate lists.

Real-world use #

Arrays underpin almost everything: rows returned from a database, pixels in an image, samples in audio, matrices in machine learning. When order and positional access matter, an array is the default.

The performance lesson shows up in queue-like code. Using a list and pop(0) to process a work queue is fine at ten items and terrible at a hundred thousand; deque.popleft() is the fix.

Contiguous memory has a second, less obvious benefit: CPU caches load nearby memory together, so walking an array in order is much faster than jumping around. This is why libraries like NumPy store data in compact arrays rather than Python lists — the layout itself makes the maths fast.

When you need constant-time lookup by something other than position, that is a hash table, which is the next structure worth knowing.

Common mistakes #

• Using pop(0) in a loop to drain a list. Use collections.deque instead.
• Searching with in inside a loop, turning an O(n) job into O(n²).
• Creating 2D grids with [[0] * n] * m, which shares one inner list.
• Slicing large lists repeatedly and forgetting that each slice copies.
• Assuming an index always exists. Check the length or handle IndexError.

Practice #

Build a list of 100,000 numbers. Time how long it takes to (a) read the middle element 10,000 times, (b) call pop(0) 10,000 times, and (c) call append 10,000 times. Then repeat (b) with collections.deque and compare.