Jagged lists and copying in Python

Why this matters

Real data is often uneven. One student sits three tests and another sits one. A text file has short lines and long lines. A row of Pascal's triangle is longer than the row above it. A grid where every row has the same length is convenient, but many problems do not give you one.

Copying is the other half of this lesson. Beginners often copy a list of lists, change the copy, and find that the original changed too. The cause is not a bug in Python. It is how lists are stored, and once you see it, the rule is short.

The matrix lessons of this module cover grids where every row has the same length. This lesson covers the case where the rows differ, and then the two kinds of copy that Python gives you.

Words you need first

A list of lists is a list whose items are themselves lists. The outer list holds the rows, and each row is an inner list of values.

len(marks) is the number of rows. len(marks[r]) is the number of values in row r. Those two numbers are different things, and most of the mistakes in this lesson come from mixing them up.

A jagged list is a list of lists whose rows have different lengths. The name comes from the uneven edge of a saw blade. A rectangular list is the opposite, with every row the same length.

A reference is the value that a name holds when it points at an object. Think of it as a note that gives the address of the object in memory. The object itself stays where it is. Two names with the same note both point at one object.

A copy is a new object with the same values. A shallow copy makes a new outer list but reuses the inner lists. A deep copy makes new outer and inner lists, so nothing is shared.

The idea: the outer list holds references

Each row of a list of lists is its own list object, and the outer list only holds references to them. That is why a row can be any length, and why copying a table takes more care than copying a single row.

A jagged list is simple to build in Python. You write each row with its own length, and the outer list holds them all. There is no separate step to create the rows first.

Worked example 1: a triangle of rows

Pascal's triangle is a classic example of jagged rows. Row i has i + 1 values, counting from 0. Each value is the sum of the two values above it, and the edges are always 1.

Output:

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
rows: 5
length of row 3: 4

The list comprehension [[0] * (i + 1) for i in range(5)] makes five rows, and row i gets i + 1 zeros. The next loop fills the edges with 1 and the middle values from the row above. The loop for row in triangle gives each row in turn.

len(triangle) is 5 because there are five rows. len(triangle[3]) is 4 because row 3 has four values. The two numbers answer different questions.

Worked example 2: marks with uneven rows

Now a more practical case. Each student has a list of test marks, and the lists have different lengths. One student has no marks yet, so the row is empty but still exists.

Output:

total marks: 659 over 8 tests
marks table: [[70, 85, 90], [60], [88, 92, 79, 95], []]

The loop for each student uses student, a row of its own length, so it never reads past the end of a row. The total is 245 for the first student, 60 for the second, and 354 for the third, which adds to 659. The number of tests is 3 plus 1 plus 4 plus 0, which is 8. The empty list [] is a real row with length 0. It is not None, so a loop over it runs zero times and does not fail.

Python prints the whole table with print(marks), including rows of different lengths. No special function is needed.

Worked example 3: a jagged table with a harder question

Suppose you want the length of the longest row. You cannot use one length for the whole table, so you ask each row for its own length.

Output:

longest row: 4
number of rows: 4

The loop reads the length of each row, not of the outer list. The outer list has four rows, and that number is len(marks). In this table both numbers happen to be 4, which is a coincidence and not a rule. Keeping the two lengths apart is the main skill for jagged lists.

Worked example 4: rows that arrive one at a time

Often you do not know how many rows there will be before the program starts. Lines typed by a user or read from a file are examples. A list grows as you add to it with append, so it is a good place to collect the rows.

Output:

table: [[3, 1, 4], [1, 5], [9]]
rows in list: 3
rows[0] after change: [77, 1, 4]

Here table = rows gives a second name to the same outer list, so table and rows are one list. The change to table[0][0] shows in rows[0], because they are the same row. Python lists grow directly, so the list you collect into is the table you use.

Worked example 5: a snapshot to restore

A game or an editor often needs to go back to an earlier state. Before a move, save a copy of the board, and restore from the copy if the move is undone. The board below has rows of length 3, 2 and 1, so it is jagged. Each row holds only numbers, so copying each row with a slice is a complete deep copy.

Output:

after move: [[0, 0, 0], [0, 5], [8]]
snapshot:   [[0, 0, 0], [0, 0], [0]]
restored:   [[0, 0, 0], [0, 0], [0]]

