Gregory Friedman The Greg Wide Web on the name →
The Arc · lecture I of XIV

Lecture I · Data Structures & Algorithms

A mental model for Python

This course is about choosing the right structure for the job, and every one of those choices lives or dies on a single question: when you write b = a, what just happened? Most bugs I have ever chased in a data-structures course trace back to a wrong answer to that question. So before we build a single stack or tree, let us get the picture of Python’s memory exactly right.

Names are not boxes

The first thing most of us are taught is a lie of convenience: a variable is a box, and assignment puts a value in the box. It is a comforting picture and it will betray you within a week. Python does not work that way.

In Python, an object comes first. The number 3, the list [1, 2, 3], the string "cartography": each is a thing that exists somewhere in memory, with an identity all its own. A name is just a label you tie to one of those objects. Assignment does not copy anything and it does not fill a box. It ties a label to an object that already exists.

x = [1, 2, 3]
y = x

There is one list here, not two. x is a label on it. Then y = x ties a second label to the very same list. No copy is made. If you could photograph memory you would see a single list with two strings pointing at it, the way two names on a mailbox point at one apartment.

Rebinding a name never disturbs the object. x = 3 then x = 4 does not change the number three into four; three is eternal. It moves the label x off the 3 and onto the 4. This is why you should read = as “bind the name on the left to the object on the right,” never as “store.” Once that reading is automatic, a whole category of confusion evaporates.

The aliasing trap

Here is where the box picture costs you real money. Two labels on one object are called aliases, and if that object can be changed in place, then a change made through one label is visible through the other, because there is only one object to change.

a = [1, 2, 3]
b = a
b.append(4)
print(a)   # [1, 2, 3, 4]

Read that slowly. We never touched a. We appended to b. Yet a grew a fourth element, because a and b are two names for one list, and append reaches into that one list and mutates it. If you were holding the box picture, this looks like witchcraft. With the label picture it is obvious, even boring: of course a changed, there was only ever one list.

The plate below is the whole lecture in one figure. Press Trace, then Step through it line by line and keep your eye on the diagram on the right.

python runs in your browser · first run downloads ~240 kb
Plate I The tracer. Two names, one object: the aliasing picture drawn one step at a time. Press Trace, then Step. Watch the diagram at line 2, where a second name arrives, and the arrows for a and b converge on a single box; then at line 3 that one box gains a fourth cell, and a can see it.

When you reach b = a, notice that the diagram does not draw a second list. It draws a second arrow into the first one. That convergence is the entire idea. Everything else in this lecture, and a surprising amount of the rest of the course, is a consequence of it.

None of this happens with numbers, strings, or tuples, because those objects cannot be changed in place. They are immutable. There is no append on a number. So aliasing an immutable object is harmless: the only way to “change” b is to rebind it to a different object, which leaves a pointing where it always did. Mutability is what makes aliasing dangerous, and lists, dicts, and sets are all mutable. Hold that thought; it will decide half your design choices later.

python runs in your browser · first run downloads ~240 kb
Plate II A prediction to settle. Because 5 is immutable, b = b + 1 builds a brand-new integer and rebinds only b; a keeps pointing at the original 5. Contrast this with Plate I, where append mutated the one shared list. Run it, then Trace it if the result surprises you.

The difference between Plate I and Plate II is not a difference in =. The = behaves identically in both. The difference is that a list can be mutated in place and an integer cannot. Same rule, two outcomes.

Sequence, selection, iteration

Now that we know what memory looks like, we can talk about how control moves through it. There are exactly three ways, and you already know all three; the point is to name them so we can reason about cost later.

Sequence is one statement after another, top to bottom. The default. Nothing clever.

Selection is choosing a path: if, elif, else. The program looks at a condition and commits to one branch.

if score >= 90:
    grade = "A"
elif score >= 80:
    grade = "B"
else:
    grade = "C"

Iteration is repetition: for and while. This is the one that matters most for us, because iteration is where cost accumulates. A single line inside a loop that runs a thousand times is a thousand units of work, and if that loop sits inside another loop, you are suddenly doing a million.

for row in grid:
    for cell in row:
        visit(cell)

That nesting is the shape of quadratic cost, and spotting it by eye will become second nature. For today, just notice that iteration is the only one of the three that multiplies. Sequence and selection cost about what they look like. Iteration costs what it looks like times how many times it runs, and choosing a data structure is very often a fight to make that multiplier smaller.

Four collections, four costs

Python hands you four built-in collections, and the entire art of this course is knowing which to reach for. They are not interchangeable. Each is fast at some things and slow at others, and using one where another belonged is the classic beginner mistake that turns a snappy program into a slow one.

