Week 04 · Phase 1 · Thinking in steps

Lists: Holding Many Things at Once

Making lists, reading items, searching with in — and feeling work grow with size.

Big question: What happens to the work when the data gets bigger?listssearching by hand≈2.5 hours

By the end of this week you can

create lists, read items by position, and add to a list;
loop over a list to search, count and total;
build a new list from an old one, with a loop or a comprehension;
use in to ask "is this here?" and know roughly what it costs;
build test data of any size with range and random;
show, with your own step counts, that searching an unsorted list grows with its length.

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.

lists look like this

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

[72, 88, 45, 91, 63] 5

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

reading by position

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 ninth shelf".

Worth knowing already

Reading students[0] and reading students[999999] cost the computer exactly the same: it computes where the shelf is and goes straight there. Position access does not care how long the list is. Remember this in week 10, where it becomes the first row of an important table.

4.2Changing a list

the four you need

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)

['Ada', 'Bilal', 'Cem'] ['Ada', 'Burak'] | removed: Cem

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

three everyday jobs

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}")

average 71.8, passed 4, best 91

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.

Two ways to walk a list

for g in grades hands you each value in turn — use it when you only care about the items. When you also need the position, loop over range(len(grades)) and read grades[i]. You will want the position version in §4.4, where the point is precisely how far along the match was found.

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.

searching by hand, with a counter

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")

found: True after 4 looks

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

the in operator

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

Situation	Looks needed	Name for it
The item is first	1	best case
The item is somewhere in the middle	about n / 2	average case
The item is last, or missing entirely	n	worst case

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.

keep only what passes

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")

[72, 88, 91, 63] 4 of 6 passed

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

transform every item

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

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

print(boosted)

[77, 93, 50, 96, 68]

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:

data on demand

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])

100000 [0, 1, 4, 9, 16] [48213, 7, 99001, 15522, 6]

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:

comprehension with a filter

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)

[0, 2, 4, 6, 8, 10, 12, 14, 16, 18] [72, 88, 63]

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.

worst-case search, counted

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")

list of 1000: 1000 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:

the aliasing surprise

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)

a: [1, 2, 3, 4] b: [1, 2, 3, 4] a: [1, 2, 3, 4] c: [1, 2, 3, 4, 99]

When you genuinely want a separate list, copy it with a[:] (or list(a)). Otherwise the two names move together forever.

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

append returns None

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)

[3, 1, 2, 5]

The rule: methods that change a list (append, sort, pop when you ignore its result) do their work in place. Do not reassign the variable from them.

Mistake	Symptom	Fix
`b = a` then editing `b`	The other list changes too	Copy with `a[:]` or `list(a)`.
`x = mylist.append(v)`	`x` is `None`	Write `mylist.append(v)` on its own line.
Index past the end	`IndexError`	Valid positions run 0 to `len(list) - 1`.

4.9Try it yourself

Task 1 — basic statistics, by hand

Given [12, 7, 30, 4, 18], compute the total, average, largest and smallest using a single loop and no built-in functions except len.

Solution

stats.py

data = [12, 7, 30, 4, 18]
total = 0
biggest = data[0]
smallest = data[0]

for x in data:
    total = total + x
    if x > biggest:
        biggest = x
    if x < smallest:
        smallest = x

print(total, total / len(data), biggest, smallest)

One pass, four answers — and the cost is one visit per item however long the list is.

Task 2 — count the misses

Build data = list(range(10000)). Search for 20 different values that are all missing, adding up the total looks. How many comparisons did those 20 innocent-looking searches cost?

Answer

200 000. Twenty searches × 10 000 looks. Now imagine 10 000 searches over 10 000 items: 100 million comparisons — a nested loop in disguise. Week 11 shows how to make this same job almost free.

Task 3 — duplicates the obvious way

Write code that reports whether a list contains any repeated value, comparing every item with every later item. Count the comparisons for lists of 100, 200 and 400 random numbers.

Solution and what to notice

duplicates.py

import random
data = random.sample(range(1000000), 400)

comparisons = 0
found = False
for i in range(len(data)):
    for j in range(i + 1, len(data)):
        comparisons = comparisons + 1
        if data[i] == data[j]:
            found = True

print(found, comparisons)

About 4 950, 19 900 and 79 800 comparisons. Doubling the list roughly quadruples the work — the nested-loop signature from week 3, now on real data.

Task 4 — two ways to keep the evens

From list(range(20)), build a list of just the even numbers twice: once with an empty list and an append loop, once with a one-line comprehension. Confirm both lists are equal.

Solution

two_ways.py

data = list(range(20))

loop_way = []
for x in data:
    if x % 2 == 0:
        loop_way.append(x)

comp_way = [x for x in data if x % 2 == 0]

print(loop_way == comp_way)   # True — same result
print(comp_way)

