Sequences 0/2

Lesson 12 of 21

Lists and sequences

Hold many values in one list, walk through them, slice them and process them in a single line.

Part 1 of 9 Lists

Many values under one name

A weather station records the temperature at noon every day: 18, 21, 19, 24, 22, 17 and 20 in its first week. Seven numbers fit in seven names, mon to sun. A year gives 365, and a judge problem can give 100,000. Writing 100,000 names is impractical, and a loop cannot step from mon to tue.

Python keeps the week in order as one value, a list: temps = [18, 21, 19, 24, 22, 17, 20]. Each value inside is an element, and its position is its index, counted from 0. A list is a sequence, like the strings and tuples that come later, and most of what this lesson does with lists works on every sequence.

Writing a list and selecting by index

You write a list as its elements between square brackets, separated by commas. Square brackets after the name select one element by its index:

Sign up to run
nums = [3, 8, 1, 6]
print(nums[0])
print(nums[3])
print(len(nums))
nums[1] = 5
print(nums)
print(nums + [2, 7])
print([0] * 3)
Python details

A list can hold values of different types. nums.append(x) adds an element at the end, nums.pop() removes the last one, del nums[i] removes the one at index i, and nums.remove(x) removes the first element equal to x.

nums[0] is the first element, 3, and nums[3] is the fourth, 6. len(nums) gives the length, 4. nums[1] = 5 replaces the 8 at index 1 and leaves the other elements alone.

+ between two lists makes a new list with the elements of the first followed by those of the second, and * with a number repeats the elements. Neither changes nums.

Definition

A sequence is an ordered collection of values with a finite length. Each element is selected by its index, a whole number from 0 to the length minus one.

nums after the change: four elements at indexes 0 to 3
Index0123
Element3516

An index counts the elements before it: none before the first, three before the fourth. So the last index is one less than the length:

last index=length−1=4−1=3\text{last index} = \text{length} - 1 = 4 - 1 = 3

There is no element at index 4, so nums[4] stops with IndexError. A negative index counts from the end and stands for the length plus that number: nums[-1] is nums[4 - 1], the last element 6, and nums[-4] is the first, 3. nums[-5] is out of range too.

Selecting by index takes one step however long the list is. A list keeps its elements in a row of equal-sized slots in memory, so Python finds nums[i] with one calculation, the start of the list plus ii times the size of one slot, and reading nums[99999] takes as long as reading nums[0]. Adding or removing at the end is also quick on average. Inserting or removing at the front is slow, because every other element shifts one place: on a list of 10510^5 elements, one nums.insert(0, x) or nums.pop(0) makes about 10510^5 moves.

Nested lists and grids

An element can be any value, including another list. A grid of numbers is usually stored as a list of its rows.

Sign up to run
grid = [[1, 2, 3], [4, 5, 6]]
print(grid[1])
print(grid[1][0])
print(len(grid), len(grid[0]))

grid[1][0] is two selections, read from the left: grid[1] is the second row, [4, 5, 6], and [0] selects its first element, 4. len(grid) counts the rows and len(grid[0]) the elements of one row.

Deeper read: copying a list or a vector

b = a does not copy a list. It gives the same list a second name, so a change made through b shows through a:

Sign up to run
a = [1, 2, 3]
b = a
b[0] = 99
print(a)

To copy a list, write b = a.copy() or b = a[:], a slice.