The expression row[:] makes a new list with the same values. The list comprehension applies it to each row, so every row of the snapshot is a new list. The move then changes only the board.

If the snapshot were a shallow copy, the move board[1][1] = 5 would also change the snapshot, and restoring would show the moved board. The line board = snapshot makes board a second name for the snapshot list. A later move would then change the snapshot too. If you keep playing after a restore, make a fresh copy of the snapshot first.

Copying: what = really does

Here is the first copy case. Assignment with = between two list names does not copy the list. It copies the note that points at the list.

a = [1, 2, 3]
b = a
b[0] = 99

Now a and b point at the same three boxes. Changing b[0] changes a[0] too. This short program shows it:

Output:

assignment: a = [99, 2, 3] b = [99, 2, 3]
same object? True

a is b is True because is asks whether the two names point at the same object. It does not compare the values inside them. The == operator compares values, and it is the one to use for equal contents.

Copying a list of lists

Case 1: copy copies only the outer list

Every list has a copy method that makes a new list with the same items. For a list of lists, copy makes a new outer list. The items of that new outer list are the same row objects as before. The rows themselves are not copied.

Output:

shallow changed grid: [[100, 2], [3, 4]]
same row object? True

The change to shallow[0][0] went into the row that both outer lists share, so grid shows it too. This is a shallow copy: the outer list is new, but the rows are shared. The slice grid[:] and list(grid) are also shallow copies.

Case 2: a deep copy copies each row

A deep copy makes a new list for every row as well. A list comprehension that copies each row with a slice does this.

def deep_copy(source):
    return [row[:] for row in source]

The comprehension creates a new outer list, and each row is a slice, which is a new list with the same values. Each row of the copy has the same length as the row it came from, so the function works on jagged lists without any extra code.

The main code below uses the function, then compares the copy with the original, then changes the copy.

Output:

equal: True
is: False
original: [[1, 2, 3], [4], [5, 6]]
copy:     [[100, 2, 3], [200], [5, 6]]

Two things are worth noticing. The change to the copy did not reach the original, because each row is separate. The == operator compares the contents of nested lists, so it says the two tables match. The is operator says they are different objects. The == operator checks every row, so it says the two tables match.

Case 3: the copy module

The standard library module copy has deepcopy, which copies any depth of nesting. It is the simplest choice when you are not sure how deep the structure goes.

Output:

deepcopy copy: [[1, 2, 3], [4], [5, -1]]
jagged still: [[1, 2, 3], [4], [5, 6]]

copy.deepcopy is slower than the comprehension, because it checks every object it meets. For a two-level table, the comprehension is clear and fast enough. Use deepcopy when the structure may have more levels than you expect.

Choosing a copy

The ways to copy differ in what they make new.

Use = only when you want a second name for the same data. Use copy() on a list of lists only when you know the rows will never change. Use a deep copy when the copy will change and the original must stay the same.

Case 4: a row that was never created

Python has a trap that looks like a row creation but makes every row the same object. The expression [[0, 0]] * 2 gives two references to one inner list. Changing one row changes both.

Output:

shared rows: [[0, 9], [0, 9]]
separate rows: [[0, 9], [0, 0]]

The fix is the list comprehension, which creates a new inner list on every pass.

The related case is a row that is None. Making the outer list with [None] * 2 gives two empty slots, and there is no row to write into yet. Writing into a slot that holds None fails at run time.

grid = [None] * 2
grid[0][0] = 1

Output:

Traceback (most recent call last):
  File "main.py", line 2, in <module>
    grid[0][0] = 1
    ~~~~~~~^^^
TypeError: 'NoneType' object does not support item assignment

The fix is to create the row before writing into it: grid[0] = [0, 0, 0]. The name None is Python's word for "no object here". The error says that grid[0] is None, which has no slots to assign into.

Common mistakes

1. Using the first row's length for every row. A jagged list has no single width. If the loop uses len(marks[0]) for every row, it will read past the end of a shorter row. Here is the program, run on rows of length 3 and 1:

marks = [
    [70, 85, 90],
    [60],
]
for r in range(len(marks)):
    for c in range(len(marks[0])):
        print("row", r, "col", c, "=", marks[r][c])

The output is:

