Lists, tuples and the aliasing bug
Why b = a does not copy a list, what shallow and deep copies mean, when a tuple is the right answer, and the cost of every list operation you will use.
Lists are where the "a name is a label" model from lesson 1 stops being philosophy and starts causing bugs.
The aliasing bug
a = [1, 2, 3]
b = a
b.append(4)
print(a) # [1, 2, 3, 4]
print(b) # [1, 2, 3, 4]There is one list and two names for it. b = a copied the reference, not the list. This is the
bug that shows up as "my function modified my input", and it is worth being able to explain in
one sentence.
Four ways to actually copy:
a = [1, 2, 3]
b = a[:] # slice — a full copy
c = list(a) # constructor
d = a.copy() # method, Python 3.3+
import copy
e = copy.copy(a) # explicit shallow copyAll four are shallow: they produce a new outer list whose elements are the same objects. For a flat list of numbers or strings, shallow is all you need. For a nested list, it is not:
grid = [[0, 0], [0, 0]]
copy_of = grid[:] # new outer list...
copy_of[0][0] = 9 # ...but the inner lists are shared
print(grid) # [[9, 0], [0, 0]] — the original changedFor that you need deepcopy, which walks the whole structure:
import copy
safe = copy.deepcopy(grid)
safe[0][0] = 9
print(grid) # [[0, 0], [0, 0]] — untoucheddeepcopy is correct and slow. Use it when you mean it.
The [[0] * 3] * 2 trap
This one appears in coding rounds and eats submissions:
grid = [[0] * 3] * 2
grid[0][0] = 1
print(grid) # [[1, 0, 0], [1, 0, 0]] — both rows changed[x] * n repeats the reference n times. The outer list holds two pointers to one inner list.
The correct way to build a 2-D grid is a comprehension, which evaluates the inner expression
each time:
grid = [[0] * 3 for _ in range(2)]
grid[0][0] = 1
print(grid) # [[1, 0, 0], [0, 0, 0]] — correct[0] * 3 on the inside is fine, because integers are immutable — there is nothing to share.
Lists in a function
Because arguments are passed by binding a name to the same object, a mutable argument can be changed by the callee:
def add_marks(marks):
marks.append(100) # mutates the caller's list
scores = [80, 90]
add_marks(scores)
print(scores) # [80, 90, 100]But rebinding the parameter does not affect the caller, because that only points the local name somewhere new:
def replace(marks):
marks = [0] # rebinds the local name only
scores = [80, 90]
replace(scores)
print(scores) # [80, 90] — unchangedThe correct name for this is call by object reference (sometimes call by sharing). It is neither C's pass-by-value nor pass-by-reference in the C++ sense, and saying so accurately is worth a mark.
The list methods, and what they cost
xs = [3, 1, 2]
xs.append(4) # add one at the end O(1) amortised
xs.extend([5, 6]) # add many at the end O(k)
xs.insert(0, 0) # insert at index O(n) — shifts everything after
xs.pop() # remove and return last O(1)
xs.pop(0) # remove and return first O(n)
xs.remove(3) # remove first matching VALUE O(n)
del xs[1] # remove by index O(n)
xs.index(2) # first index of a value O(n)
xs.count(2) # occurrences O(n)
xs.sort() # sort in place, returns None O(n log n)
xs.reverse() # reverse in place O(n)
xs.clear() # empty it O(n)
2 in xs # membership O(n)Two of those lines decide whether a solution passes:
xs.pop(0) is O(n). Using a list as a queue means every dequeue shifts the entire list. If
you need a queue, use collections.deque, where both ends are O(1):
from collections import deque
q = deque([1, 2, 3])
q.append(4) # right, O(1)
q.popleft() # left, O(1)x in xs is O(n). If you are checking membership inside a loop, you have written an O(n²)
solution. Convert to a set first — lesson 5.
sort versus sorted
xs = [3, 1, 2]
xs.sort() # sorts xs, returns None
ys = sorted(xs) # leaves xs alone, returns a new listxs = xs.sort() sets xs to None, and it is one of the most common beginner bugs. Both accept
the same options:
words = ["banana", "kiwi", "apple"]
print(sorted(words, key=len)) # ['kiwi', 'apple', 'banana']
print(sorted(words, reverse=True)) # ['kiwi', 'banana', 'apple']
students = [("Raja", 87), ("Anu", 92), ("Vik", 87)]
print(sorted(students, key=lambda s: (-s[1], s[0])))
# [('Anu', 92), ('Raja', 87), ('Vik', 87)]That last line is the pattern for "sort by score descending, then by name ascending", and it comes up in ranking questions constantly. Python's sort is stable — equal keys keep their original order — which is why you can sort by one key and then another and get a sensible result.
Tuples
A tuple is an immutable sequence. Same indexing and slicing, no methods that modify:
point = (3, 4)
print(point[0]) # 3
point[0] = 5 # TypeErrorThree real reasons to use one:
1. It says "this will not change." A pair of coordinates, a database row, a return value with two parts. Readers trust it.
2. It can be a dict key or a set element. Lists cannot, because keys must be hashable and hashability requires immutability:
seen = set()
seen.add((1, 2)) # fine
seen.add([1, 2]) # TypeError: unhashable type: 'list'This is the standard way to remember visited cells in a grid problem.
3. Unpacking. Tuples make multiple return values and swaps natural:
def divide(a, b):
return a // b, a % b
q, r = divide(17, 5) # 3 2
a, b = 1, 2
a, b = b, a # swap, no temporary variable
first, *rest = [1, 2, 3, 4] # 1, [2, 3, 4]One caveat worth knowing: a tuple being immutable does not make its contents immutable.
t = ([1], [2])
t[0].append(9)
print(t) # ([1, 9], [2])The tuple still holds the same two lists — and those lists changed. So a tuple containing a list is not hashable either.
A one-element tuple needs a trailing comma, and this is a real source of confusion:
print(type((1))) # <class 'int'> — just brackets
print(type((1,))) # <class 'tuple'>What to take into an interview
b = aon a list creates a second name for one list.a[:],list(a)anda.copy()copy.- A copy is shallow by default; nested structures need
copy.deepcopy. [[0] * 3] * 2shares one inner list. Use[[0] * 3 for _ in range(2)].- Mutating an argument affects the caller; rebinding it does not. Call by object reference.
pop(0)andinsert(0, x)are O(n) — usecollections.dequefor a queue.inon a list is O(n); on a set it is O(1).list.sort()mutates and returnsNone;sorted()returns a new list. Both are stable.- Tuples are hashable, so they can be dict keys and set members — lists cannot.