Arrays and Dynamic Arrays: How Python Lists Work

An array stores items next to each other in one block of memory. Because every slot is the same size, the computer can jump straight to item i with simple arithmetic:

address of item i = start address + i × slot size

That is why reading items[i] is O(1): no searching, just one calculation. Python's list is an array of references to objects, and everything in this lesson applies to it.

Operation costs#

Why inserting in the middle is slow#

Inserting at the front means every existing item moves one place right. Here is what insert does internally, written out by hand:

def insert_at(items, index, value):
    items.append(None)                 # make room at the end
    moves = 0
    for i in range(len(items) - 1, index, -1):
        items[i] = items[i - 1]        # shift right
        moves += 1
    items[index] = value
    return moves

data = [10, 20, 30, 40, 50]
print(insert_at(data, 0, 5), "moves ->", data)
print(insert_at(data, 6, 60), "moves ->", data)

5 moves -> [5, 10, 20, 30, 40, 50]
0 moves -> [5, 10, 20, 30, 40, 50, 60]

Inserting at the front moved all 5 items; inserting at the end moved none. Deleting is the mirror image: later items shift left to close the gap.

Dynamic arrays: how lists grow#

A plain array has a fixed size. Python lists can grow because they are dynamic arrays: they keep some spare capacity, and when it runs out they allocate a bigger block and copy everything across.

This small class does the same thing and counts the copying:

class DynamicArray:
    def __init__(self):
        self.capacity = 1
        self.size = 0
        self.slots = [None] * self.capacity
        self.copies = 0

    def append(self, value):
        if self.size == self.capacity:          # full: grow
            self.capacity *= 2
            bigger = [None] * self.capacity
            for i in range(self.size):
                bigger[i] = self.slots[i]
                self.copies += 1
            self.slots = bigger
        self.slots[self.size] = value
        self.size += 1

arr = DynamicArray()
for n in range(1, 17):
    arr.append(n)
    if n in (1, 2, 3, 5, 9, 16):
        print(f"size {arr.size:>2}, capacity {arr.capacity:>2}, total copies so far {arr.copies}")

size  1, capacity  1, total copies so far 0
size  2, capacity  2, total copies so far 1
size  3, capacity  4, total copies so far 3
size  5, capacity  8, total copies so far 7
size  9, capacity 16, total copies so far 15
size 16, capacity 16, total copies so far 15

Resizes happen at sizes 1, 2, 4, 8, … The occasional resize is O(n), but they are so rare that 16 appends caused only 15 copies in total: less than one copy per append on average. This is what amortized O(1) means: individual appends may be slow, but the average cost per append stays constant.

2D arrays#

A grid is an array of arrays. Build each row separately:

rows, cols = 3, 4
grid = [[0] * cols for _ in range(rows)]
grid[1][2] = 7
for row in grid:
    print(row)

[0, 0, 0, 0]
[0, 0, 7, 0]
[0, 0, 0, 0]

Common mistakes#

Practice#

def remove_all(items, value):
    write = 0
    for read in range(len(items)):
        if items[read] != value:
            items[write] = items[read]
            write += 1
    del items[write:]          # drop the leftover tail
    return write

data = [3, 1, 3, 2, 3, 4]
print(remove_all(data, 3), data)

3 [1, 2, 4]

Key takeaway#

Next: arrays of characters, in Strings.