row 0 col 0 = 70
row 0 col 1 = 85
row 0 col 2 = 90
row 1 col 0 = 60
Traceback (most recent call last):
  File "main.py", line 7, in <module>
    print("row", r, "col", c, "=", marks[r][c])
                                   ~~~~~~~~^^^
IndexError: list index out of range

The output shows the four values that were read before the failure. The last frame names the failing line. Row 1 has only one value, and the loop asked for column 1. The fix is to loop over len(marks[r]) for each row, or to loop over the rows directly with for row in marks.

2. Expecting a shallow copy to be a full copy. The copy changes when you change the original, or the other way round. The fix is a comprehension that copies each row, as in deep_copy. The same sharing happens when a list of rows is built with [row] * n instead of a comprehension.

3. Comparing tables with is. The operator is asks whether two names point at the same object, so two copies are never is each other. Use == to compare the contents of two tables.

4. Writing into a row before creating it. [None] * 3 is a common line, and it is easy to forget that it leaves every slot empty. Create each row first, for example with grid[r] = [0] * length, then fill it.

5. Dividing by the length of an empty row. An average is a total divided by the number of values. The row [] has length 0, so dividing by its length fails. This program computes the average of each student in the marks table from worked example 2:

marks = [
    [70, 85, 90],
    [60],
    [88, 92, 79, 95],
    [],
]
for student in marks:
    total = 0
    for m in student:
        total += m
    print("average:", total // len(student))

The output is:

average: 81
average: 60
average: 88
Traceback (most recent call last):
  File "main.py", line 11, in <module>
    print("average:", total // len(student))
                      ~~~~~~^^~~~~~~~~~~~~
ZeroDivisionError: division by zero

The first three averages are right. The // operator is floor division, which drops the decimal part, so 245 divided by 3 gives 81. The fourth row has no values, so len(student) is 0 and the division stops the program. The last line of the error text can differ by Python version, but the error type is always ZeroDivisionError. The fix is to check if len(student) == 0 before dividing and to print a message such as "no marks yet" instead.

Practice

Try each one before you read the answer. Save each program as main.py and run it with python3 main.py.

1. Given rows = [[1, 2, 3], [4], [], [5, 6]], what are len(rows), len(rows[2]), and the sum of every value in the table?

Show the answer

len(rows) is 4, because there are four rows. len(rows[2]) is 0, because row 2 is the empty list []. The sum is 21, which is 1 + 2 + 3 + 4 + 5 + 6. The empty row adds nothing, and a loop over it runs zero times.

2. Predict the output of this code.

a = [[1, 2], [3, 4]]
b = a.copy()
b[1][1] = 0
print(a[1][1])

Show the answer

The output is 0. copy makes a new outer list, but both outer lists share the row [3, 4]. Changing b[1][1] changes that shared row, so a[1][1] is also 0.

3. Predict the output of this code. It uses a deep copy made with a comprehension.

a = [[1, 2], [3, 4]]
c = [row[:] for row in a]
c[1][1] = 0
print(a[1][1])

Show the answer

The output is 4. Each row of c is a new list, so changing c[1][1] does not reach a. The original value of a[1][1] is still 4.

4. The code below raises a TypeError. Explain why, and write the line that fixes it.

grid = [None] * 3
grid[2][1] = 7

Show the answer

[None] * 3 creates three slots, and every slot is None until a row is put in it. grid[2] is None, so writing into grid[2][1] fails. The fix is to create row 2 with a length of at least 2 before writing into it: grid[2] = [0, 0]. Then grid[2][1] = 7 works.

5. Write a function total_values(table) that returns the number of values in a jagged list. Do not use a fixed width.

Show the answer

Output:

8

The loop adds the length of each row. For the marks table from worked example 2, this returns 8. Python also has a shorter form, sum(len(row) for row in table), which does the same work.

Summary

• A jagged list is a list of lists whose rows have different lengths. len(marks[r]) is the length of one row, and len(marks) is the number of rows.
• [None] * 3 creates empty slots only. Each row must be created before you write into it.
• = between two names copies the note that points at the list, not the list itself.
• copy() on a list of lists makes a shallow copy, so the rows are shared.
• A deep copy makes a new list for each row, as in [row[:] for row in table], or uses copy.deepcopy.
• Compare two tables with ==, and use is only to check whether two names point at one object.