Week 04 — Lists: Holding Many Things at Once

The big question

What happens to the work when the data gets bigger?

A list stores many values without a separate variable for each. Reading a known position, scanning every value, and comparing pairs are different jobs with different costs.

Read and modify lists, trace scans and searches, construct filtered results, and explain aliasing. Justify a running maximum and distinguish condition tests from successful updates.

Retrieve with answers

Keep a small list on paper; predict each visited value before running code.

Positions, values and changes

For scores = [72, 88, 45, 91, 63], the length is five. The indices are 0 through 4, so scores[0] is 72 and scores[4] is 63. scores[-1] also accesses the last value. Index 5 is outside this list and raises IndexError.

The slice scores[1:4] produces [88, 45, 91]: start at index one and stop before index four. A single index retrieves one value; a slice creates a list of the selected values. A full slice, scores[:], creates a new outer list containing all the existing values.

Türkçe açıklama: “Üçüncü eleman” günlük dilde sıra numarasıdır; Python'daki indeksi 2'dir. İndeks ile elemanın değerini de ayır: scores[2] içindeki 2 konumu, sonuç olan 45 ise o konumdaki veriyi gösterir.

append(value) adds an item at the end. pop() removes and returns the final item. scores[0] = 75 replaces the value at an existing position. append modifies the list and returns None, so scores = scores.append(80) mistakenly replaces the useful name with None. However, removed = scores.pop() is valid because pop deliberately returns the removed value.

Reading a valid known index has constant growth cost in the usual list model: Python need not inspect all earlier entries. Searching for an unknown value may require inspecting the whole list. This does not promise identical measured time on every access; it describes dependence on list length.

Worked example 1: four answers from one scan

Compute the total, mean, number passing at 60, and maximum of the lesson's five scores. Assume a nonempty list so its first value initializes best and its length divides the total.

scores = [72, 88, 45, 91, 63]
total = 0
passed = 0
best = scores[0]
for score in scores:
    total = total + score
    if score >= 60:
        passed = passed + 1
    if score > best:
        best = score
mean = total / len(scores)
print(total, mean, passed, best)

359 71.8 4 91

The mean is 359 / 5 = 71.8. Passing values are 72, 88, 91 and 63. Each iteration performs several operations; there is one traversal. Doubling the length doubles its iterations.

Why initialize best from the data instead of zero? If the permitted data were [-8, -3, -6], a starting zero would never be replaced and would falsely appear as the maximum. The first real item supplies a valid candidate.

Türkçe açıklama: Başlangıç değeri, çözümün doğruluğunu etkiler. Toplam için sıfır uygundur; en büyük değer için her zaman uygun değildir. Boş listede ise “ilk eleman” yoktur: ya boş girdiyi baştan dışlamalı ya da onun için ayrı bir sonuç belirlemelisin.

Why the running maximum is correct

After inspecting some items, maintain this promise: best is the largest of the inspected items. This is a loop invariant. It is true initially because the first item is the largest of a one-item collection. For a new item, there are two cases. If it exceeds best, replace best. Otherwise keep best, which is at least as large as the newcomer. After the final item, the inspected prefix is the whole list.

Not every previous item exceeds the newcomer. For [2, 9] followed by 5, the previous 2 is smaller than 5, but maximum 9 remains correct. This distinction matters in Chapter 2 problem 2-6.

Türkçe açıklama: Korunan bilgi “önceki tüm sayılar büyük” değildir; “öncekilerin en büyüğü elimizde” bilgisidir. Her yineleme bu bilgiyi koruyunca son durumda bütün listenin cevabını elde ederiz. Buna değişmez denir çünkü doğru kalan ifade, döngü boyunca aynı yapıdadır.

Worked example 2: finding a value versus knowing its index

Search the lesson's name list for "Dilek". Record its first index and count equality comparisons.

names = ["Ada", "Bilal", "Cem", "Dilek", "Ece"]
target = "Dilek"
found_index = -1
looks = 0
for index in range(len(names)):
    looks = looks + 1
    if names[index] == target:
        found_index = index
        break
