Unit 3 · Programming 2 · Lesson 3.8

Traversal

“Do this to every element” is half of all programs ever written. Traversal is the loop that visits an entire list, one element at a time — and paired with the accumulator, it’s where lists finally pay off.

Big Idea 3 — Algorithms & ProgrammingWeek 2 · Lists

Before this lesson — read on Runestone

This is today’s lesson exactly — the for-each traversal. Enrolled in our Runestone course? Open it from there so your progress counts.

1

Where We Are

People→ Bits→ Programs→ Internet→ Security→ Big Data→ Impact

Still in Programs. You have loops (Week 1) and lists (3.6–3.7). Traversal is where they combine: a loop that walks a list end to end. Drop an accumulator inside and you can sum, count, or search a whole collection.

2

The Hook

“Grade every paper in the stack.” You don’t grade paper #0, then #1, then #2 by number — you just go through the stack, one at a time, until it’s done. That’s traversal: for each item, do something.

Python’s for item in list hands you each element directly — no index needed. It reads almost like English, and it’s the cleanest way to touch every value in a collection.

3

The Idea

Traversal means visiting every element of a list in order. The clean way is the for-each loop, which gives you the value each pass — no index arithmetic:

Python — sum by traversal

scores = [85, 90, 78]
total = 0
for s in scores:
    total = total + s
print(total)   # 253

AP Pseudocode — FOR EACH

scores ← [85, 90, 78]
total ← 0
FOR EACH s IN scores
{ total ← total + s }
DISPLAY(total)   /* 253 */

Hover or tap a line to light its twin. This is traversal + accumulator: the loop supplies each score, the accumulator adds it. Trace it — total goes 0 → 85 → 175 → 253.

Two ways to traverse: element-based (for s in scores) hands you the value — best when you just need each value. Index-based (for i in range(len(scores)), then use scores[i]) hands you the position — needed when you must know where you are, or change the list as you go.
Traversal + accumulator = most list programs. Sum a list, count how many pass, find the longest name, add up a cart — nearly every one is “walk the list, update a running value.” You already know both halves; today just clicks them together.
4

Try It — Traverse and Accumulate

Step through a traversal and watch the loop hand over each element while the accumulator updates. Switch the job to see the same traversal sum or count.

list:
5

Vocabulary

traversal Programs
Visiting every element of a list in order, usually with a loop.
for-each loop Programs
A loop that hands you each element directly (for s in scores / FOR EACH s IN scores) — no index needed.
sequential access Programs
Reaching elements one after another, in order — what a traversal does.
6

Check

Five questions. Trace the traversal element by element, updating the accumulator as you go, then pick your answer.

0 of 5 answered
7

Impact Check

“For each” is how the big numbers get crunched

Total a store’s daily sales, average a million survey answers, scan every transaction for fraud, apply a filter to every pixel — all traversal. The phrase “for each” is doing the heavy lifting behind analytics, recommendations, and search. One clean loop, applied to a collection of any size.

It’s also where scale becomes visible. The same for-each that sums three scores in an instant takes real time over three billion — which is why Unit 4 asks how long algorithms take, and Unit 5 asks how we handle data too big to look at all at once.

8

Connections

Came from 3.4 + 3.6 — traversal is the accumulator loop pointed at a list.
Next in 3.9 — the four canonical algorithms (max, min, average, count-if) are all traversal + accumulator with different update rules.
Returns in 3.10 — the gradebook traverses a list of scores to report everything at once.
Returns on the exam — “what does this FOR EACH loop compute?” is a guaranteed pseudocode question. Trace it element by element.
← 3.7 Lists II