AP® Computer Science Principles · Big Idea 3 · Topic 3.10
Traversing a List
Traversing a list means visiting every element once, in order, usually with a FOR EACH loop that hands the loop body one item at a time until the list runs out.
A list can hold a thousand values, but a program can only act on one value at a time. Traversal is the pattern that bridges this: a loop steps through the list from the first element to the last, running the same block of code on each one. Without the loop, you'd need a separate line of code for every single element, which only works if you know exactly how many there are in advance.
FOR EACH handles this automatically. Each time through the loop, it takes the next element from the list, in order, and assigns it to a variable you name, then runs the loop body with that variable. Once it has handed out the last element, the loop ends on its own. You never manage an index or check a count yourself; the loop structure does that bookkeeping.
Traversal connects directly to searching. A search that stops the moment it finds a match looks faster than one that checks every element, and on average it often is. But worst case tells a different story: if the target is the last element, or isn't in the list at all, the stop-early search has to check every single element before it can stop or give up. That's exactly the same work as a full traversal. This gap between average behavior and worst-case behavior is the seed of later ideas about how algorithms are measured and compared.
Key terms
- Traversal
- Visiting every element of a list exactly once, typically from first to last.
- FOR EACH
- A loop structure that automatically assigns each element of a list, in order, to a variable for one pass through the loop body.
- Worst case
- The scenario where an algorithm takes the most possible steps, such as the target being last or absent in a search.
- Element
- A single value stored at one position within a list.
Watch it explained
- How it worksHow does FOR EACH hand the loop body one element at a time from first to last?
- Worked exampleTrace a FOR EACH loop that displays every element of the list 3, 1, 4, 1, 5.
- Going furtherWhat changes about a traversal when you only ever need the first half of the list?
- Common mistakeWhy isn't a partial traversal faster than a complete one in the worst case?
Check yourself
End of topic.