AP Computer Science Principles · Unit 3 lecture · Part 9 of 14 · 9 min

3.10 List traversal and linear searchVisiting every element

Mr. Thompkins
A list is only useful if you can go through it. Going through a list is called traversal, and a handful of traversal patterns cover almost every list question on the exam.

Traversing a list means accessing its elements one at a time. A complete traversal visits every element; a partial traversal visits only some, for example stopping once it finds what it needs. FOR EACH item IN aList is the easiest way to traverse: the body runs once per element, in order, with item set to each element. You can also traverse by index, using a counter i from 1 to LENGTH(aList) inside a loop.

?Wait, in FOR EACH t IN temps, is t an index or a value?
A value. t takes on each element itself: 71, then 68, then 77. If you need the position, use a counter i and aList[i] instead.

The classic traversal algorithms the course names: find the maximum or minimum, and compute the sum or average. Here's the maximum. Start with the first element (a value that's really in the list), then replace it whenever you see something bigger.

1temps ← [71, 68, 77, 74, 77]2best ← temps[1]13FOR EACH t IN temps4{5  IF (t > best)26  {7    best ← t28  }9}10DISPLAY(best)
  1. line 2 Start with a value that is really in the list
  2. line 5-7 Keep the biggest seen so far
output › 77
Finding the highest temperature.
tt > best?best
(start)71
71false71
68false71
77true77
74false77
77false77
best only changes when t is strictly bigger. The second 77 leaves it alone.

Why start with temps[1] and not 0? If every value in the list were negative, starting at 0 would leave best at 0, a number that isn't even in the list. That's a logic error that ordinary tests miss. For a sum, though, starting at 0 is exactly right, and the average is the sum divided by LENGTH.

Linear search

A linear search, also called a sequential search, checks each element of a list in order until it finds the value it wants or has checked every element. It works on any list, sorted or not. In the worst case, when the value is last or missing, it checks every element.

1names ← ["Ava", "Ben", "Cruz", "Ben"]2i ← 13found ← 04REPEAT UNTIL ((i > LENGTH(names)) OR (found ≠ 0))15{6  IF (names[i] = "Ben")27  {8    found ← i9  }10  i ← i + 111}12DISPLAY(found)
  1. line 4 Stop at the end of the list, or once found
  2. line 6 Check one element at a time, in order
output › 2
A linear search by index. It stops early once found becomes nonzero: a partial traversal.
checkistop?names[i]found after
11false"Ava"0
22false"Ben"2
33true (found ≠ 0)2
The trace. It finds the first "Ben" and never looks at the second.
?Wait, why is the stop condition an OR?
The search should stop when either thing happens: it runs off the end of the list, or it finds the target. Either one is enough, so OR. With AND it would need both at once and could run past the end of the list.
Pause and think
What would the search display if the target were "Zoe"?
I thought about it. Show me
0. It checks all four names, i grows to 5, the condition i > LENGTH(names) becomes true, and found was never changed. 0 serves as the "not found" signal, since no real index is 0.
Count with a traversal

What is displayed?

nums ← [9, 4, 12, 7, 15, 3]
count ← 0
FOR EACH n IN nums
{
  IF (n MOD 3 = 0)
  {
    count ← count + 1
  }
}
DISPLAY(count)
  1. The condition n MOD 3 = 0 is true when n is a multiple of 3.
  2. Go through the list: 9 yes (count 1), 4 no, 12 yes (count 2), 7 no, 15 yes (count 3), 3 yes (count 4).
    Why?
    3 MOD 3 = 0, so 3 counts as a multiple of itself.
  3. The loop ends after the last element, and count is 4.

Answer: 4

Stuck? Get a hint
  1. Which numbers in the list divide evenly by 3?
  2. Don't forget the last one, 3.
  3. count goes up once for each multiple.
Check yourself
What does this procedure return for mystery([8, 3, 9, 3, 5])?
PROCEDURE mystery(nums)
{
  m ← nums[1]
  FOR EACH v IN nums
  {
    IF (v < m)
    {
      m ← v
    }
  }
  RETURN(m)
}
  1. A8
  2. B3
  3. C5
  4. D9
Show the answer

B. It starts at 8 and keeps any smaller value: 3 replaces 8, and nothing after is smaller than 3. It returns the minimum, 3. 5 is the trap: it is the last element, not the smallest.

Check yourself
A list of 2,000 names is in no particular order. Which search can be used to find a name, and how many names might it check?
  1. ABinary search, about 11 names
  2. BLinear search, up to 2,000 names
  3. CBinary search, up to 2,000 names
  4. DLinear search, about 11 names
Show the answer

B. The list isn't sorted, so binary search won't work. Linear search works on any list, and in the worst case it checks all 2,000.

  • Traversal: visit elements one by one. Complete or partial.
  • FOR EACH gives values; an index loop gives positions.
  • Max/min: start with the first element. Sum: start at 0. Average: sum ÷ LENGTH.
  • Linear search checks in order until found or the end; it works on unsorted lists.