Inside the List

Data Structures in Practice

Chapter 2 · Inside the List

The list is the structure you use most, so it pays to know what it is. A Python list is a dynamic array: one block of memory holding a row of references, one per item, side by side. Being a single block explains almost every cost in the table from Data Structures in Practice 1.

What was run, and what was not

Everything below was run. Exact sizes in bytes and the exact points where a list grows can differ between Python versions, so the chapter claims only the pattern. Timing ratios depend on the machine; only the direction and the widening gap are claimed.

Why Position Lookup Is Instant

Because the references sit in a row, item number i is found by arithmetic: start of the block plus i steps. No scanning, whatever the length. That is why items[500000] costs the same as items[0]. The same layout explains the weak spot: to insert at the front, every reference must shift one place to make room, so the work grows with the length of the list.

Operation	Cost	Why
items[i]	constant	arithmetic on the block's start
append(x)	constant, amortised	usually there is spare room
pop()	constant	just shrink the length
insert(0, x)	grows with length	every item shifts right
pop(0)	grows with length	every item shifts left
x in items	grows with length	scans from the start

Over-Allocation: Spare Room at the End

If the block were exactly the right size, every append would need a bigger block and a copy of everything. Python avoids that by over-allocating: when the block is full it grabs noticeably more space than needed. We can watch this with sys.getsizeof, which reports the list's memory size.

import sys

a = []
last = None
changes = []
for i in range(40):
    size = sys.getsizeof(a)
    if size != last:
        changes.append((len(a), size))
        last = size
    a.append(i)
print(changes)
    

One run printed:

[(0, 56), (1, 88), (5, 120), (9, 184), (17, 248), (25, 312), (33, 376)]

Read it as: the size changed only seven times while forty items went in. Between those points, appends found spare room and cost almost nothing. (Your byte counts may differ on another Python version, but you will see the same stepped shape.) In one test, 1000 appends caused only 29 size changes.

Amortised Cost

A growth step is expensive: allocate, copy every reference, free the old block. But because the new block is larger by an amount proportional to the current size, such steps become rarer as the list grows. Spread the occasional big cost over the many cheap appends and the average is a small constant. This is called amortised O(1).

Amortised is not "every time"

A single append can occasionally be slow, because it triggers a growth step. If you need every operation to be fast and predictable, amortised analysis is not a promise about any one call, only about the average over many.

The Cost of Making Room at the Front

Compare two ways to build the same list in reverse order: insert each new item at the front, or append and reverse once at the end.

def insert_front(n):
    a = []
    for i in range(n):
        a.insert(0, i)
    return a

def append_rev(n):
    a = []
    for i in range(n):
        a.append(i)
    a.reverse()
    return a

print(insert_front(5), append_rev(5))
print(insert_front(2000) == append_rev(2000))
    

[4, 3, 2, 1, 0] [4, 3, 2, 1, 0]
True
    

Same result. On the author's machine, insert_front was about 50 times slower at 5,000 items and about 200 times slower at 20,000. The gap grew with the size, the signature of work that depends on the length.

Slicing Copies

A slice such as items[1:] builds a new list and copies the references in it. It is not a view. So a slice that keeps most of a long list costs work proportional to its length, while a slice of a handful of items is cheap whatever the original size.

import timeit

for n in (1000, 100000):
    d = list(range(n))
    big = timeit.timeit(lambda: d[1:], number=200)
    small = timeit.timeit(lambda: d[-5:], number=200)
    print(n, "big slice is", round(big / small), "times slower")
    

The author saw roughly 16 times at 1,000 items and over 5,000 times at 100,000. A recursive function that does f(items[1:]) on every call therefore copies the list again and again; pass an index instead.

Copies Are Shallow

Copying a list copies the references, not the objects they point to. For a list of numbers that is harmless. For a list of lists it hides a trap: the copy and the original share the inner lists.

import copy

x = [1, 2, 3]
y = x            # same list, two names
z = x[:]         # a new list
y.append(4)
print(x, z, y is x, z is x)

m = [[0, 0], [0, 0]]
c = m[:]                  # shallow copy
c[0][0] = 9
print(m, c)

d = copy.deepcopy(m)      # copies the inner lists too
d[1][1] = 7
print(m, d)
    

[1, 2, 3, 4] [1, 2, 3] True False
[[9, 0], [0, 0]] [[9, 0], [0, 0]]
[[9, 0], [0, 0]] [[9, 0], [0, 7]]
    

The grid trap

[[0] * 2] * 2 does not make two rows; it makes one row referenced twice. Setting r[0][0] = 1 gives [[1, 0], [1, 0]]. Build grids with a comprehension, [[0] * 2 for _ in range(2)], which creates a fresh row each time.

A decision habit

Appending and popping at the end of a list is what lists are built for. The moment you work at the front or in the middle, or test membership, ask whether the table points to another structure.

Challenges

Exercise 1

Write growth_points(n) that appends n items to an empty list and returns the list lengths at which sys.getsizeof changed. Run it for n = 100 and say whether the gaps between growth points get wider or narrower.

📄 View solution

Exercise 2

This function sums a list recursively: def total(items): return 0 if not items else items[0] + total(items[1:]). Say what it costs in copying, then rewrite it with an index parameter so no slices are made. Check both give the same answer on list(range(500)).

📄 View solution

Exercise 3

Make a 3 by 3 grid of zeros two ways: with [[0] * 3] * 3 and with a comprehension. Set the middle cell of each to 5 and print both. Explain the difference, then make an independent copy of the good grid and show that changing the copy leaves the original alone.

📄 View solution

Quick Reference

A list is a dynamic array: one block of references, so indexing is instant
Over-allocation gives amortised O(1) append and pop at the end
Front and middle: insert and pop shift items, so cost grows with length
Slices copy; avoid big slices in loops and recursion
Copies are shallow: use copy.deepcopy for nested data
Grids: use a comprehension, never * on a list of lists

Coming next

Data Structures in Practice 3 covers tuples, sets and dicts: what immutability buys you, the rules for hashing, set algebra, and common dict patterns.