A list is an ordered, mutable sequence. It is superb at indexing (xs[i] is instant) and at appending to the end. It is bad at membership tests. Asking x in xs makes Python walk the list from the front, comparing element by element, until it finds x or runs off the end. On a list of a million items that is up to a million comparisons, every single time you ask. We call that cost linear, written O(n)O(n): the work grows in step with the size.

A tuple is a list that cannot be changed: ordered, indexable, immutable. Because it cannot be mutated, it is safe to alias freely and it can serve as a dictionary key. Reach for a tuple when you have a fixed little bundle, like a coordinate (row, col), that should never grow or shrink.

A dict maps keys to values, and here is the payoff: looking a key up, or asking whether a key is present, takes roughly constant time no matter how large the dict grows. We write that O(1)O(1). A dict of a million entries answers k in d about as fast as a dict of ten. It buys this with a hash table, which we will build with our own hands later in the course; for now, treat “I need to look things up by a key, fast” as the sound of a dict.

A set is a dict that kept only its keys. Unordered, no duplicates, and the same constant-time membership test. When you catch yourself writing x in some_list inside a loop, that is the moment to ask whether some_list should have been a set all along.

There is a rule hiding behind that constant-time speed, and it is worth saying out loud now because it decides real design choices. A dict or set finds a key fast by hashing it: it runs the key through a function that turns it into a slot number, then looks only in that one slot, never scanning. For that trick to work the key’s hash must never change, so only immutable objects may be keys. A number, a string, a tuple of those: all fine. A list is not, and Python stops you cold. Writing d = {}; d[[1, 2]] = "x" raises TypeError: unhashable type: 'list'. That is the real reason a coordinate you intend to look up should be a tuple (row, col) and never a list [row, col]. Immutability is not a restriction here, it is the admission ticket for the O(1)O(1) lookup, and it is a bargain.

That last point is worth a measurement. Suppose you have a big collection and you test membership many times:

# xs is a list of 100000 numbers; we test 100000 queries.
hits = 0
for q in queries:
    if q in xs:      # each test walks the list: O(n)
        hits += 1

Every q in xs is a linear scan, so the whole loop does about 100000 * 100000, ten billion comparisons. Turn xs into a set first, xs = set(xs), and each test becomes O(1)O(1), so the loop does about a hundred thousand units of work total. Same code shape, same answer, and the difference between a coffee break and an eyeblink. That is the game, the whole course in one substitution.

One more trap in the same family, because it is so common. Building a big string by repeated += looks innocent and is quietly quadratic:

s = ""
for word in words:
    s += word        # strings are immutable: this copies s every time

Strings are immutable, so s += word cannot extend s in place. It builds a whole new string each pass, copying everything accumulated so far. Over n words that is a triangle of copying, O(n2)O(n^2). The fix is to collect the pieces in a list, which appends cheaply, and join once at the end:

parts = []
for word in words:
    parts.append(word)   # cheap append
s = "".join(parts)       # one pass

Notice what just happened: we chose a different structure, list instead of repeated string concatenation, and a quadratic cost collapsed to linear. We did not get cleverer. We picked the right container. Hold onto that, because it is the move you will make, in one disguise or another, in every lecture that follows.

Identity and equality

We have been leaning on a phrase without pinning it down. When I say two names point at “the same object,” Python has an operator that asks exactly that, and it is not ==.

== asks about value: do these two objects carry the same contents? is asks about identity: are these two names tied to the very same object, the one and only? The two questions usually agree, but they are not the same question, and the gap between them is precisely where aliasing lives.

a = [1, 2, 3]
b = a
c = [1, 2, 3]
print(a == b)   # True: same contents
print(a is b)   # True: b is an alias of a
print(a == c)   # True: same contents
print(a is c)   # False: c is a separate list

a and c are equal but not identical: two different lists that happen to hold the same numbers. a and b are both, because b = a tied a second name to one list. So is is really the aliasing question in operator form, which is exactly why the copy exercises below check copy_list(a) is not a. They are asking, in code, “did you build a genuinely new object, or hand the same one back?”

Now the honest surprise, because you will meet it and it will look like a bug. Ask CPython whether two separately written small integers are identical:

a = 256
b = 256
print(a is b)   # True in CPython: 256 is cached

x = 257
y = 257
print(x is y)   # often False: one past the cache

