Lists, tuples, dicts and sets · about 45 min

Lists

Why this matters

Real programs work with many values at once: the lines of a file, the scores in a game, the rows of a spreadsheet, the results of a search. The list is Python's general-purpose ordered collection and by far its most used data structure. In this lesson you will learn to create and manipulate lists, and also what a list looks like in memory, which explains why some operations are instant and others get slow as lists grow.

Creating lists and indexing

A list is written with square brackets, items separated by commas. Items can be of any type, even mixed:

primes = [2, 3, 5, 7, 11]
names = ["Ada", "Grace", "Linus"]
mixed = [1, "two", 3.0, None]
empty = []
print(len(primes), primes)

5 [2, 3, 5, 7, 11]

Lists are sequences, like strings, so everything you learned about string indexing and slicing carries over:

print(primes[0])     # first: 2
print(primes[-1])    # last: 11
print(primes[1:3])   # slice: [3, 5]
print(primes[::-1])  # reversed copy: [11, 7, 5, 3, 2]
print(7 in primes)   # membership: True

An index out of range raises IndexError: list index out of range. Slices never raise; they just give fewer items.

The big difference from strings: lists are mutable. You can change them in place.

primes[0] = 1        # replace an item
print(primes)
del primes[0]        # delete an item
print(primes)

[1, 3, 5, 7, 11]
[3, 5, 7, 11]

Essential list methods

Methods are called on the list with a dot. Most mutate the list and return None:

Method	Effect
`lst.append(x)`	add `x` at the end
`lst.extend(other)`	add every item of `other` at the end
`lst.insert(i, x)`	insert `x` before index `i`
`lst.pop()` / `lst.pop(i)`	remove and return the last item / item `i`
`lst.remove(x)`	remove the first item equal to `x` (`ValueError` if absent)
`lst.index(x)`	position of the first item equal to `x`
`lst.count(x)`	how many items equal `x`
`lst.sort()`	sort in place (returns `None`)
`lst.reverse()`	reverse in place (returns `None`)
`lst.clear()`	remove everything

todo = ["write", "test"]
todo.append("ship")
todo.insert(0, "plan")
print(todo)
done = todo.pop(0)
print(done, todo)
todo.extend(["celebrate", "rest"])
print(todo)

['plan', 'write', 'test', 'ship']
plan ['write', 'test', 'ship']
['write', 'test', 'ship', 'celebrate', 'rest']

Note the difference between append and extend: todo.append(["a", "b"]) adds one item, which is itself a list.

Operators also work: a + b makes a new list joining both, a * 3 repeats, and a += b extends a in place.

Useful built-in functions take a list as argument: len, sum, min, max, and sorted, which returns a new sorted list and leaves the original alone:

scores = [70, 95, 82]
print(sorted(scores), scores)
print(sorted(scores, reverse=True))
scores.sort()
print(scores)

[70, 82, 95] [70, 95, 82]
[95, 82, 70]
[70, 82, 95]

Building lists with loops

A very common pattern: start empty, loop, append.

squares = []
for n in range(1, 6):
    squares.append(n * n)
print(squares)

words = "the quick brown fox".split()
lengths = []
for w in words:
    lengths.append(len(w))
print(words, lengths)

[1, 4, 9, 16, 25]
['the', 'quick', 'brown', 'fox'] [3, 5, 5, 3]

str.split() returns a list of strings, and "-".join(list_of_strings) turns a list back into a string. The iteration module will show a shorter way to build lists, called comprehensions.

What a list is underneath

A Python list is a dynamic array of references. The list object holds a pointer to a contiguous block of memory containing one pointer per item. The items themselves are separate objects elsewhere in memory:

 primes ---> list object
             +------------------+
             | size = 4         |
             | allocated = 4    |
             | items ---------------> [ ptr | ptr | ptr | ptr ]
             +------------------+        |     |     |     |
                                         v     v     v     v
                                        int3  int5  int7  int11

Three consequences follow.

Indexing is fast, whatever the size. To get lst[i], CPython computes start + i * 8 (8 bytes per pointer on a 64-bit machine) and follows that pointer. lst[0] and lst[999999] take the same time. In complexity terms, indexing is O(1), constant time.

Appending is fast on average. CPython over-allocates: when the block is full, it allocates a bigger one (roughly 12.5% larger plus a little), copies the pointers over, and frees the old block. Most appends find a free slot and just write one pointer; the occasional resize copies everything. Averaged over many appends, the cost per append is constant ("amortized O(1)"). You can watch the over-allocation:

import sys
lst = []
for i in range(10):
    print(len(lst), sys.getsizeof(lst))
    lst.append(i)

On 64-bit CPython 3.13, the size in bytes jumps only occasionally (56, 88, 88, 88, 88, 120, ...), each jump making room for several more items.

Inserting or deleting near the front is slow for big lists. lst.insert(0, x) and lst.pop(0) must shift every following pointer one slot over, so their cost grows with the length of the list (O(n)). For a list of 10 items you will never notice; for a million items in a loop, you will. If you need fast adds and removes at both ends, the standard library offers collections.deque (covered in module 10).

Likewise x in lst, lst.index(x), lst.remove(x) and lst.count(x) must look at items one by one: O(n). When you need fast membership tests on many items, use a set (lesson 4).

