Lists: Holding Many Things at Once

4.1One name, many values

So far every variable held one thing. A list holds many, in order, under one name — written in square brackets, separated by commas.

grades = [72, 88, 45, 91, 63]
students = ["Ada", "Bilal", "Cem", "Dilek"]
mixed = ["Ada", 72, True]        # allowed, but rarely a good idea

print(grades)
print(len(grades))               # how many items

Items are numbered from zero. The last item is at position len(list) - 1, or more conveniently at -1.

print(students[0])     # Ada     — the first
print(students[2])     # Cem     — the third
print(students[-1])    # Dilek   — the last
print(students[1:3])   # ['Bilal', 'Cem'] — a slice, stops before 3

Asking for students[9] in a four-item list gives IndexError: list index out of range — "there is no tenth shelf" (index 9).

4.2Changing a list

queue = []                     # start empty

queue.append("Ada")            # add to the end
queue.append("Bilal")
queue.append("Cem")
print(queue)

queue[1] = "Burak"             # replace an item
last = queue.pop()             # take the last one off

print(queue, "| removed:", last)

append and pop work at the end of the list, which turns out to be the cheap end. There are also insert(0, x) and pop(0) for the front, and those are quietly expensive — week 10 measures exactly how expensive, and the answer is worse than most people expect.

4.3Looping over a list

grades = [72, 88, 45, 91, 63]

total = 0
passed = 0
best = grades[0]

for g in grades:
    total = total + g
    if g >= 60:
        passed = passed + 1
    if g > best:
        best = g

print(f"average {total / len(grades):.1f}, passed {passed}, best {best}")

One pass over the list answers three questions at once. And notice the shape of the cost: one visit per item. A list ten times longer takes ten times the work. Your step counter from week 3 will confirm it.

4.4Searching, and what it costs

"Is this name in my list?" Python has a short way to ask, and it is worth writing the long way first so you can see what really happens.

names = ["Ada", "Bilal", "Cem", "Dilek", "Ece"]
target = "Dilek"

found = False
looks = 0

for name in names:
    looks = looks + 1
    if name == target:
        found = True
        break                  # stop early — we found it

print(f"found: {found} after {looks} looks")

The short way does exactly the same work behind the scenes:

print("Dilek" in names)     # True
print("Zeynep" in names)    # False

This one-by-one method has a name we will use for the rest of the course: linear search. The worst case is the one we plan around, and it is the interesting one for another reason: every failed search costs a full pass. A program that checks thousands of items against a list of thousands is doing millions of comparisons — and it looks like two innocent lines of code.

4.5Building a new list from an old one

Very often you do not want to change a list in place — you want to make a new one from it: the passing grades only, each price with tax added, the names in capitals. The reliable pattern is: start with an empty list and append as you go.

grades = [72, 88, 45, 91, 63, 30]

passing = []                 # start empty
for g in grades:
    if g >= 60:
        passing.append(g)    # add the ones we want to keep

print(passing)
print(f"{len(passing)} of {len(grades)} passed")

The same shape builds a transformed list — here, each grade rounded up by 5 marks of generous marking:

grades = [72, 88, 45, 91, 63]

boosted = []
for g in grades:
    boosted.append(g + 5)

print(boosted)

Python has a compact one-line spelling for exactly this pattern, the list comprehension, which you will meet properly in the next section. Whichever spelling you use, the cost is the same and familiar: one visit per item, so a list ten times longer takes ten times the work.

4.6Making test data of any size

From next week you will need lists far too long to type. Two ways to conjure them:

import random

numbers = list(range(100000))                     # 0, 1, 2, ... 99999
squares = [x * x for x in range(10)]              # a list comprehension
shuffled = random.sample(range(100000), 100000)   # same numbers, random order

print(len(numbers), squares[:5], shuffled[:5])

The middle line is a list comprehension: "make a list of x * x for every x in this range". It is the compact Python idiom for building a list from another sequence — the same job as the append loop in §4.5, written in one line. You can add a condition too, which reads like plain English:

evens = [x for x in range(20) if x % 2 == 0]
passing = [g for g in [72, 45, 88, 30, 63] if g >= 60]

print(evens)
print(passing)

Read it left to right: the value to keep, then where the items come from, then the condition they must pass. It appears in nearly every benchmark in this course.

4.7The experiment: does searching get slower?

Run this, then change size to 10 000 and 100 000. Predict the numbers before each run and write your predictions down.

size = 1000
data = list(range(size))
target = -1                    # deliberately not in the list

looks = 0
for item in data:
    looks = looks + 1
    if item == target:
        break

print(f"list of {size}: {looks} looks for a missing item")

Ten times the data, ten times the looks — every time, no exceptions. You have just measured your first growth law with your own hands. Week 5 puts a stopwatch next to the counter, and week 6 turns the pair into a graph.

4.8Common mistakes with lists

Lists bring two surprises that catch nearly everyone, because they involve how Python shares and returns things. Meet them now.

1. Two names, one list. Writing b = a does not copy the list — it gives the same list a second name. Change it through one name and the other sees it too:

a = [1, 2, 3]
b = a                 # NOT a copy — same list, two names
b.append(4)

print("a:", a)        # a changed too!
print("b:", b)

c = a[:]              # a real copy (a full slice)
c.append(99)
print("a:", a, "c:", c)

When you genuinely want a separate list, copy it with a[:] (or list(a)). Otherwise mutations are shared while the names refer to the same list; giving one name a different object does not change what the other name refers to. A slice copies the outer list, so nested mutable objects can still be shared.

2. append changes the list and returns nothing. A very common bug is to assign its result back:

nums = [3, 1, 2]

# WRONG: append changes nums in place and hands back None
# nums = nums.append(5)   -> nums becomes None, next line crashes

nums.append(5)        # RIGHT: just call it; the list is already changed
print(nums)

Methods such as append and sort change the list in place and return None; do not replace the list name with that result. pop also changes the list, but returns the removed item, so last = queue.pop() is a valid way to save that item.

4.11Optional Studio Extension

4.12Words from this week

4.13Chapter problem set — Skiena 2.10

These are exercises from Skiena's Algorithm Design Manual, Chapter 2, matched to this week and solved step by step. Both are about the little loop you used to find a maximum or minimum — why it is correct, and how much work it really does.

m = A[0]                       # current champion
for i in range(1, len(A)):
    if A[i] > m:
        m = A[i]               # a bigger value dethrones it
print(m)                       # claim: this is the maximum

tmp = A[0]
assignments = 0
for i in range(1, len(A)):
    if A[i] < tmp:
        tmp = A[i]                 # how often does THIS line run?
        assignments = assignments + 1
print(tmp, "updated", assignments, "times")