Lists and arrays

The Python list is the data structure you have used most, from the coffee list in PYTH-101 to the order lines in PYTH-102. It is also the foundation for understanding every other structure in this course, because its speed comes from the way it is laid out in memory. Some list operations take the same tiny amount of time whether the list holds ten items or ten million; others get slower in direct proportion to the length. Knowing which is which is the single most useful piece of performance knowledge a Python programmer can have.

This lesson looks inside the list. It explains what an array is, how Python's list builds a growable array on top of one, why appending is fast but inserting at the front is slow, what slicing and copying really cost, and how to work with two-dimensional data such as Ridgeline's weekly sales grid. It ends with the array module and a preview of when a different structure is the better choice.

Arrays: items side by side

An array stores items in one continuous block of memory, one after another, each taking the same amount of space. That layout makes finding an item by its position extremely fast. If the block starts at memory address a and each slot takes s bytes, item i is at address a + i × s: one multiplication and one addition, whatever the length of the array. This is why indexing is O(1), constant time.

The same layout makes some changes expensive. To insert a new item at position 0, every existing item must move one slot along to make room, and removing the first item means moving every other item back. Both are O(n). Changing an item that is already there, by contrast, is O(1): the slot is found by arithmetic and overwritten.

A Python list is an array with two refinements. First, its slots do not hold the items themselves but references (memory addresses) to objects stored elsewhere, which is why one list can hold strings, numbers and Coffee objects side by side while every slot stays the same size. Second, the list grows automatically when it fills up, which the next section explains.

sales = [18.50, 22.00, 19.75, 20.25]
sales[2] = 19.95                   # O(1): overwrite a slot
print(sales[0], sales[-1], sales[2])

mixed = ["RC-101", 42, 18.5, None]
print([type(x).__name__ for x in mixed])

18.5 20.25 19.95
['str', 'int', 'float', 'NoneType']

Dynamic arrays and amortized append

A raw array has a fixed size, chosen when it is created. Python's list hides this by allocating more slots than it currently needs. When you append and a spare slot is free, the item goes straight in: O(1). When the spare slots run out, Python allocates a bigger block, copies every reference across and frees the old block, which is O(n). Because each resize makes the block larger by a proportion of its current size, resizes become rarer as the list grows.

Averaged over many appends, the occasional expensive copy is spread so thinly that each append costs a constant amount. This is called amortized O(1). You can watch the capacity jump by checking the list's memory size with sys.getsizeof as items are added; the exact sizes depend on the Python version and the machine, but the pattern of occasional jumps is always there.

import sys

items = []
last = sys.getsizeof(items)
jumps = 0
for i in range(64):
    items.append(i)
    size = sys.getsizeof(items)
    if size != last:
        jumps += 1
        last = size
