AP Computer Science A · Unit 4 lecture · Part 3 of 14 · 8 min

4.4 Array traversalsTraversals: visit every element

Mr. Thompkins
Almost every array method you'll ever write is the same loop with a different body. Learn the loop cold, and you can spend your thinking on the body.

A traversal visits the elements of an array, usually every one, in order. The standard version is a for loop whose index starts at 0, runs while it is less than the length, and goes up by 1. Inside the loop, arr[i] is the current element.

1int[] scores = {7, 3, 9, 4};2int sum = 0;3for (int i = 0; i < scores.length; i++)14{5    sum += scores[i];6}7System.out.println(sum);89for (int i = scores.length - 1; i >= 0; i--)210{11    System.out.print(scores[i] + " ");12}13System.out.println();1415for (int s : scores)316{17    System.out.print(s * 10 + " ");18}
  1. line 3 Start at 0, stop before length, step by 1
  2. line 9 Backward: start at length - 1, stop after 0
  3. line 15 Enhanced for: s is each value in order, no index
output › 23 4 9 3 7 70 30 90 40
Three traversals of one array: forward with an index, backward with an index, and an enhanced for.
ii < scores.lengthscores[i]sum after
0true77
1true310
2true919
3true423
4false: loop ends23
The first loop, one pass per row. The test fails at i = 4, which is exactly when arr[4] would have been out of range.
?Wait, why i < scores.length and not i <= scores.length?
The last index is length - 1. With <=, the loop runs one extra time with i equal to length, and scores[4] throws an ArrayIndexOutOfBoundsException. "Start at 0, stop before length" is the pattern to memorize.

You can change any part of the loop to visit only some elements: start at 1 to skip the first, use i += 2 to take every other one, stop at length / 2 to cover the first half, or run backward from length - 1 down to 0. A while loop works too, as long as you update the index yourself.

The enhanced for loop, for (int s : scores), reads "for each int s in scores". It visits every element in order and hands you the value, with no index. It's the cleanest way to read every element. But the variable s is a copy of each value, and that has consequences.

1int[] pts = {3, 8, 5};2for (int x : pts)3{4    x = x * 2;15}6System.out.println(pts[0] + " " + pts[1] + " " + pts[2]);7for (int i = 0; i < pts.length; i++)8{9    pts[i] = pts[i] * 2;210}11System.out.println(pts[0] + " " + pts[1] + " " + pts[2]);1213Tile[] row = {new Tile(1), new Tile(5)};14for (Tile t : row)15{16    t.bump();317}18System.out.println(row[0].getValue() + " "19    + row[1].getValue());
  1. line 4 x is a copy of each value. The array never changes
  2. line 9 To change elements, assign through the index
  3. line 16 t is a copy of a reference, so bump changes the real Tile
output › 3 8 5 6 16 10 2 6
Assigning to the enhanced for variable changes a copy. Calling a method through it changes the real object.
?Wait, what's the Tile class in that code?
A tiny class written for this example: a Tile has a private int value, a constructor that sets it, a method bump() that adds 1 to value, and getValue(). An array of Tiles holds references to Tile objects, just like a variable of type Tile would.
Pause and think
Why did the Tile objects change, when the ints in pts didn't?
I thought about it. Show me
In both loops the variable is a copy. For pts, x is a copy of an int, so changing x changes nothing else. For row, t is a copy of a reference, and a copied reference still points to the same Tile, so t.bump() changes the real object. It's the same rule as passing parameters in Unit 3.

So which loop should you use? Use an index loop when you need the position: to change elements, to compare an element with its neighbor, to go backward or to report where something is. Use an enhanced for when you only need to read each value.

Trace a partial traversal

What does this print?

int[] v = {6, 1, 8, 3, 7, 2};
int total = 0;
for (int i = 1; i < v.length; i += 2)
{
    total += v[i] - v[i - 1];
}
System.out.println(total);
  1. The loop starts at i = 1 and jumps by 2: i is 1, 3, 5. At i = 7 the test 7 < 6 fails.
    Why?
    List the values of i first. It's the fastest way to avoid off-by-one mistakes.
  2. i = 1: v[1] - v[0] = 1 - 6 = -5. total is -5.
  3. i = 3: v[3] - v[2] = 3 - 8 = -5. total is -10.
  4. i = 5: v[5] - v[4] = 2 - 7 = -5. total is -15.

Answer: -15

Stuck? Get a hint
  1. Which values does i take? Start at 1 and add 2 each time while i < 6.
  2. Each pass subtracts the element just before i.
  3. Three passes, each adding -5.
Check yourself
What is printed?
int[] v = {2, 5, 1, 6, 3};
int s = 0;
for (int i = v.length - 1; i > 0; i -= 2)
{
    s += v[i];
}
System.out.println(s);
  1. A4
  2. B6
  3. C17
  4. D11
Show the answer

A. i starts at 4 and goes down by 2: i = 4 adds 3, i = 2 adds 1, and then i = 0 fails the test i > 0. So s is 4. The second choice is the trap: it includes v[0], which would need i >= 0.

  • Standard traversal: for (int i = 0; i < arr.length; i++).
  • Change the start, the step or the stop to visit only part of the array, or go backward from length - 1.
  • The enhanced for variable is a copy: assigning to it never changes the array.
  • For an array of objects, calling a method through the enhanced for variable does change the object.