Operation	Cost
`lst[i]`, `lst[i] = x`, `len(lst)`	O(1)
`lst.append(x)`, `lst.pop()`	O(1) amortized
`lst.insert(0, x)`, `lst.pop(0)`	O(n)
`x in lst`, `lst.remove(x)`	O(n)
`lst.sort()`	O(n log n)

Because a list stores references, putting an object in a list does not copy it. Lesson 5 explores what that means when the object is mutable.

Common mistakes

Assigning the result of a mutating method: lst = lst.sort() or lst = lst.append(x) sets lst to None. Then lst[0] gives TypeError: 'NoneType' object is not subscriptable.
Off-by-one indexing: the last index is len(lst) - 1; lst[len(lst)] is an IndexError. Use lst[-1].
remove of a missing value: ValueError: list.remove(x): x not in list. Check with in first if it might be absent.
Modifying a list while looping over it: removing items inside for item in lst: skips elements, because positions shift under the loop. Build a new list instead.
Confusing append and extend, ending up with a list nested inside a list.

Recap

Lists are ordered, mutable sequences: [a, b, c]. Indexing and slicing work as for strings.
Mutating methods (append, insert, pop, remove, sort, ...) change the list and mostly return None; sorted() returns a new list.
A list is a dynamic array of references: indexing and appending are fast, inserting at the front and searching are proportional to length.

Going further: read "More on Lists" in the official tutorial (section 5.1). Then time lst.insert(0, x) versus lst.append(x) for 100,000 items using import time; t = time.perf_counter() before and after.

Exercises

Exercise 1 · quiz

Predict the list

What does this print?

nums = [3, 1, 4]
nums.append(1)
nums.insert(0, 5)
nums.pop()
print(nums)

[5, 3, 1, 4]
[3, 1, 4, 1, 5]
[5, 3, 1, 4, 1]
[3, 1, 4]

Answer

[5, 3, 1, 4]

append(1) gives [3, 1, 4, 1]; insert(0, 5) puts 5 at index 0: [5, 3, 1, 4, 1]; pop() with no argument removes and returns the last item, leaving [5, 3, 1, 4].

Exercise 2 · quiz

sort versus sorted

What does this print?

scores = [70, 95, 82]
result = scores.sort()
print(result, scores)

[70, 82, 95] [70, 82, 95]
None [70, 82, 95]
[70, 82, 95] [70, 95, 82]
None [70, 95, 82]

Answer

None [70, 82, 95]

list.sort() sorts the list in place and returns None, a Python convention for methods that mutate. sorted(scores) would instead return a new sorted list and leave scores unchanged. Writing scores = scores.sort() is a classic bug that replaces your list with None.

Exercise 3 · write code

Read numbers into a list

The input is a series of lines, each containing one integer, ending with a line containing only end. Read them into a list and print, on separate lines:

count: <how many numbers>
max: <largest>
min: <smallest>
middle: <the middle element of the numbers sorted ascending>

There is always at least one number, and the count is always odd, so the middle is well defined: for sorted list s it is s[len(s) // 2]. For input 5 2 9 end (one per line):

count: 3
max: 9
min: 2
middle: 5

File: main.py

Starting point

numbers = []
line = input()
while line != "end":
    line = input()

Example

input

5
2
9
end

expected output

count: 3
max: 9
min: 2
middle: 5

Example

input

-4
end

expected output

count: 1
max: -4
min: -4
middle: -4

Hint 1

Inside the loop, numbers.append(int(line)) before reading the next line.

Hint 2

max(numbers), min(numbers), len(numbers) and sorted(numbers) are all built in.

Reference solution

numbers = []
line = input()
while line != "end":
    numbers.append(int(line))
    line = input()
s = sorted(numbers)
print("count:", len(numbers))
print("max:", max(numbers))
print("min:", min(numbers))
print("middle:", s[len(s) // 2])

Exercise 4 · write code

Rotate with slices

Define rotate(items, k) that returns a new list with the elements of items rotated left by k positions, leaving items unchanged:

rotate([1, 2, 3, 4, 5], 2) returns [3, 4, 5, 1, 2]
rotate([1, 2, 3], 0) returns [1, 2, 3]
rotate([1, 2, 3], 4) returns [2, 3, 1] (k larger than the length wraps around)
rotate([], 3) returns []

Use slicing and +; no loops needed.

File: solution.py

Starting point

def rotate(items, k):
    return items

Hint 1

items[k:] is everything from index k on; items[:k] is everything before it.

Hint 2

Reduce k first with k % len(items), but guard the empty list (modulo by zero is an error).

Reference solution

def rotate(items, k):
    """Return a new list: items rotated left by k positions."""
    if not items:
        return []
    k = k % len(items)
    return items[k:] + items[:k]

Exercise 5 · write code

Remove duplicates, keep order

Define unique(items) that returns a new list with duplicates removed, keeping the first occurrence of each value in its original position:

unique([3, 1, 3, 2, 1]) returns [3, 1, 2]
unique(["b", "a", "b"]) returns ["b", "a"]
unique([]) returns []

Use a loop, a result list, and the in operator.

File: solution.py

Starting point

def unique(items):
    result = []
    return result

Hint 1

Loop over items; append each one to result only if it is not already there.

Hint 2

if item not in result: result.append(item)

Reference solution

def unique(items):
    """Return items without duplicates, keeping first occurrences in order."""
    result = []
    for item in items:
        if item not in result:
            result.append(item)
    return result