print(f"64 appends caused {jumps} resizes")
print("resizes are rare:", jumps < 64 // 4)

64 appends caused 8 resizes
resizes are rare: True

Amortized cost is a promise about a long sequence of operations, not each single one. A program that needs every individual operation to be quick, such as a point-of-sale screen, can still feel the occasional resize on a very large list, but for almost all purposes appending to a list is effectively constant time.

def copies_made(n, growth=2):
    """Simulate a doubling array: how many item copies do n appends cause?"""
    capacity, size, copies = 1, 0, 0
    for _ in range(n):
        if size == capacity:
            copies += size          # copy every item into the bigger block
            capacity *= growth
        size += 1
    return copies

for n in [10, 1_000, 1_000_000]:
    c = copies_made(n)
    print(f"{n:>9,} appends: {c:>9,} copies, {c / n:.2f} per append")

       10 appends:        15 copies, 1.50 per append
    1,000 appends:     1,023 copies, 1.02 per append
1,000,000 appends: 1,048,575 copies, 1.05 per append

The cost of common list operations

Once you picture a list as an array of references, the cost of each operation follows directly. Working at the end of the list is cheap; working at the front or in the middle means shifting the items after the change point; searching means looking at items one at a time. The table summarizes the operations you use every day.

The difference between front and back is easy to measure. The listing below removes 20,000 orders from a list, once from the front and once from the back, counting how many item moves the front version implies. Run it to see the times on your own machine.

import time

def drain_front(n):
    queue = list(range(n))
    while queue:
        queue.pop(0)                 # shifts every remaining item

def drain_back(n):
    stack = list(range(n))
    while stack:
        stack.pop()                  # nothing shifts

for f in (drain_front, drain_back):
    start = time.perf_counter()
    f(20_000)
    print(f"{f.__name__}: {time.perf_counter() - start:.4f} s")
print("item moves implied by drain_front:", sum(range(20_000)))

drain_front: 0.0412 s
drain_back: 0.0011 s
item moves implied by drain_front: 199990000

Draining from the front implies almost 200 million item moves. If a program needs to remove items from the front regularly, such as orders waiting to be packed in arrival order, a list is the wrong structure; lesson 3 introduces collections.deque, which adds and removes at both ends in O(1).

def running_totals(sales):
    totals = []
    for i in range(len(sales)):
        totals.append(round(sum(sales[:i + 1]), 2))
    return totals

print(running_totals([18.5, 22.0, 3.25]))

Slicing and copying

Slicing looks cheap but builds a brand-new list, copying references to every item in the slice: items[a:b] costs O(b - a) time and memory. That is usually fine, but a loop that slices on every pass, such as the starter in the exercise above, quietly becomes quadratic. When you only need to look at a range, loop over the indexes, or use itertools.islice, instead of copying.

Copies are also shallow. Copying a list copies the references, not the objects they point to, so two lists can end up sharing the same inner objects. That matters as soon as the items are mutable, such as lists or dictionaries. copy.deepcopy copies the inner objects as well, at a higher cost.

import copy

week = [["RC-101", 5], ["RC-104", 2]]
shallow = week.copy()
deep = copy.deepcopy(week)
week[0][1] = 99                      # change an inner list
print(shallow[0], deep[0])
print(shallow[0] is week[0], deep[0] is week[0])

['RC-101', 99] ['RC-101', 5]
True False

Two-dimensional data

Kai keeps a weekly grid of bags roasted: one row per coffee and one column per day. In Python, a natural representation is a list of lists, where grid[r][c] is the value at row r and column c. Reading or writing one cell is O(1), a pass over every cell is O(rows × columns), and summing a column means visiting one cell in every row.

There is one classic trap. Writing [[0] * 7] * 3 does not make three separate rows: it makes one row and three references to it, so changing one cell appears to change a whole column. Build each row separately with a comprehension instead.

days = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]
wrong = [[0] * 7] * 3
wrong[0][0] = 30
print("wrong:", [row[0] for row in wrong])

grid = [[0] * 7 for _ in range(3)]          # three separate rows
grid[0][0], grid[1][2], grid[2][4] = 30, 30, 30
print("right:", [row[0] for row in grid])

coffees = ["RC-101", "RC-104", "RC-106"]
grid[0][3] = 30
for name, row in zip(coffees, grid):
    print(name, sum(row))
print("Wed total:", sum(row[days.index("Wed")] for row in grid))

wrong: [30, 30, 30]
right: [30, 0, 0]
RC-101 60
RC-104 30
RC-106 30
Wed total: 30

def column_totals(grid):
    return [sum(row) for row in grid]

print(column_totals([[30, 0, 30], [0, 30, 0]]))

The array module and when to use something else

Because a list stores references, each number in it is a full Python object, which takes far more memory than the raw value. The standard library's array module stores numbers of one type directly in a compact block, like arrays in C. It supports the same indexing, slicing and appending as a list, with the same costs, but uses much less memory for large numeric data. You choose the type with a code such as 'd' for floating-point numbers or 'i' for integers.

import array, sys

weights = [round(10.2 + k * 0.01, 2) for k in range(10_000)]
packed = array.array("d", weights)
print(packed[0], packed[-1], len(packed))
print("array uses less memory:", sys.getsizeof(packed) < sys.getsizeof(weights) + 24 * len(weights))
packed.append(10.15)
print(packed.typecode, len(packed))

10.2 110.19 10000
array uses less memory: True
d 10001

For serious numeric work, PYTH-250 introduces NumPy, whose arrays add fast whole-array arithmetic. For everyday programs the list remains the right default. Reach for something else when the access pattern fights the array layout: frequent removal from the front calls for a deque (lesson 3), frequent membership tests call for a set or dictionary (lesson 5), and keeping items in sorted order while inserting calls for the bisect module (lesson 7) or a heap (lesson 10).

products = [{"sku": f"RC-{k}", "stock": k % 3} for k in range(100, 109)]
products[:] = [p for p in products if p["stock"] > 0]
print([p["sku"] for p in products])

['RC-100', 'RC-101', 'RC-103', 'RC-104', 'RC-106', 'RC-107']

def dedupe(skus):
    return sorted(set(skus))

print(dedupe(['RC-104', 'RC-101', 'RC-104']))