Arrays and Dynamic Arrays

1What an array actually is

Strip away the language's convenience and an array is startlingly simple: one block of memory and one multiplication.

An array is a contiguous block of memory divided into equal-sized slots. Two properties do all the work:

• Contiguous — the slots are next to each other, no gaps.
• Uniform — every slot is the same size in bytes.

Given those, the address of element i is pure arithmetic:

address(i) = base_address + i * element_size

# An array of 8-byte integers starting at address 4000:
#   element 0  → 4000
#   element 1  → 4008
#   element 2  → 4016
#   element 500 → 4000 + 500 * 8 = 8000

# One multiply, one add, one memory fetch. Element 500 costs
# exactly what element 1 costs. That is O(1).

2What contiguity costs you

Contiguity is a promise, and promises constrain. Every awkward array operation traces back to keeping that promise.

If element i must sit at base + i×size, then inserting a new element at position 2 of a ten-element array means elements 2 through 9 must physically move one slot right. Eight memory writes to insert one value.

Watch it happen. This animation reverses an array in place, which is nothing but a sequence of element moves — the counter shows the real cost:

* amortised — see section 4.

Look at that table as a shape rather than a list of facts. Arrays are brilliant at positional work and bad at structural work. Anything that changes where things live costs a linear pass; anything that just reads or writes a known position is free.

xs = [10, 20, 30, 40, 50]

xs[2]                # O(1)  — computed address
xs[2] = 99           # O(1)  — computed address
xs.append(60)        # O(1)* — write into a free slot at the end
xs.pop()             # O(1)  — just decrement the length

xs.insert(0, 5)      # O(n)  — every element shifts right
xs.pop(0)            # O(n)  — every element shifts left
xs.remove(30)        # O(n)  — search for it, THEN shift
30 in xs             # O(n)  — no shortcut without sorting

3Static arrays and the growth problem

A true array has a fixed size, decided when it is created. Python hides this from you, and the hiding is where the interesting engineering lives.

In C, an array's size is baked in at creation:

int scores[100];    // exactly 100 ints, forever. No append().

Why not just allocate it bigger? Because the memory has to be contiguous, and the block immediately after your array is very likely already occupied by something else. You cannot extend in place; you can only find a bigger free space elsewhere and move.

So the naive fix — grow by one slot each time — would be catastrophic:

# The naive A strategy, in pseudocode:
def append_naive(arr, x):
    bigger = allocate(len(arr) + 1)   # find a new block
    for i in range(len(arr)):         # ← copy EVERYTHING
        bigger[i] = arr[i]
    bigger[len(arr)] = x
    free(arr)
    return bigger

# Appending n items copies 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 elements.
# That is O(n²) to build a list. Building a million-item list would
# perform about 500,000,000,000 copies.

4The doubling trick

Grow by a constant amount and you get O(n²). Grow by a constant factor and you get amortised O(1). The difference is one word.

The fix: when the array fills up, do not allocate one more slot. Allocate twice as many. You waste some space, and in exchange the expensive copies become exponentially rarer.

Step through it. Watch the capacity meter, and notice how far apart the resizes get:

Count what just happened. Resizes occurred at sizes 1, 2, 4, 8, 16 — five of them for seventeen appends. The copying work across all of them was 1 + 2 + 4 + 8 + 16 = 31, which is less than 2 × 17.

That is not a coincidence. Doubling from 1 to n costs 1 + 2 + 4 + … + n/2 + n copies, and that geometric series sums to less than 2n, for any n. Every geometric series with ratio 2 is dominated by its last term.

The average stays under 2, forever. That constant — a bounded average, no matter how large n gets — is precisely what amortised O(1) means.

import sys

xs = []
last = -1
for i in range(70):
    xs.append(i)
    size = sys.getsizeof(xs)
    if size != last:
        print(f"length {len(xs):3}  →  {size} bytes  ← reallocated here")
        last = size

# Run this in the playground below. The jumps are the resizes,
# and they get further apart exactly as the argument predicts.

5Python's list, and its cousins

Python gives you three array-ish things. They are not interchangeable, and the differences are the trade-offs of this chapter made concrete.

A CPython list is not an array of values. It is a dynamic array of pointers to objects living elsewhere in memory. That is why a list can hold mixed types — every slot is the same size because every slot is an address.

xs = [1, "hello", 3.14, [1, 2]]     # perfectly legal
# Each slot holds an 8-byte pointer. The objects themselves are scattered.
#
# Cost: an extra indirection per access, and the values are NOT
# contiguous in memory — which is why NumPy exists.

The reason a tuple can be a dictionary key and a list cannot comes straight from this chapter's theme: hashing requires the value never to change, and a list's whole purpose is changing.

6When an array is the wrong answer

Arrays are the default for good reason. Here is how to notice when the default has become the problem.

Three signals, in rough order of how often they show up in real code:

1. You are inserting or deleting anywhere but the end

Every such operation is O(n). Inside a loop, that is O(n²). If you are queueing work with pop(0), you want a deque. If you are splicing in the middle constantly, you may want a linked list.

2. You are searching by value, repeatedly

x in my_list is O(n). Doing it inside a loop is the single most common accidental O(n²) in working code. If you only need membership, a set makes it O(1).

3. You keep needing the smallest or largest item

min(xs) is O(n), and doing it repeatedly while also removing items is O(n²). A heap gives you O(log n) per removal.

# ---- The three smells, and their fixes ----

# 1. Queue with a list                       O(n) per pop
while queue:
    job = queue.pop(0)
#    → from collections import deque; queue.popleft()   O(1)

# 2. Membership in a loop                    O(n) per check → O(n²)
for x in items:
    if x in blacklist:      # blacklist is a list
        ...
#    → blacklist = set(blacklist)                        O(1)

# 3. Repeatedly taking the minimum           O(n) per take → O(n²)
while tasks:
    nxt = min(tasks)
    tasks.remove(nxt)
#    → import heapq; heapq.heappop(tasks)                O(log n)

>_Playground

Watch a real Python list reallocate, and measure the cost of the operations this chapter claims are expensive.

✓Exercises

Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.