Python keeps a private stash of small integers, roughly -5 through 256, and hands out the same object every time one of them is needed, so 256 is 256 comes back True. Step one past the cache and the guarantee evaporates. Some short strings get shared the same way. None of this is a rule you may lean on: it is an implementation detail, it varies between Python builds, and code that depends on it is quietly broken. The lesson is not where the boundary sits; the lesson is never use is to compare values. Use == for that, every time.

There is exactly one everyday place where is is the right tool: testing against None. A running program has only ever one None object, so if x is None is the precise, idiomatic check, and you will write it constantly. == for values, is for None and for genuine “same object?” questions. Keep those in their lanes and identity will never surprise you again.

Copies, shallow and deep

The copy you will write in the problems below makes a new list, and for a flat list of numbers that is the end of the story. But the moment a list holds other lists, “make a copy” quietly splits into two different jobs, and picking the wrong one is a bug that hides for weeks.

Picture a grid: a list of rows, each row a list of cells.

grid = [[0, 0], [0, 0]]
copy = grid[:]        # a new outer list
copy[0].append(9)
print(grid)           # [[0, 9], [0, 0]], the original changed too

grid[:] did make a new outer list, so copy is not grid. But it copied the references sitting inside, not the rows themselves. copy[0] and grid[0] are two names for one inner list, the Plate I picture again, one level down. Reach through copy[0] and mutate, and grid[0] sees it, because there is still only one inner list. That is a shallow copy: fresh on the outside, shared underneath.

A deep copy goes all the way down, rebuilding every level so nothing is shared. For a grid that means copying each row too:

deep = [row[:] for row in grid]   # a fresh outer list of fresh rows

Now deep[0] is its own list, and mutating it leaves grid untouched. For arbitrarily nested structures the standard library’s copy.deepcopy does this recursively, but knowing why you reach for it matters more than the import: a shallow copy guards the top level and nothing beneath it. You will build a deep copy by hand in the final problem, and it is worth being able to.

The very same one-shared-object mistake wears a second disguise, famous enough to sit on every list of Python traps: the mutable default argument.

def collect(item, bucket=[]):
    bucket.append(item)
    return bucket

print(collect(1))   # [1]
print(collect(2))   # [1, 2], where did the 1 come from?

That [] is not built fresh on each call. It is created once, when the function is defined, and that single list becomes the default for every call that does not pass its own. So the calls share one bucket and it fills across them like a static variable you never asked for. The picture is the aliasing trap once more: one list, several names, mutation visible through all of them.

The fix is to make the sentinel immutable and build the real object inside:

def collect(item, bucket=None):
    if bucket is None:
        bucket = []
    bucket.append(item)
    return bucket

Notice the is None from the last section earning its keep. Each call with no bucket now gets a fresh list, and the trap is gone. Every one of these bugs, aliasing and shallow copies and shared defaults alike, is the one fact seen from a new side: assignment and argument-passing bind names to objects, they never copy. Learn to see the single object and you have learned to see the bug.

Problems

