COMP 202 Foundations of Programming • McGill University, Montreal
Revision sheet: Lists, dictionaries and the structure to choose (COMP 202)
This sheet is not a summary of the data structures chapter of COMP 202 at McGill University: the course notes already do that. It answers one question, what loses marks on lists, dictionaries, sets and tuples, on the paper midterm and in the assignments marked by the autograder, and which precise gesture avoids each loss.
The angle of the chapter: a structure is chosen on the question the program will keep asking, never on the syntax you know best. Once the structure is right, the marks are lost in the mechanics, a mutating call whose None is stored, a copy that shares its inner lists, a key that cannot be hashed, a dictionary changed while it is being walked. Every trap below is a line from a real submission, with the line to write instead.
Mark this sheet as read or add it to your favourites: a free account, no password, keeps your read sheets and favourites from one visit to the next and tells you which chapter to tackle next. Create your space, an email is enough.
The thread of the chapter
The marks on this chapter go to two things. Choosing the structure on the QUESTION the loop will keep asking: what is at position i is a list, what belongs to this key is a dictionary, have I seen this one is a set, a record that must never change is a tuple. And knowing what a call hands back: every call that changes a list returns None, and a copy stops at the level you asked for.
Four structures, four questions: choose on the question, not on the syntax
•A list answers what is at position i and in what order. Positions start at 0, duplicates are allowed, and finding whether a value is in it means scanning the whole list.
•A dictionary answers what belongs to this key. The lookup costs the same whether it holds 3 entries or 300000, and that single property is the reason it exists.
•A set answers have I already seen this one, at the same constant cost, and it refuses duplicates and order. A tuple is a record that refuses change, which is exactly what allows it to be a dictionary key.
•A key must be immutable: a string, a number or a tuple of immutables. A list as a key is refused with TypeError, unhashable type: list.
•Several values under one key is a dictionary whose values are lists, filled with marks[name] = marks.get(name, []) + [value].
Read the first column, then the third: a membership test on a list is the only line whose cost grows with the size, which is why the same test is written against a set.
On the midterm, a question that starts with the wrong structure is marked as wrong even when the loop that follows is correct: the marker reads the structure first.
What a call gives back: a change to the list returns None
•append, extend, insert, remove, sort and reverse CHANGE the list and return None. pop is the only mutating call that returns something, the element it removed.
•sorted(values), values + other and values[:] build a NEW object and leave the original alone. values += [x] extends in place.
•remove takes a VALUE; del values[i] and values.pop(i) take a POSITION. index(x) returns a position or raises ValueError, so test x in values first.
•d[k] raises KeyError when k is absent; d.get(k) returns None; d.get(k, 0) returns the default you gave. Iterating a dictionary gives its KEYS, in insertion order; .values() and .items() give the rest.
•b = a gives the same list a second name. b = a[:], list(a) and a.copy() copy the outer level only; copy.deepcopy(a) copies every level.
A mutating call is a STATEMENT on its own line, never the right-hand side of an assignment. values = values.append(x) can be marked wrong without running it.
The rules in table form
Each row reads from left to right: the assumptions, then the result. A red cell is not an answer, it is the finding that the form settles nothing and the instruction to rewrite it. Every case is followed by a worked example.
You write, you expect, you get
The chapter's silent errors: the line runs without complaint and the value it produces is not the one the student had in mind. A red cell is a result that will never come, and the row says what to write instead.
You write
You expect
You get
r = values.append(7)
the enlarged list in r
Noneno value comes back
Example: values = [1, 2] then r = values.append(7): values is [1, 2, 7], with 3 elements, and r is None.
What to do: Call values.append(7) on its own line, then use values.
values + [7]
values changed
a NEW list
Example: [1, 2] + [7] gives [1, 2, 7], and the original still has 2 elements unless you assign the result back.
values.append([3, 4])
two more elements
ONE more element, a list
Example: [1, 2] after append([3, 4]) is [1, 2, [3, 4]], length 3; after extend([3, 4]) it is [1, 2, 3, 4], length 4.
b = a[:] on a list of lists
an independent copy
the inner lists sharedouter level only
Example: a = [[1, 2], [3, 4]], b = a[:], b[0].append(9): a is now [[1, 2, 9], [3, 4]], while b.append([9]) leaves a with 2 elements.
What to do: import copy, then b = copy.deepcopy(a); or rebuild by comprehension.
d['x'] with 'x' absent
None, or 0
KeyErrorraises
Example: {'a': 1}['b'] raises KeyError; {'a': 1}.get('b', 0) gives 0 and leaves the dictionary at 1 entry.
What to do: d.get('x', 0) when absence is normal; d['x'] only when absence is a bug you want to see.
for k in d:
the values
the KEYS
Example: for k in {'Ana': 7.5, 'Ben': 6}: gives 'Ana' then 'Ben'; the average is sum(d.values()) / len(d), that is 6.75.
x in seen, seen a list
one quick test
a scan of the list
Example: 20000 registrations each tested against a list of the previous ones: up to 20000 times 20000, 400 million comparisons. Against a set: 20000 lookups.
Every red cell is the same error in a different costume: the student read the line as what they MEANT, not as what Python does. The five second check of each row is a print of len or of type just after the line.
The mistakes that cost marks
These are the errors I correct most often in session. Each one costs marks on a paper, even when the reasoning behind it is right.
1.Storing the result of a mutating call
the whole function in an autograded assignment: every later line raises TypeError, NoneType object is not subscriptable
What not to write
“values = values.append(x)” or “names = names.sort()”, then the next line uses values.
What to write
“values.append(x)” on its own line: the call changes the list and returns None, so there is nothing to store.
Why: Every method that changes a list returns None by design. The assignment throws the list away and keeps the None. The one exception is pop, which returns the element it removed.
2.append where extend was meant
2 to 3 marks, and a list of lists where a flat list was expected
What not to write
“values.append([3, 4]) adds 3 and 4 to the list.”
What to write
“values.extend([3, 4]) adds each element; values.append([3, 4]) adds ONE element, the list [3, 4], and len grows by 1.”
Why: append adds exactly one thing, whatever that thing is. The error is silent until a later loop finds a list where it expected a number, usually in a sum.
3.Removing by position with a call that takes a value
the whole question when the list holds small integers, because the wrong element is removed without any error
What not to write
“values.remove(2) removes the element at index 2.”
What to write
“values.remove(2) removes the first element EQUAL to 2, and raises ValueError if there is none. To remove the element at index 2, write del values[2], or values.pop(2) when you still need it.”
Why: remove is the only one of the three that takes a value; del and pop take a position. On [10, 20, 2, 30], remove(2) drops the 2 at index 2 by luck; on [10, 2, 20, 30] it drops the wrong one.
4.Building a grid with [[0] * 3] * 3
the whole question: every write shows up in all three rows, and the board or matrix that follows is wrong everywhere
What not to write
“grid = [[0] * 3] * 3, then grid[0][0] = 1 sets the top left square.”
What to write
“grid = [[0] * 3 for r in range(3)]: the comprehension runs [0] * 3 once per row, so the three rows are three objects.”
Left, the three names of the outer list point at ONE row, so a 1 written through grid[0] is seen through grid[1] and grid[2]; right, three arrows, three rows, and the 1 stays in row 0.
Why: The outer multiplication repeats the REFERENCE to one inner list three times. The inner [0] * 3 is safe because its elements are numbers, which cannot be changed in place.
5.Reading a missing key with brackets inside a counting loop
the whole question: the first word raises KeyError, and the autograder marks the function as crashing
What not to write
“for w in words: counts[w] = counts[w] + 1”
What to write
“for w in words: counts[w] = counts.get(w, 0) + 1”, with counts = {} written BEFORE the loop.
Why: Brackets on an absent key raise; get with a default returns the default. The first time a word is seen there is nothing to add 1 to, and get supplies the 0 without an if.
6.Deleting from a dictionary while iterating over it
the whole question: RuntimeError, dictionary changed size during iteration, on the first deletion
What not to write
“for code in stock: if stock[code]['qty'] == 0: del stock[code]”
What to write
“empty = [code for code in stock if stock[code]['qty'] == 0], then for code in empty: del stock[code]”: collect the keys first, delete afterwards.
Why: The loop walks the dictionary's own key table, and that table moves under it as soon as an entry is removed. On a list the same shape does not crash, it silently SKIPS the element after each removal, which is worse.
7.A list used as a dictionary key
the whole question: TypeError, unhashable type: list, on the first assignment
What not to write
“visited[[row, col]] = True”
What to write
“visited[(row, col)] = True”: a key must be immutable, and the tuple (row, col) is the standard key for a position.
Why: A dictionary computes where to store the value FROM the key, so the key must never change afterwards. Python enforces it by refusing every mutable type, and a tuple that contains a list is refused for the same reason.
8.A membership test written against a list inside a loop
the whole question when the autograder has a time limit, and 2 marks for the cost argument on paper
What not to write
“seen = [], then for number in numbers: if number in seen: reject, else seen.append(number)”, on 20000 registrations.
What to write
“seen = set(), then if number in seen: reject, else seen.add(number)”: the same test, at constant cost per element.
Why: in on a list scans the list, so the loop does up to 20000 times 20000, 400 million comparisons. in on a set is one lookup, 20000 in all. The code is one word longer and twenty thousand times faster.
9.A tuple of one element written without its comma
1 to 2 marks on a paper question about types, and a TypeError when the value is later unpacked or indexed
What not to write
“point = (5), so point is a tuple with one element.”
What to write
“(5) is the integer 5 in parentheses; a tuple of one element is written (5,), with the comma, and len((5,)) is 1.”
Why: It is the comma that makes a tuple, not the parentheses: 2, 5 is already a tuple, and (2, 5) only adds brackets for reading. With one element the comma is the only thing left to say so.
Which method to choose
Which structure, from the question the loop will ask
Before writing the loop, write the question the program will keep asking about the data, then read the branch that names it
The same three marks in four shapes: the list keeps position 1, the dictionary keeps who scored what, the set keeps only who is there, and the tuple keeps a pair that cannot move.
If what is at position i, or in what order did they arrive → a list; grow it with append, walk it with for x in values
Example: the marks of one student in the order the assignments came back: marks.append(new_mark)
If what belongs to this name, this code, this key → a dictionary; write with d[k] = v, read with d.get(k, default)
Example: the capital of each province: capitals['Quebec'] is 'Quebec City'
If have I already seen this one, or how many DISTINCT ones → a set; test with in, add with add, count with len
Example: duplicate registrations among 20000 entries: 20000 lookups instead of 400 million comparisons
If a record that must not change, or must serve as a key → a tuple; unpack it with row, col = position
Example: a position on a grid: visited[(row, col)] = True
If several values under one key → a dictionary of lists; append through get with an empty list as default
Example: every mark of every student: marks[name] = marks.get(name, []) + [value], so 2 marks for Ana give [7.5, 8]
the value is a list, so marks[name][0] is the first mark and len(marks[name]) the number of marks
If a table with rows and columns → a list of lists built by comprehension, indexed board[row][col]
Example: a 3 by 3 board: [[' '] * 3 for r in range(3)], column 1 is [row[1] for row in board]
the first index is the ROW; a column has to be gathered from every row
If two branches apply, keep both structures: a list for the order and a set for the membership test, filled by the same loop. The marker expects the idioms written out; a library that counts for you is not the answer the question is testing.
Which list call, from what you need back
Decide first whether you need the list CHANGED or a NEW object, then whether you need a value back
If the list must grow by one element, nothing needed back → values.append(x), on its own line
Example: [1, 2] becomes [1, 2, 7] after append(7); the call returns None
If the list must grow by every element of another → values.extend(other), or values += other
If the original must stay intact → sorted(values), values + other, values[:], a comprehension: all build a new list
Example: sorted([3, 1, 2]) returns [1, 2, 3] and the original still reads [3, 1, 2]
If a copy of a list of LISTS must be independent → copy.deepcopy(values), or a comprehension that rebuilds each row
Example: [[1, 2], [3, 4]] deep copied: appending 9 to the copy's first row leaves the original at [1, 2]
The one call that is never right: assigning the result of append, sort, extend, remove or reverse. If the question asks you to return a sorted list without changing the argument, that is sorted, not sort.
How the answer is expected to be written
A marker ticks steps. Here they are in order, with the concluding sentence expected word for word.
Counting occurrences with a dictionary, as the autograder expects it
When to use it: The question says count how many times each item appears, or find the most frequent, and hands you a list or a string to split
1Create the empty dictionary BEFORE the loop: counts = {}. Inside the loop it would be reset at every item.
2One line per item, through get with 0 as default: counts[item] = counts.get(item, 0) + 1. No if, no special case for the first occurrence.
3Return the dictionary; do not print it. The autograder compares the returned value, and a printed dictionary is worth nothing to it.
4If the order matters, sort OUTSIDE the dictionary: sorted(counts.items(), key=lambda pair: pair[1], reverse=True) returns a list of (item, count) tuples, and the top three is a slice [:3] of that list.
5Make the order explicit on ties: key=lambda pair: (-pair[1], pair[0]) ranks by decreasing count, then alphabetically.
Concluding sentence
“counts = {} then for word in words: counts[word] = counts.get(word, 0) + 1, and return counts. On 'the cat sat on the mat the end', counts['the'] is 3 and the dictionary has 6 entries.”
The trap: Writing counts[word] = counts[word] + 1: the first word of the text raises KeyError, and nothing after it runs.
Marking: Typically 1 mark for the structure, 2 for the loop, 1 for the return, 1 for the sort when it is asked.
Building a table and reading it by row and by column
When to use it: The question describes a board, a grid of marks, a matrix, anything with rows AND columns
1Build the empty table by comprehension: grid = [[0] * cols for r in range(rows)]. Say in one clause why: each row is created separately.
2Name the convention: grid[row][col], the first index is the row. Read a value as grid[1][2], row 1, column 2.
3Walk a row with for square in grid[r]; gather a column with [row[c] for row in grid], because a column lives in every row.
4Count over the whole table with a nested loop, outer loop on rows, inner loop on columns, or the flat comprehension sum([1 for row in grid for x in row if x == 0]).
5Print with a loop over rows, one line per row: for row in grid: print(' '.join(row)). print(grid) shows the Python literal, which is not a table.
Concluding sentence
“grid = [[0] * 3 for r in range(3)] builds three distinct rows; grid[1][2] is row 1, column 2; column 1 is [row[1] for row in grid].”
The trap: Reading grid[col][row]: the two indices are swapped, and on a square board no error tells you.
Check before you hand in
Five minutes of checking recover more marks than one more problem started in a hurry.
Search your code for an equals sign before a mutating call
Scan every line for = followed by .append(, .sort(, .extend(, .remove( or .reverse(. Each one stores None. The fix is to delete the left-hand side and the equals sign, nothing else.
names = names.sort() leaves names equal to None; the next len(names) raises TypeError, object of type NoneType has no len.
Print len just after the line that grows the list
After an append or an extend, print len(values) once. Grown by exactly 1 after append, by the length of the argument after extend. Any other number says a list was appended as one element.
A list that should hold 10 numbers and reports len 6 was built with append([a, b]) five times: it holds five lists and one number.
Change the copy, print the original
Three lines: b = your copy, then change something INSIDE b, then print a. If a changed, the copy was shallow and the inner objects are shared. Do it on the smallest example you can type.
a = [[1], [2]], b = a[:], b[0].append(9), print(a) shows [[1, 9], [2]]: the slice did not copy the second level.
Say the key's type out loud
Before writing d[something] = value, name the type of something. A string, a number or a tuple of those is fine. A list, or a tuple that contains a list, will raise TypeError, unhashable type.
d[[row, col]] is refused; d[(row, col)] is accepted, and d[position] works when position was built as a tuple.
No del or append inside a loop over the same object
Read the body of every for loop. If it deletes from or appends to the object being walked, rewrite it: collect first into a new list, then act; or build the result by comprehension.
for k in d: del d[k] raises RuntimeError on the first deletion; for x in values: values.remove(x) skips every second element without any error.
The typical problem, taken apart
A robot on a grid: four structures for one walk
A robot starts at cell (0, 0) of a 3 by 3 grid and follows the string moves = 'RDLURD', one letter per step: R adds 1 to the column, L subtracts 1, D adds 1 to the row, U subtracts 1.
Write path(moves), which returns the list of the cells visited in order, the start included; visits(path), which returns how many times each cell was visited; and from those, the number of distinct cells and the cells visited more than once. State the structure chosen for each question and why.
Six moves, four cells: the two doubled arrows are the R and the D taken twice, so the walk comes back on cells it already visited, which is what the questions are about.
python
def path(moves):
row, col = 0, 0
cells = [(row, col)]
for m in moves:
if m == 'R':
col = col + 1
elif m == 'L':
col = col - 1
elif m == 'D':
row = row + 1
elif m == 'U':
row = row - 1
cells.append((row, col))
return cells
def visits(cells):
counts = {}
for cell in cells:
counts[cell] = counts.get(cell, 0) + 1
return counts
walk = path('RDLURD')
counts = visits(walk)
distinct = len(counts)
repeated = [cell for cell in counts if counts[cell] > 1]
Step 1
Choose the structures before the loop. The order of the cells is asked, so the path is a LIST. A cell is a pair that must not change and will serve as a key, so it is a TUPLE (row, col). A count per cell is a DICTIONARY keyed by the tuple. Distinct cells is a SET question, and the dictionary's keys already are one.
Why
This is the sentence the marker reads first. Writing a cell as [row, col] would crash at the first counts[cell], and writing the path as a set would lose the order and the repeats the questions need.
Step 2
Build the path with an accumulator that starts with the start cell: cells = [(0, 0)], then one append per move, of a NEW tuple built from the updated row and col. path('RDLURD') returns [(0, 0), (0, 1), (1, 1), (1, 0), (0, 0), (0, 1), (1, 1)], 7 cells for 6 moves.
Why
The append is a statement on its own line, never cells = cells.append(...). Seven cells for six moves is the off-by-one to state: the start counts, the loop adds one cell per letter.
Step 3
Count with the get idiom: counts = {} before the loop, counts[cell] = counts.get(cell, 0) + 1 inside. The result is {(0, 0): 2, (0, 1): 2, (1, 1): 2, (1, 0): 1}.
Why
get supplies the 0 the first time a cell is seen; brackets would raise KeyError on (0, 0) at the very first step. The tuple key is what makes this line legal.
Step 4
Distinct cells: len(counts), which is 4. The same answer comes from len(set(walk)), since a set drops the three repeats of the 7 cells.
Why
A dictionary's keys are unique by construction, so counting them IS the distinct count: no second structure is needed. Naming the set version shows the marker you know which question a set answers.
Step 5
Cells visited more than once: [cell for cell in counts if counts[cell] > 1], which gives [(0, 0), (0, 1), (1, 1)], 3 cells. The comprehension reads the dictionary and writes into a new list.
Why
Never del the once-visited cells inside for cell in counts: the dictionary would change size under the loop and raise RuntimeError. Reading while iterating is fine, writing is not.
Step 6
Check on the figure: 7 cells in the path, and the counts add up to 7, 2 + 2 + 2 + 1. The cell (1, 0) is the only one with a single arrow going in, so it is the only one visited once.
Why
sum(counts.values()) must equal len(walk): a mismatch means a cell was appended before its coordinates were updated, or the start was forgotten.
The conclusion, written out
“The path is a list of tuples, [(0, 0), (0, 1), (1, 1), (1, 0), (0, 0), (0, 1), (1, 1)]; the visits are a dictionary keyed by tuple, {(0, 0): 2, (0, 1): 2, (1, 1): 2, (1, 0): 1}; 4 distinct cells; 3 cells visited more than once, listed by a comprehension over the dictionary.”
The classic mistake on this problem: Writing cells.append([row, col]) with square brackets: the path looks right when printed, and visits crashes with TypeError, unhashable type: list, on the first cell.
Learn by heart
•append, extend, insert, remove, sort, reverse CHANGE the list and return None; pop returns the element it removes; sorted, + and a slice build a NEW list.
•remove takes a VALUE; del values[i] and values.pop(i) take a POSITION; index raises when the value is absent, so test in first.
•b = a is one list with two names; a[:], list(a) and a.copy() copy the outer level only; copy.deepcopy(a) copies every level.
•A grid is [[0] * cols for r in range(rows)], never [[0] * cols] * rows; it is read grid[row][col], the first index is the ROW.
•d[k] raises KeyError on an absent key; d.get(k, default) never raises; counting is counts[w] = counts.get(w, 0) + 1.
•Iterating a dictionary gives its KEYS in insertion order; .items() gives the pairs; never delete from or add to a structure while iterating over it.
•A key must be immutable: a tuple yes, a list no. Membership in a set costs one lookup; membership in a list is a scan. A tuple of one element is (5,).
Frequently asked questions
Why does my list become None after append in Python?
Because append changes the list in place and returns None, and you stored that None. Write values.append(x) alone on its line, without values equals in front of it, then keep using values. The same holds for sort, extend, insert, remove and reverse. Only pop gives something back, the element it removed, and sorted gives a new sorted list without touching the original.
How do I count how many times each word appears in a list in Python?
Create an empty dictionary before the loop, then for each word write counts of word equals counts dot get of word and 0, plus 1. The get call returns 0 the first time a word is seen, so no if is needed. Return the dictionary at the end. To rank the words, call sorted on counts dot items with a key that reads the count and reverse set to True, which gives a list of pairs.
What is the difference between a shallow copy and a deep copy in Python?
A shallow copy, made by a slice, list of a, or a dot copy, creates a new outer list that still points at the same inner objects. For a list of numbers that is enough, since a number cannot be changed in place. For a list of lists, changing an inner list through the copy changes the original too. A deep copy, copy dot deepcopy of a, rebuilds every level, so nothing is shared.
When should I use a set instead of a list in Python?
When the question you keep asking is whether an element has already been seen, or how many distinct elements there are. Testing membership in a set costs the same whatever its size, while testing it in a list scans the whole list, which becomes millions of comparisons inside a loop. Use a list when the order or the position matters, or when duplicates must be kept.
Why can a list not be a dictionary key in Python?
A dictionary computes where to store a value from the key itself, so the key must never change afterwards. A list can be changed in place, so Python refuses it with TypeError, unhashable type: list. Use a tuple instead, for example the pair row comma col in parentheses, which cannot change and works as a key. A tuple that contains a list is refused for the same reason.
Practise it
Corrected exercises: Lists, dictionaries and the structure to choose, COMP 202
A method is proved on a paper, not on a sheet. The set for the same chapter takes each of these traps into a problem, with the solution written out step by step.
I tutor COMP 202 at McGill in English or in French, in person in Montreal or online. Get in touch for a first session and we go through the data structures questions of a past midterm together.
