Nested lists and copies

Picture a movie theater. It has several rows, and each row has several seats. To find your place, you first look for the row and then for the seat in that row.

A table—seats in a hall, cells of a game board—is stored in Python the same way. It is a list of rows, where each row is a list too. Such a list is called a nested list:

grid = [[1, 2, 3], [4, 5, 6]]
print(len(grid), len(grid[0]))  # 2 3
print(grid[1])  # [4, 5, 6]
print(grid[1][0])  # 4
grid[0][2] = 9
print(grid)  # [[1, 2, 9], [4, 5, 6]]

Let's go through it line by line:

1. len(grid) is the number of rows, 2, and len(grid[0]) is the number of seats in the first row, 3.
2. grid[1] gives the whole second row: [4, 5, 6].
3. grid[1][0] reads from left to right: first the second row, then the first seat in it—4.
4. grid[0][2] = 9 finds the first row the same way and replaces its third element.

Going over it with two loops

To go over every seat in the hall, you need two loops, one inside the other. The outer loop goes over the rows, and the inner one goes over the seats of the current row:

grid = [[1, 2, 3], [4, 5, 6]]
total = 0
for row in grid:
    for x in row:
        print(x, end=" ")  # 1 2 3 4 5 6
        total += x
print()
print(total)  # 21

Let's see in what order the loops run:

1. The outer loop takes the first row, [1, 2, 3], and binds the name row to it.
2. The inner loop goes through that whole row: it prints 1 2 3 and adds each number to total.
3. The outer loop takes the second row, and the inner one again goes through it from start to end: 4 5 6.
4. After both loops, print() ends the line, and the last print outputs the sum of all the numbers—21.

The body of the inner loop ran six times: three times for each of the two rows. That is how any table is traversed: row by row, and within a row from left to right.

Shallow and deep copies

a[:], list(a) and a.copy() copy only the outer list. For a table, this means the copy shares its rows with the original. The line import copy brings in a set of copying functions, as import math brings in math ones. Copies come in two kinds.

Shallow copy

A shallow copy is a new outer list holding the very same rows as the original. copy.copy(grid) makes one, and so do all three ways above. Picture a second entrance to the same hall: the door is new, but the rows behind it are the old ones.

Deep copy

copy.deepcopy(grid) makes a deep copy: both the outer list and all the nested ones are copied in it. It is a second hall built to the same plan, with its own rows and seats.

import copy

grid = [[1, 2], [3, 4]]
shallow = copy.copy(grid)
deep = copy.deepcopy(grid)
grid[0][0] = 9
print(shallow[0], deep[0])  # [9, 2] [1, 2]
print(shallow[0] is grid[0])  # True

Let's see what changed after grid[0][0] = 9:

• in the shallow copy the first row is the same list as grid[0], so it shows [9, 2];
• shallow[0] is grid[0] gives True: it is one object;
• the deep copy has its own rows, and it still holds [1, 2].

A deep copy is needed when the elements of the copy's rows will change. If only the outer list changes—whole rows are added or removed—a shallow copy is enough.

Interviewers like to ask this: "How does a shallow copy differ from a deep one?" The answer is whether the nested objects are copied. A shallow copy shares them with the original, and a deep copy creates its own.

Common mistake

It is tempting to build a table of zeros in one line. The * operator repeats the elements of a list: [0] * 3 is [0, 0, 0]. If you multiply the outer list the same way, the rows turn out to be one object:

grid = [[0] * 3] * 2  # ✗
grid[0][0] = 5
print(grid)  # [[5, 0, 0], [5, 0, 0]]

grid = []
for i in range(2):
    grid.append([0] * 3)  # ✓
grid[0][0] = 5
print(grid)  # [[5, 0, 0], [0, 0, 0]]

The outer * 2 repeats a reference to the row, not the row: grid has two elements, and both are the same list. It is like two entrances to a hall with only one row. That is why a change through grid[0] also shows in grid[1].

The inner [0] * 3 is safe: numbers cannot be changed, and grid[0][0] = 5 replaces one element of the row with a new object.

The fix is in the second part of the example: the rows are created with a loop. On each iteration the expression [0] * 3 is evaluated again and builds a new row list. Then append adds it to the outer list. The variable i is not used in the body: it is there only so the body runs twice.

Key points

• A table is stored as a list of lists: grid[1][0] is the second row, first element.
• Two nested loops go over a table row by row, and within a row from left to right.
• A shallow copy shares its rows with the original, and copy.deepcopy copies them too.
• [[0] * 3] * 2 repeats one and the same row, so rows are created with a loop.