print(found_index, looks)

3 4

Index three means the fourth item, so four comparisons are correct. The -1 is a chosen “not found” marker here; do not immediately use it as names[-1], which would access the last name. A missing target requires five comparisons, and found_index remains -1.

If a successful target is equally likely to occupy any of n positions, the average comparison count is (1 + 2 + ... + n) / n = (n + 1)/2. For five names this is three. Without that probability assumption, “average” is unspecified; a workload containing many misses can be much more expensive.

Türkçe açıklama: target in names aynı işi daha kısa yazabilir, fakat liste içinde arama maliyetini ortadan kaldırmaz. Kaynak kodun kısalığı ile incelenen eleman sayısı farklı ölçülerdir.

Constructing lists and understanding shared objects

Filtering keeps selected values; transforming calculates new ones. From [72, 88, 45], filtering for at least 60 gives [72, 88]; adding five gives [77, 93, 50]. The comprehension [score + 5 for score in scores] means: visit each score, add five, collect the results. Every score is still visited.

list(range(4)) constructs [0, 1, 2, 3]. The lesson's random.sample produces distinct values, useful for a no-duplicates test. Deliberately include duplicates to test successful detection too.

For aliasing, a = [1, 2] followed by b = a makes two names refer to the same list. b.append(3) changes that shared list, so both names show [1, 2, 3]. Reassigning b = [9] instead attaches b to another list and leaves a unchanged. Names are not permanently tied together.

Türkçe açıklama: Atama bir listeyi otomatik kopyalamaz. İki isim aynı kutuyu gösterebilir; kutunun içini değiştirmek ikisinden de görünür. İsmi başka bir kutuya yönlendirmek ise önceki kutunun içini değiştirmez. a[:] yeni bir dış liste oluşturur; iç içe listelerde iç nesneler yine paylaşılabilir.

Three practice problems with complete solutions

Practice 1 — statistics and safe copying

For [12, 7, 30, 4, 18], find the total, mean, minimum and maximum. Create an independent outer list, append 99 to it, and state both final lists.

Solution 1

Total: 12 + 7 + 30 + 4 + 18 = 71; mean: 71 / 5 = 14.2; minimum: four; maximum: 30. Assign this list to original, use copy = original[:], then copy.append(99). The original stays [12, 7, 30, 4, 18]; the copy becomes [12, 7, 30, 4, 18, 99]. Türkçe: Tam dilim, bu sayı listesinin dış yapısını bağımsızlaştırır.

Practice 2 — build a filtered result

From [3, 8, 2, 9, 4], keep the even values in their original order. Give both a readable loop and an equivalent comprehension. Does finding three matches require only three tests?

Solution 2

data = [3, 8, 2, 9, 4]
evens = []
for value in data:
    if value % 2 == 0:
        evens.append(value)
compact = [value for value in data if value % 2 == 0]
print(evens)
print(compact)

[8, 2, 4]
[8, 2, 4]

Five values are tested, but only 8, 2 and 4 are appended. Both versions perform five tests; shortening the notation does not reduce that count. Türkçe: Çıktının uzunluğu üç, girdinin uzunluğu beştir. Filtreleme koşulunu reddedilen elemanlarda da denemek zorundayız.

Practice 3 — repeated searches and all distinct pairs

Twenty missing-target searches each scan 10 000 items. Find the total comparisons. Separately, compare every item with every later item in a four-item list, with no early stop. Enumerate the index pairs and generalize to n items.

Solution 3

The searches require 20 × 10 000 = 200 000 comparisons. For four items, the pairs are (0,1), (0,2), (0,3), (1,2), (1,3), (2,3). Row counts are three, two, one and zero, totaling six. For n items the total is (n − 1) + (n − 2) + ... + 1 = n(n − 1)/2.