Work these in order. The last two grade themselves; make every row turn green.

  1. Warm-up. On paper, draw the names-and-objects diagram after these three lines: p = [0], then q = p, then q = [0]. How many list objects exist, and which names point at which? (Careful: the third line rebinds q, it does not mutate anything.)

  2. Predict, then verify in any plate above. What does this print, and why? t = (1, 2); u = t; print(u is t). Then explain in one sentence why aliasing a tuple, unlike aliasing a list, can never surprise you.

  3. You are given a list names and must count how many entries of a second list queries appear in it. Describe the O(n2)O(n^2) way and the near-linear way, and say exactly which structure you would build to get the speedup.

  4. The main event. Write copy_list(a) so that it returns a new list with the same items, fully independent of a: mutating the copy must never touch the original. The starter code just hands back a itself, which is an alias, so the last check fails. Fix it and make all three rows pass.

    The checks · run against your code

    # copy_list returns an equal list
    assert copy_list([1, 2, 3]) == [1, 2, 3]
    # the copy is a different object
    a = [1, 2, 3]
    assert copy_list(a) is not a
    # mutating the copy leaves the original alone
    a = [1, 2, 3]
    c = copy_list(a)
    c.append(99)
    assert a == [1, 2, 3]
    python runs in your browser · first run downloads ~240 kb
    Plate III An independent copy. The starter returns a, an alias, so appending to the copy mutates the original and the third check fails. Return a genuinely new list instead. Press Run to grade against the three checks; use Trace to watch whether one list or two appears.
    Hint one

    Returning a hands back the same object, so the caller ends up with an alias, exactly the Plate I situation. You need a second list that starts life holding a’s items.

    Hint two

    A slice of the whole thing, a[:], builds a fresh list with the same elements. So does list(a). Either makes a new object; check with is.

    The solution

    Any of these returns an independent copy:

    def copy_list(a):
      return a[:]        # or: list(a)  |  or: [x for x in a]

    All three build a new list object holding the same items, so copy_list(a) is a is false and mutating the result leaves a alone. One caution for later: this is a shallow copy. If a held lists of its own, the inner lists would still be shared. We will meet that wrinkle when it starts to bite.

  5. Hashability, on paper. You try to use a point as a dictionary key two ways: first d = {}; d[[0, 0]] = "origin", then d = {}; d[(0, 0)] = "origin". One of them raises TypeError: unhashable type: ‘list’ and the other works fine. Which is which, and why? Answer in terms of what a dict, and a set, must be able to trust about a key that a list cannot promise.

  6. Drive it yourself. Enough watching; take the wheel. The plate below builds a small list, ties a second name to it, and mutates through one name. This is the Plate I story, but now the code is yours to edit and re-run.

    python runs in your browser · first run downloads ~240 kb
    Plate IV Now you drive. One list, two names. The before snapshot is taken with three cells; then a single append through the second name grows that one shared object to four; and the after snapshot, read back through the first name, proves the first name saw it too. Edit the code and Run again to make the picture your own.
  7. See the other three collections. You have watched lists all lecture; now put a dict and a set under the same instrument. Run the plate: the dict draws as key -> value rows, and the set draws as unordered cells with the repeated “Belgrade” collapsed to one. The membership test on the last line is O(1)O(1), which is the entire reason a set exists. Try adding a duplicate to the dict or the set and re-running to see what each one keeps.

    python runs in your browser · first run downloads ~240 kb
    Plate V The other three, drawn. A dict prints as key-to-value rows and a set as unique cells in no order you may lean on; the repeated Belgrade collapses to a single member. That final membership test answers in constant time, which is the whole point of reaching for a set.
  8. Keep the order, lose the repeats. Write dedupe_preserve_order(items) so it returns the items with duplicates removed but the order of first appearance intact. The stub reaches for list(set(items)), which does delete the repeats but throws the order away, so the two order checks fail. Use a set for the O(1)O(1) membership test and a list to hold the order, and turn every row green.

    The checks · run against your code

    # every distinct item survives exactly once
    assert sorted(dedupe_preserve_order([3, 1, 3, 2, 1])) == [1, 2, 3]
    # first-seen order is kept, not sorted and not shuffled
    assert dedupe_preserve_order([3, 1, 3, 2, 1]) == [3, 1, 2]
    # strings behave the same way: the first "c" wins its slot
    assert dedupe_preserve_order(["c", "a", "b", "a", "c"]) == ["c", "a", "b"]
    # an empty list stays empty
    assert dedupe_preserve_order([]) == []
    python runs in your browser · first run downloads ~240 kb
    Plate VI Order kept, repeats dropped. The stub returns list(set(items)): the set deletes duplicates but scrambles the order, so the first-seen-order checks fail. Carry a seen set for the fast membership test and an out list for the answer. Press Run to grade against the four checks.
    Hint one

    list(set(items)) is the classic trap: a set has no order you can rely on, so the result comes back reshuffled. You need two structures working together, one to answer “have I seen this?” and one to remember “in what order?”.

    Hint two

    Walk items once. Keep a seen set for the fast membership test and an out list for the answer. For each element, if it is not in seen, add it to both. First occurrences land in out in order; the repeats are skipped.

    The solution

    A set for speed, a list for order, one pass:

    def dedupe_preserve_order(items):
      seen = set()
      out = []
      for x in items:
          if x not in seen:      # O(1) membership, not an O(n) scan
              seen.add(x)
              out.append(x)      # first time only: order preserved
      return out

    Each x not in seen is the constant-time set lookup from the collections section, so the whole routine is O(n)O(n). Swap in if x not in out against the list instead and every test becomes a linear scan, dragging the routine to O(n2)O(n^2): the exact substitution this lecture keeps making, now made with your own hands.

  9. One level deeper than the last coding problem. A grid is a list of rows, each row a list of cells. Write deep_copy_grid(g) so the result is independent at both levels: mutating any row of the copy must never reach back into g. The starter returns a shallow copy, g[:], which builds a new outer list but shares every inner row, so the third check fails. Rebuild the rows too and turn all three rows green.

    The checks · run against your code

    # the copy equals the original grid
    assert deep_copy_grid([[1, 2], [3, 4]]) == [[1, 2], [3, 4]]
    # the outer list is a new object
    g = [[1, 2], [3, 4]]
    assert deep_copy_grid(g) is not g
    # the rows are new too: mutating one must not touch g
    g = [[1, 2], [3, 4]]
    d = deep_copy_grid(g)
    d[0].append(99)
    assert g == [[1, 2], [3, 4]]
    python runs in your browser · first run downloads ~240 kb
    Plate VII Deep versus shallow. The starter copies only the outer list, so the copy's rows are still the originals: appending to a row of the copy mutates g and the third check fails. Copy each row as well. Press Run to grade against the three checks; use Trace to watch whether one inner list or two appears.
    Hint one

    g[:] copies the outer list but not the rows inside it. d[0] and g[0] are still two names for one row, the Plate I picture one level down. Each row has to become its own new list.

    Hint two

    Copy every row as you go. A comprehension does it in one line: a new list whose elements are row[:] for each row in g. list(g) or g[:] alone only touches the top level, so it cannot pass the third check.

    The solution

    Copy the outer list and every row inside it:

    def deep_copy_grid(g):
      return [row[:] for row in g]     # or: [list(row) for row in g]

    Each row[:] builds a fresh inner list, so the copy shares nothing with g at either level: d[0] is g[0] is now false, and appending to a row of the copy leaves g alone. For structures nested deeper than this, or a mix of types, copy.deepcopy recurses all the way down; here one comprehension is enough. This is the shallow copy caveat from the previous solution, finally paid in full.