True [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

Same answer, same cost (one visit per item) — the comprehension is just the compact spelling.

Task 5 — where was it found?

Write a linear search over ["Ada", "Bilal", "Cem", "Dilek", "Ece"] that returns the position of a target, or -1 if it is missing. Report the position and the number of looks for a first item, a last item, and a missing one.

Solution

find_position.py

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

position = -1
looks = 0
for i in range(len(names)):
    looks = looks + 1
    if names[i] == target:
        position = i
        break

print(f"position {position}, {looks} looks")

position 3, 4 looks

A first item costs 1 look (best case), a last or missing item costs 5 (worst case) — the three rows of the §4.4 table, measured directly.

Task 6 — spot the aliasing bug

This code should leave original untouched while building a doubled copy, but it corrupts original. Explain why, then fix it with a one-character change.

buggy.py

original = [1, 2, 3]
copy = original
for i in range(len(copy)):
    copy[i] = copy[i] * 2
print("original:", original)   # [2, 4, 6] — wrong!

Show the answer

copy = original makes a second name for the same list, so editing copy edits original. Take a real copy with a slice:

fixed.py

copy = original[:]      # the [:] makes a separate list

Now the loop changes only copy, and original stays [1, 2, 3].

4.10Self-check

colours = ["red", "green", "blue"]. What is colours[1]?

Counting starts at zero, so position 1 is the second item.

Searching an unsorted list of 1 000 items for something that is not there costs about:

A miss is the worst case: you cannot conclude "not here" until you have checked every item.

Which pair of operations costs the same no matter how long the list is?

Position access jumps straight to the shelf; the length of the list is irrelevant. The other pairs differ wildly.

After b = a where a = [1, 2, 3], you run b.append(4). What is a?

b = a does not copy; both names point at one list, so appending through b is visible through a. Use a[:] for a real copy.

What does [x * x for x in range(4)] produce?

range(4) gives 0, 1, 2, 3, and the comprehension squares each: 0, 1, 4, 9.

4.11Homework

Due before week 5

Create AA_Week04.ipynb and solve Tasks 1–6.
Run the §4.7 experiment for sizes 1 000, 10 000, 100 000 and 1 000 000. Record the looks in a table.
Repeat the experiment searching for an item that is first in the list. Put both columns in the same table.
Build a list of the first 50 square numbers two ways — an append loop and a comprehension — and confirm with == that they match.
Write five sentences: what does the gap between the best-case and worst-case columns tell you about linear search? Which figure would you quote to a client, and why?

4.12Words from this week

Term	Meaning in plain words
list	An ordered collection of values under one name.
index	The position of an item, counted from zero.
append / pop	Add to / remove from the end of a list.
linear search	Checking items one by one until you find it or run out.
aliasing	Two names pointing at the same list; a change through one shows through the other.
best / worst / average case	The luckiest, unluckiest and typical amount of work for the same method.
list comprehension	`[f(x) for x in things]` — build a list from a sequence in one line.

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.

Problem 2-6 · why the maximum algorithm is correct

Here is the standard way to find the largest value in a list A: remember the first item, then walk through the rest, keeping whatever is bigger. Argue that this really does return the maximum, for any list.

max_of_list.py

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

Worked solution

The idea: a running champion. Think of m as the current title-holder in a "who is biggest?" contest. We claim something simple stays true the whole way through the loop — a loop invariant:

After we have looked at the first k items, m holds the largest of those k.

If that sentence is true right up to the last item, then when the loop ends — having looked at all of them — m must hold the largest of the whole list. So we just need to see why it can never become false. Two small checks do it.

Base case (before the loop, k = 1). We set m = A[0]. The largest of just the first item is, of course, the first item. So the invariant is true at the start — with one item examined, m holds the biggest of that one item.

Each step keeps it true. Suppose it is true after k items: m is the biggest of the first k. Now we look at the next item, A[k]. Only two things can happen:

A[k] is bigger than the champion — the if fires, m becomes A[k], and now m is the biggest of all k + 1 items (it beat the old best, which beat everyone before it).
A[k] is not bigger — we leave m alone, and it is still the biggest of the first k, which are all at least as big as the newcomer, so it is the biggest of all k + 1 too.

Either way the invariant survives the step. Since it is true for one item, and each pass carries it from k to k + 1, it is still true after the last item — so the printed m is the maximum of the whole list. (This is the "running champion" version of a formal induction proof; it is exactly the argument you traced by hand on tiny inputs in §4.3.)

Answer: the loop keeps the invariant "m is the maximum of A seen so far". It holds before the loop (one item), each pass preserves it, so after the final pass m is the maximum of the entire list — the algorithm is correct.

Problem 2-45 · how often does the minimum get updated?

To find the minimum of a list, set tmp = A[0], then compare tmp against A[1], A[2], …, A[n] in order, doing tmp = A[i] whenever A[i] is smaller. If the list is in a random order, how many times, on average, does that assignment tmp = A[i] run?

min_of_list.py

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")

Worked solution

What is counted. The initial tmp = A[0] is set-up, not one of the assignments we count. We count the assignments made during the scan, at positions i = 1 … n (the array is A[0..n], i.e. n+1 numbers). When does position i assign? Only when A[i] is the smallest of the first i+1 numbers seen, A[0..i]. (A new "record low".)

Among the first i+1 numbers, in a random order each is equally likely to be the smallest, so the chance A[i] is a new record is exactly 1/(i+1). As i grows a new record gets rarer.

Add the chances over the scanned positions i = 1 … n:

expected assignments = Σ_i=1ⁿ 1/(i+1) = 1/2 + 1/3 + … + 1/(n+1) = H_n+1 − 1

Here H_m = 1 + 1/2 + … + 1/m is the harmonic number; H_n+1 − 1 is it with the leading 1 removed. It grows about like ln n — about 2.0 at n = 10, 4.2 at 100, 6.5 at 1000, 13.4 at a million. A quick simulation over random shuffles agrees. (If the array has exactly n elements, the same argument gives H_n − 1.)

Answer: the assignment fires at position i with probability 1/(i+1), so the expected number is H_n+1 − 1 = 1/2 + 1/3 + … + 1/(n+1) ≈ ln n — that is O(log n). It is not the full H_n: the initial tmp = A[0] is not a counted assignment.

Where this leads

You searched a list by hand and felt the work grow with n. Time to stop counting by hand: week 5 wraps work in a function and times it with a real stopwatch.