At 100, 200 and 400 items, this gives 100 × 99 / 2 = 4950, 200 × 199 / 2 = 19 900, and 400 × 399 / 2 = 79 800. Doubling gives close to four times the comparisons, not exactly four for these finite sizes. Türkçe: Her çifti bir kez sayıyoruz; (0,1) ile (1,0) aynı iki elemanı tekrar karşılaştırmak olurdu.

A careful extension: tests versus updates

Chapter 2 problem 2-45 counts new minimum assignments, not all comparisons. In a uniformly random ordering of N distinct values, the second item becomes a new minimum with probability 1/2, the third with probability 1/3, and so on. Expected updates after initialization are 1/2 + 1/3 + ... + 1/N.

For four items: 1/2 + 1/3 + 1/4 = 6/12 + 4/12 + 3/12 = 13/12, about 1.083 updates. Each run makes an integer number; the fraction averages possible orders. Three comparisons still occur. The lesson indexes zero through n, so N = n + 1; check that convention before substituting.

Türkçe açıklama: Nadir güncellenen bir değişken, tüm algoritmanın az çalıştığını göstermez. Daha küçük bir değer çıkmasa bile sıradaki eleman karşılaştırılır. Olasılık hesabı ayrıca farklı değerler ve eş olasılıklı sıralamalar varsayar.

Misconceptions and glossary

Readiness, repair and Review A

Explain why a missing search over six values needs six comparisons, why two names can display the same appended item, and why a four-item all-pairs scan needs six comparisons. Answers: every candidate must be rejected; the names may share one list; the row counts are 3 + 2 + 1 + 0.

If any answer is uncertain, draw the list with indices, draw arrows from names to the list, or enumerate pairs on paper. Then change one input and predict the outcome again. Complete Review A — Weeks 1–4 before moving on: this is the built-in consolidation point for instructions, types, loops and lists. Week 5 packages a process into a function and measures it with a stopwatch. Clear inputs, correct outputs and meaningful counts come first.

Knowing a position is different from searching

An index is an item’s position in a list. If you already know the index, you can go straight to that item. Searching means checking items to find a value. That may take many checks, even when the Python instruction is short.

Draw or trace. Draw the list [8, 3, 8, 6] with positions (indices) 0–3. Point directly to index 2, then trace a left-to-right search for 6.

Predict before checking. How many equality checks find the first 8, find 6, or establish that 9 is missing?

Worked reasoning

The searches need 1, 4 and 4 comparisons. Because 8 appears twice, be clear about the answer you want: its first position, all its positions, or just whether it is present. These are different tasks. An empty list needs no item comparisons to report that a value is missing.

def first_match(values, target):
    checks = 0
    for index, value in enumerate(values):
        checks += 1
        if value == target:
            return index, checks
    return None, checks

assert first_match([8, 3, 8, 6], 8) == (0, 1)
assert first_match([8, 3, 8, 6], 6) == (3, 4)
assert first_match([8, 3, 8, 6], 9) == (None, 4)
assert first_match([], 9) == (None, 0)
print(first_match([8, 3, 8, 6], 9))

Change one thing. Move 6 to the front. Does that change the missing-target count? Explain why input arrangement matters for successful search.

Türkçe: İndis konumu zaten belirtir; değer aramak konumu bulmayı gerektirir. İlk eşleşme ile bütün eşleşmeler aynı çıktı değildir.

Additional analysis laboratory

Lists introduce the difference between known position and unknown value. This distinction is the bridge from basic Python to algorithm analysis.

Extra exam-style prompt: For [4, 1, 4, 9, 4], compare "does 4 appear?" with "how many 4s appear?" Give the output and the necessary inspections.

Solution: Membership can stop after the first item and return True after one comparison. Counting occurrences must inspect all five items and returns 3. The same input and target produce different work because the output contract is different.

Turkce: "Aramak" ve "saymak" ayni is degildir. Ilk eslesmede durmak, var mi sorusu icin dogru olabilir; kac tane sorusu icin yanlistir.