Lists & Aliasing
Lists index like strings but, unlike strings, they can be changed in place. That one difference creates the hardest concept in the course: two names can refer to the same list, so changing it through one name changes what the other sees. Almost every mysterious bug in CSC108 is this.
- Distinguish mutating a list from rebinding a name.
- Predict when two names share a list and when they do not.
- Copy a list correctly, including the nested case.
- Explain why a function can change its caller's list.
Mutation is efficient: appending to a list of a million items does not copy a million items. The cost is that a list is a shared thing, and sharing is invisible in the source unless you are watching for it.
Shared mutable state is the root of most concurrency bugs in every language. The discipline this unit teaches — know who else can see this object — is the same discipline that keeps large systems correct.
Whole languages exist to avoid this. Haskell and Clojure make data immutable by default, so aliasing cannot bite; the trade is that every change copies. Python picks the other side, which is why you have to think about it.
Lists are mutable
A list is an ordered, mutable sequence written [1, 2, 3]. It
indexes and slices exactly like a string, but item assignment is allowed:
xs[0] = 99 works.
xs = [3, 1, 2] xs.append(4) # [3, 1, 2, 4] - adds one item at the end xs.extend([5, 6]) # [3, 1, 2, 4, 5, 6] - adds each item of another list xs.insert(0, 0) # [0, 3, 1, 2, 4, 5, 6] xs.remove(3) # removes the FIRST 3 by value xs.pop() # removes and returns the last item xs.sort() # sorts in place, returns None xs.reverse() # reverses in place, returns None
Every one of these changes xs itself. Contrast the string
methods of Unit 4, which changed nothing.
xs = xs.sort() sets xs to None and
loses the list. The sort already happened; there is nothing to assign. If
you want a sorted copy, use the built-in
sorted(xs), which returns a new list and leaves the original
alone. Same pairing for reverse() and
reversed().
Aliasing
ys = xs binds a second name to the same list. There
is now one list with two names. Mutating through either name is visible
through both.
xs = [1, 2, 3] ys = xs ys.append(4) # MUTATES the shared list print(xs) # [1, 2, 3, 4] - xs sees it ys = [9] # REBINDS ys to a different list print(xs) # [1, 2, 3, 4] - xs unaffected
append reaches into the object. An assignment to the bare name
moves the label somewhere else.xs is ys, which asks whether they
are the same object — different from xs == ys, which asks
whether the contents match.a = [1, 2] b = [1, 2] c = a a == b # True - same contents a is b # False - two separate lists a is c # True - one list, two names
Copying
ys = xs[:] or ys = list(xs) makes
a shallow copy: a new outer list holding the same inner
objects.grid = [[0, 0], [0, 0]] copy = grid[:] # new outer list, SAME two inner lists copy[0][0] = 9 print(grid) # [[9, 0], [0, 0]] - leaked through copy.append([1, 1]) print(len(grid)) # 2 - the outer list really was copied
To copy properly, copy each row:
copy = [row[:] for row in grid].
grid = [[0] * 3] * 2 looks like a 2-by-3 grid and is a
disaster: it makes one inner list and points at it twice. Setting
grid[0][0] = 1 changes both rows. Build it with
[[0] * 3 for _ in range(2)], which evaluates the inner list
fresh each time.
Lists as arguments
Passing a list to a function binds the parameter to the same list. The
function can mutate the caller's data. This is not a leak — it is how
sort works — but it must be deliberate and
documented.
def add_one_bad(xs: list) -> None:
"""Add 1 to every item of xs, modifying xs in place."""
for i in range(len(xs)):
xs[i] = xs[i] + 1
def add_one(xs: list) -> list:
"""Return a new list with 1 added to every item of xs.
>>> add_one([1, 2])
[2, 3]
"""
return [x + 1 for x in xs]None, matching the
convention of sort and append: in-place operations
return nothing.def wipe(xs: list) -> None:
xs = [] # rebinds the LOCAL name only
data = [1, 2, 3]
wipe(data)
print(data) # [1, 2, 3] - untouchedTo actually empty the caller's list you must mutate it:
xs.clear() or del xs[:]. Same rule as
always — assignment moves a label, it does not touch the
object.
• xs = xs.sort(). In-place methods return
None.
• Believing ys = xs copies. It never does.
• Shallow-copying a nested list and being surprised when inner changes
leak.
• [[0] * 3] * 2 for a grid. Use a comprehension.
• Removing from a list while iterating it, as in Unit 2.
Practice
Predict each answer before running it. Original exercises written for this guide in the style of the course's weekly sets.
What prints?
a = [1, 2] b = a b.append(3) b = [7] print(a)
Answer
[1, 2, 3].
The append mutated the shared list; the later assignment only
moved b.What is x?
x = [3, 1, 2].sort()
Answer
None. The
list was sorted and then discarded, since nothing else referred to it. Use
sorted([3, 1, 2]).Copy g = [[1, 2], [3, 4]] so changing the copy cannot
affect g.
Solution
c = [row[:] for row in g]. A plain g[:] shares
the inner lists.What does this print, and why?
g = [[0] * 2] * 2 g[0][0] = 5 print(g)
Answer
[[5, 0],
[5, 0]]. There is only one inner list, referenced twice, so the
change appears in both rows.When is a == b True but a is b False?
Answer
[1, 2] lists. Use == for values;
is only for identity, and in practice mostly for
is None.Write a function returning a new list with duplicates removed, order preserved.
Solution
def dedupe(xs: list) -> list:
"""Return a new list with duplicates of xs removed, keeping first
occurrences in order.
>>> dedupe([1, 2, 1, 3, 2])
[1, 2, 3]
"""
out = []
for x in xs:
if x not in out:
out.append(x)
return outx not in out
scans the whole list each time.Does this change the caller's list?
def f(xs: list) -> None:
xs = xs + [1]Answer
xs + [1] builds a new list and the assignment rebinds only the
local name. xs.append(1) would change the
caller's.Flatten [[1, 2], [3], []] to [1, 2, 3].
Solution
def flatten(rows: list) -> list:
"""Return one list containing every item of every row.
>>> flatten([[1, 2], [3], []])
[1, 2, 3]
"""
out = []
for row in rows:
out.extend(row)
return outextend adds each item; append would add the row
itself as a single nested element.Expanded topic checklist
Course coverage. This unit is part of the complete CSC108H1 topic map. It should cover the following items before you move on:
- Mutation. The in-place methods and the fact they return
None. - Aliasing. Assignment binds names;
isversus==. - Copying. Shallow copy, and the nested case that needs more.
- Parameters. Why a function can change its caller's list, and how to document which it does.
The calendar lists "lists" among the elementary data types. Aliasing is the concept the term test reliably examines through tracing questions; check the syllabus for the assigned exercises.
Names refer to objects, from Unit 1. Lists are mutable, so several names can watch one object change. Copying is the deliberate act of breaking that sharing.
Deep practice extensions
Use these after the main practice set. They push on definitions and edge cases rather than routine calculation.
What does ys = xs do for a list?
Guide
What does xs.sort() return?
Guide
None. Use
sorted(xs) when you want a new sorted
list.When is xs[:] not enough?
Guide
Which changes inside a function are visible to the caller?