Lists (1D and 2D)

Earlier modules stored one value at a time, or read one value at a time from a fixed-length line. Many CCC problems instead need to hold many values together, in the order they arrived, so a program can look back at any of them later. This lesson covers Python's list, and the built-in functions that summarize and rearrange one.

Building a list

A list literal holds several values together, written between square brackets and separated by commas, such as [10, 20, 30]. .append() grows a list one value at a time, adding a new value onto the end.

1n = int(input())2scores = []3for i in range(n):4    scores.append(int(input()))5print(scores)

3
10
20
30

[10, 20, 30]

scores starts as an empty list, [], then each pass through the loop appends one more number read from input. After the loop, scores holds every number in the order it was read, ready to use as a whole.

A list comprehensionlist comprehensionA one-line way to build a list from an existing sequence, written [expression for name in sequence], optionally filtered with if.In the glossary builds a list in one line instead, written [expression for name in sequence].

1nums = [int(x) for x in input().split()]2print(nums)3evens = [x for x in nums if x % 2 == 0]4print(evens)

3 4 7 8 9

[3, 4, 7, 8, 9]
[4, 8]

[int(x) for x in input().split()] converts every piece from .split() into a number, all in one line, the same result build_with_append.py took a whole loop to reach. Adding if x % 2 == 0 at the end of a comprehension keeps only the values that pass that condition, building evens from just the even numbers in nums.

Summarizing a list

sum() adds up every value in a list. A generator expressiongenerator expressionThe same shape as a list comprehension without square brackets, producing values one at a time instead of building a whole list.In the glossary has the same shape as a list comprehension, without the square brackets, and can be passed directly to a function like sum(), any() or all() without building a separate list first.

1nums = [int(x) for x in input().split()]2print(sum(nums))3print(sum(x for x in nums if x > 0))4print(any(x < 0 for x in nums))5print(all(x > 0 for x in nums))

3 -2 5 -1

5
8
True
False

sum(nums) adds every value. sum(x for x in nums if x > 0) adds only the positive ones, using a generator expression right inside the call. any(x < 0 for x in nums) is True if at least one value matches, and all(x > 0 for x in nums) is True only if every value does.

sorted() returns a new list with the same values in order, without changing the original. reversed() visits a list back to front, and list() turns what it produces back into an actual list. enumerate() pairs each value with its position.

1nums = [int(x) for x in input().split()]2print(sorted(nums))3print(list(reversed(nums)))4for i, x in enumerate(nums):5    print(i, x)

3 1 2

[1, 2, 3]
[2, 1, 3]
0 3
1 1
2 2

sorted(nums) gives [1, 2, 3] from [3, 1, 2], smallest first. list(reversed(nums)) gives [2, 1, 3], the original order backward. enumerate(nums) hands the loop both an index and a value on every pass, without a separate counter.

zip() pairs up values from two lists by position, stopping as soon as the shorter one runs out.

1names = input().split()2scores = [int(x) for x in input().split()]3for name, score in zip(names, scores):4    print(name, score)

Ana Bo
10 20

Ana 10
Bo 20

The first line splits into two names, the second into two scores, and zip(names, scores) pairs "Ana" with 10 and "Bo" with 20, matching each name to the score at the same position.

Building a 2D grid

A 2D grid is a list of lists: an outer list of rows, where each row is itself a list of columns. grid[r][c] reads the cell at row r, column c.

1rows = 22cols = 33grid = [[0] * cols for _ in range(rows)]4grid[0][1] = 55print(grid)

[[0, 5, 0], [0, 0, 0]]

[[0] * cols for _ in range(rows)] builds rows separate row lists, each with cols zeros. Changing grid[0][1] only changes that one cell, since every row is its own independent list.

A bug to avoid: sharing one row by accident

(nothing printed yet)

[[0] * 3] * 2 looks like it builds two separate rows, but * 2 only copies the reference to the same row list twice, not the row itself. Changing grid[0][1] changes what both grid[0] and grid[1] point at, since they are the exact same list in memory.

grid = [[0] * 3 for _ in range(2)]grid[0][1] = 5print(grid)

[[0, 5, 0], [0, 0, 0]]

[[0] * 3 for _ in range(2)] runs [0] * 3 once per row, building a fresh list each time, so changing one row leaves the other alone. Whenever you build a 2D grid, use a comprehension with range() for the outer list, never * on a list that already holds a mutable row.

Slicing a list

A slice, written a_list[start:stop], pulls out a new list holding the elements from index start up to, but not including, index stop. Leaving start out means "from the beginning", and leaving stop out means "to the end", so a_list[:3] is the first three elements and a_list[2:] is everything from index 2 onward. a_list[:] with both sides left out copies the whole list.

A slice always builds a new list, even when it copies the whole thing; changing the slice afterward never touches the original. That makes slicing the safe way to hand off "a copy of these values" to another part of a program, in contrast to just writing other = a_list, which makes other a second name for the exact same list, so a change through either name shows up in both.

What lists cost as they grow

Some list operations get slower as a list grows longer: pop(0), insert(0, x), remove(), .index(), and checking x in a_list all have to shift or scan through the list's other elements. For most CCC input sizes this is not a concern, but a later module on list costs goes deeper into when it starts to matter.

Allocating slots for a 1-indexed problem

Some problems number their items starting from 1, not 0. Allocating n + 1 slots, instead of n, lets you use a problem's own numbering directly as an index.

1n = 52scores = [0] * (n + 1)3scores[3] = 104print(scores)

[0, 0, 0, 10, 0, 0]

[0] * (n + 1) gives indices 0 through n, one more than n items actually need. scores[3] stores team 3's score directly, at index 3, with no need to subtract 1 first or shift every other index to compensate.

Recap

This lesson covered building a list with a literal, .append(), and a list comprehension. It also covered summarizing a list with sum(), sorted(), reversed(), any() and all(), and pairing values with enumerate() and zip(). Last, it covered building a 2D grid safely, avoiding the shared-row bug, what a list's operations can cost as it grows, and allocating an extra slot for a 1-indexed problem. The three problems below all process several values held together in one list or grid.