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.
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.
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 : 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 . 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 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 , 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, . 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.
Warm-up. On paper, draw the names-and-objects diagram after these three lines:
p = [0], thenq = p, thenq = [0]. How many list objects exist, and which names point at which? (Careful: the third line rebindsq, it does not mutate anything.)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.You are given a list
namesand must count how many entries of a second listqueriesappear in it. Describe the way and the near-linear way, and say exactly which structure you would build to get the speedup.The main event. Write
copy_list(a)so that it returns a new list with the same items, fully independent ofa: mutating the copy must never touch the original. The starter code just hands backaitself, 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 kbPlate 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
ahands 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 doeslist(a). Either makes a new object; check withis.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 ais false and mutating the result leavesaalone. One caution for later: this is a shallow copy. Ifaheld lists of its own, the inner lists would still be shared. We will meet that wrinkle when it starts to bite.Hashability, on paper. You try to use a point as a dictionary key two ways: first
d = {}; d[[0, 0]] = "origin", thend = {}; d[(0, 0)] = "origin". One of them raisesTypeError: 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.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 kbPlate 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. 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 , 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 kbPlate 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. 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 forlist(set(items)), which does delete the repeats but throws the order away, so the two order checks fail. Use a set for the 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 kbPlate 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
itemsonce. Keep aseenset for the fast membership test and anoutlist for the answer. For each element, if it is not inseen, add it to both. First occurrences land inoutin 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 outEach
x not in seenis the constant-time set lookup from the collections section, so the whole routine is . Swap inif x not in outagainst the list instead and every test becomes a linear scan, dragging the routine to : the exact substitution this lecture keeps making, now made with your own hands.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 intog. 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 kbPlate 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]andg[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 eachrowing.list(g)org[:]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 withgat either level:d[0] is g[0]is now false, and appending to a row of the copy leavesgalone. For structures nested deeper than this, or a mix of types,copy.deepcopyrecurses 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, , 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
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.
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.