One more layer: classes, and where a method lives

The whole lecture has been about one object worn by many names. Classes add a second question on top of it: when you write rex.speak(), whose speak runs? Python answers it with a rule as mechanical as the aliasing rule, and once you see the machinery there is no mystery left.

A class is a template, and one class can inherit from another. Say Dog and Cat both inherit from Animal, which (like everything in Python) inherits from object. Each class defines only the methods special to it, and borrows the rest from above. When you call a method, Python does not guess: it lines the classes up in a fixed order, the method resolution order or MRO, and walks it left to right, subclass first and base last, taking the first class that defines the name. So rex.speak() finds Dog’s own speak and stops, a subclass method shadowing the base; rex.describe() misses Dog and inherits Animal’s; and rex.purr() walks the whole MRO, Dog→Animal→objectDog \to Animal \to object, finds purr on none of them, and raises AttributeError, because purr lives only on Cat, which is nowhere on rex’s MRO.

The plate below draws that hierarchy as boxes, each listing the methods it actually defines. Pick an object, then press a method and watch the lookup light up the MRO chain in blue, mark the classes it searched and missed, and settle on the one class (in ochre) that finally answers. The panel underneath holds the same two instances four ways, one built-in collection per row, so the two halves of this course, the objects and the containers that carry them, sit in one frame.

Animal, and the two classes below it

objectthe root of every classAnimal__init__()describe()speak()legs()Dogspeak()fetch()Catpurr()speak()

Dog and Cat each inherit from Animal, which inherits from object. A box lists only the methods that class defines for itself. Enable JavaScript to pick an instance and press a method, then watch Python walk the method resolution order (subclass first, base last) and stop at the first class that defines the name.

The same two objects, held four ways

Collection Written One-line character
list [rex, felix, rex] Ordered and mutable; indexed by position; duplicates welcome.
tuple (rex, felix) Ordered but frozen; indexed by position; hashable, so it can be a key.
set {rex, felix} No order you may lean on; mutable; every member unique; O(1) membership.
dict {"rex": rex, "felix": felix} Keyed, mutable, insertion-ordered; O(1) lookup by key.

Four containers, the same two Dog and Cat instances inside. Which one you reach for is the same choice the rest of this lecture keeps making: order or none, changeable or frozen, duplicates or unique, found by position or by key.

Plate VIII The lookup, drawn. Dog and Cat inherit from Animal, and Animal from object; each box lists only the methods it defines. Pick rex or felix, press a method, and Python walks the MRO subclass-first: blue is the chain it searches, rose a class searched without a match, ochre the class that defines the method (its row lit too). A missing method, like rex.purr, runs off the end of the MRO and raises AttributeError. Below, the same two objects sit in a list, a tuple, a set, and a dict, one line of character each.

Notice that inheritance is the aliasing lesson in a different key. A method defined once in Animal is not copied into Dog and Cat; there is a single describe, and both subclasses reach up the MRO to the one object that holds it, exactly the way two names reached one list. Learn to see the single object, up the chain or across a pair of labels, and the whole picture holds together.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.