Array Traversals

A weather app stores a week of daily high temperatures in an array. To show them, it has to print every one. With four temperatures you could write temps[0], temps[1], temps[2], and temps[3] on four lines, but a year of temperatures would need 365 nearly identical lines, and the code would break the moment the array had a different length.

Look at what changes from one of those lines to the next: only the index, which goes 0, 1, 2, 3. From Topic 2.8 you know a for loop is built for exactly that, a counter that starts somewhere, grows by 1, and stops at a limit. If the counter is used as the index, one loop body can reach every element in turn.

Using a loop to reach the elements of an array one after another is called traversing the array, and one complete run through it is a traversal. A traversal can visit every element, or only some of them in a planned order (that is 4.4.2). When the loop counter is the index, as here, the loop is called an indexed loop.

The standard header for visiting every element of an array named temps is:

for (int i = 0; i < temps.length; i++)

Because the test uses temps.length instead of a typed number like 4, the same loop works for an array of any length.

int[] temps = {68, 71, 75, 70};
for (int i = 0; i < temps.length; i++)
{
    System.out.println("Day " + i + ": " + temps[i]);
}

Day 0: 68
Day 1: 71
Day 2: 75
Day 3: 70

An indexed loop can also change elements, because points[i] on the left of = stores into the array (Topic 4.3). This program doubles every score, then uses a second traversal to print them.

int[] points = {3, 5, 8};
for (int i = 0; i < points.length; i++)
{
    points[i] = points[i] * 2;
}
for (int i = 0; i < points.length; i++)
{
    System.out.println(points[i]);
}

On line 4, the right side reads the current element and the = stores the doubled value back into the same slot. After the first loop the array holds {6, 10, 16}, and the second loop prints:

6
10
16

Remember this example; 4.4.5 shows a different loop that looks like it does the same thing but does not.

int[] temps = {68, 71, 75, 70};
for (int i = 0; i <= temps.length; i++)
{
    System.out.println(temps[i]);
}

68
71
75
70
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 4 out of bounds for length 4

String[] words = {"map", "tree", "go"};
for (int k = 0; k < words.length; k++)
{
    System.out.println(k + " " + words[k].length());
}

0 3
1 4
2 2

public class LengthParens
{
    public static void main(String[] args)
    {
        int[] scores = {90, 85, 77};
        for (int i = 0; i < scores.length(); i++)
        {
            System.out.println(scores[i]);
        }
    }
}

A bus app lists the stops on a route. Riders going the other way want the list from the last stop to the first. A coach wants to call every other runner in a lineup. A track timer wants every lap except the first and last. None of these visits the elements from index 0 to the end one at a time, yet each still visits elements in a planned order.

The indexed for loop from 4.4.1 handles all of them, because each of its three parts can change, just as they did in Topic 2.8. The rule that never changes is that every index the body uses must be between 0 and length - 1.

String[] stops = {"Elm", "Oak", "Pine", "Main"};
for (int i = stops.length - 1; i >= 0; i--)
{
    System.out.println(stops[i]);
}

Main
Pine
Oak
Elm

Now change only the update. With i += 2, the loop jumps two indexes at a time:

String[] lineup = {"Ana", "Ben", "Cy", "Dee", "Eli"};
for (int i = 0; i < lineup.length; i += 2)
{
    System.out.println(lineup[i]);
}

i takes the values 0, 2, and 4, then becomes 6, and 6 < 5 is false. The program prints:

Ana
Cy
Eli

The test i < lineup.length still protects the array. If the lineup had 4 names instead of 5, i would go 0, 2, then 4, and 4 < 4 would stop the loop before reaching a bad index.

String[] stops = {"Elm", "Oak", "Pine", "Main"};
for (int i = stops.length; i >= 0; i--)
{
    System.out.println(stops[i]);
}

int[] codes = {4, 9, 2, 7, 5, 1, 8};
for (int i = codes.length - 1; i > 0; i -= 3)
{
    System.out.println(codes[i]);
}

8
7

int[] laps = {52, 49, 47, 48, 50, 55};
for (int i = 1; i < laps.length - 1; i++)
{
    System.out.println("Lap " + i + ": " + laps[i]);
}

Every traversal so far has used a for loop. In Topic 2.8 you learned that any for loop can be written as a while loop with the same three parts placed on separate lines. The same is true for traversals, and sometimes a while loop reads more naturally, for example when the loop should also stop early for a reason other than reaching the end.

A while traversal is still an indexed traversal: you need your own index variable, declared before the loop, tested in the condition, used inside the brackets, and updated at the end of the body.

int i = 0;                  // start
while (i < temps.length)    // test
{
    // use temps[i]
    i++;                    // update
}

int[] temps = {68, 71, 75, 70};
int i = 0;
while (i < temps.length)
{
    System.out.println("Day " + i + ": " + temps[i]);
    i++;
}

Day 0: 68
Day 1: 71
Day 2: 75
Day 3: 70

Now vary the condition. A to-do list ends with a marker "done", and anything after the marker should be ignored. The while condition can check both “still inside the array” and “not at the marker yet”:

String[] tasks = {"wash", "dry", "done", "fold"};
int i = 0;
while (i < tasks.length && !tasks[i].equals("done"))
{
    System.out.println(tasks[i]);
    i++;
}
System.out.println("Stopped at index " + i);

wash
dry
Stopped at index 2

This traversal visits an ordered part of the array, from the start up to the marker. Because i is declared before the loop, it still exists afterward, so line 8 can report where the loop stopped.

The order of the two tests matters. If the array has no "done" at all, i eventually reaches the length. Then i < tasks.length is false, and by short-circuit evaluation (Topic 2.5) Java never evaluates tasks[i]. Swap the two tests and that protection disappears:

String[] tasks = {"wash", "dry"};
int i = 0;
while (!tasks[i].equals("done") && i < tasks.length)
{
    System.out.println(tasks[i]);
    i++;
}
System.out.println("Stopped at index " + i);

This prints wash and dry, then crashes with an ArrayIndexOutOfBoundsException for index 2, because when i is 2 Java evaluates tasks[2] first. With the tests in the original order, the same two-element array prints wash, dry, and Stopped at index 2.

int i = 0;
while (i < temps.length)
{
    System.out.println(temps[i]);
}

int[] seats = {12, 15, 9, 20, 11};
int n = seats.length - 1;
while (n >= 0)
{
    System.out.println(seats[n]);
    n -= 2;
}

11
9
12

Look back at PrintTemps without the day numbers. If all you want is each temperature, the index variable is just bookkeeping: you set it up, test it, add 1 to it, and use it in brackets, all to get at values you could describe simply as “each temperature in the array.” Java has a shorter loop for exactly that situation.

The enhanced for loop (sometimes called a for-each loop) visits every element of an array from first to last without any index. Its header names a variable, and on each pass that variable is given a copy of the next element.

for (int t : temps)

Read it aloud as “for each int t in temps.”

Behind the scenes Java still walks through the indexes 0, 1, 2, and so on, but you never see them. That means three things the indexed loop could do are impossible here: the loop always starts at the first element, always moves forward one element at a time, and never tells you the current index.

int[] temps = {68, 71, 75, 70};
for (int t : temps)
{
    System.out.println(t);
}

68
71
75
70

The element type does not have to be int. For an array of String, the loop variable is a String, so you can call String methods on it:

String[] guests = {"Rosa", "Kenji", "Amara"};
for (String guest : guests)
{
    System.out.println(guest + " has " + guest.length() + " letters");
}

Rosa has 4 letters
Kenji has 5 letters
Amara has 5 letters

Each pass, guest refers to the next name, and guest.length() is that name’s number of letters.

int[] temps = {68, 71, 75, 70};
for (int t : temps)
{
    System.out.println(temps[t]);
}

int[] nums = {2, 0, 3, 1};
for (int value : nums)
{
    System.out.println(nums[value]);
}

3
2
1
0

public class WrongVarType
{
    public static void main(String[] args)
    {
        int[] temps = {68, 71, 75, 70};
        for (String t : temps)
        {
            System.out.println(t);
        }
    }
}

In 4.4.1, an indexed loop doubled every score with points[i] = points[i] * 2. The enhanced for loop is shorter, so it is tempting to write the same job as “for each p in points, set p to p * 2.” Does that change the array?

The key word in 4.4.4 was copy. On each pass the loop variable gets a copy of the element, the same way a parameter gets a copy of its argument (Topic 3.5). Changing the copy does not reach back to the original. Think of copying a phone number from a contact list onto a sticky note: if you scribble a new number on the note, the contact list does not change.

int[] points = {3, 5, 8};
for (int p : points)
{
    p = p * 2;
    System.out.println("p is now " + p);
}
for (int p : points)
{
    System.out.println("array holds " + p);
}

p is now 6
p is now 10
p is now 16
array holds 3
array holds 5
array holds 8

The same thing happens with an array of String. Here the loop tries to make each name uppercase:

String[] guests = {"Rosa", "Kenji"};
for (String guest : guests)
{
    guest = guest.toUpperCase();
}
System.out.println(guests[0] + " " + guests[1]);

Rosa Kenji

guest.toUpperCase() builds a new string, "ROSA", and line 4 makes guest refer to it. The array element still refers to the original "Rosa". As with a String parameter in Topic 3.6, assigning to the variable moves only the variable.

for (int i = 0; i < guests.length; i++)
{
    guests[i] = guests[i].toUpperCase();
}

int[] quiz = {7, 9, 6};
for (int q : quiz)
{
    q += 1;
    System.out.println(q);
}
System.out.println(quiz[0] + " " + quiz[1] + " " + quiz[2]);

8
10
7
7 9 6

for (String g : guests)
{
    g = g + "!";
}

A game keeps its players in an array of Player objects. At the end of a round, every player earns a 5-point bonus. From 4.4.5 you might expect an enhanced for loop to be useless for this, since it only hands out copies. But what exactly is being copied when the elements are objects?

From Topic 3.6, a variable of a class type holds a reference, the address of an object. An array of Player holds references too. So when the enhanced for loop copies an element into its variable, it copies the address, not the object. The loop variable becomes an alias of the object the array element refers to, exactly like a parameter that receives an object. That leads to two different outcomes:

In the sticky-note picture, the note now has a house address on it. Going to the house and painting the door changes the house that the array’s address also leads to. Writing a different address on the note changes only the note.

The programs in this subsection use a small Player class with a name, a point total, two accessors, and the mutator addPoints. Java allows only one public class per file, so the helper class here leaves off public; in a real project each class gets its own file.

class Player
{
    private String name;
    private int points;

    public Player(String playerName, int startPoints)
    {
        name = playerName;
        points = startPoints;
    }

    public String getName()
    {
        return name;
    }

    public int getPoints()
    {
        return points;
    }

    public void addPoints(int amount)
    {
        points += amount;
    }
}

public class TeamBonus
{
    public static void main(String[] args)
    {
        Player[] team = {new Player("Ada", 10), new Player("Bo", 7)};
        for (Player p : team)
        {
            p.addPoints(5);
        }
        for (Player p : team)
        {
            System.out.println(p.getName() + " " + p.getPoints());
        }
    }
}

Ada 15
Bo 12

Now vary the body: instead of calling a mutator, assign a new object to p.

class Player
{
    private String name;
    private int points;

    public Player(String playerName, int startPoints)
    {
        name = playerName;
        points = startPoints;
    }

    public String getName()
    {
        return name;
    }

    public int getPoints()
    {
        return points;
    }

    public void addPoints(int amount)
    {
        points += amount;
    }
}

public class TeamReplace
{
    public static void main(String[] args)
    {
        Player[] team = {new Player("Ada", 10), new Player("Bo", 7)};
        for (Player p : team)
        {
            p = new Player("Rookie", 0);
        }
        for (Player p : team)
        {
            System.out.println(p.getName() + " " + p.getPoints());
        }
    }
}

Ada 10
Bo 7

Each pass, line 35 builds a new rookie and moves p to it. That changes only p. team[0] and team[1] still hold addresses A and B, and nothing changed those objects, so Ada and Bo keep their original points. The two rookies are lost when the loop moves on, because nothing holds their addresses.

for (int i = 0; i < team.length; i++)
{
    team[i] = new Player("Rookie", 0);
}

class Player
{
    private String name;
    private int points;

    public Player(String playerName, int startPoints)
    {
        name = playerName;
        points = startPoints;
    }

    public String getName()
    {
        return name;
    }

    public int getPoints()
    {
        return points;
    }

    public void addPoints(int amount)
    {
        points += amount;
    }
}

public class MixedLoop
{
    public static void main(String[] args)
    {
        Player[] team = {new Player("Kai", 4), new Player("Lee", 6)};
        for (Player p : team)
        {
            p.addPoints(2);
            p = new Player("Temp", 100);
            p.addPoints(2);
        }
        System.out.println(team[0].getName() + " " + team[0].getPoints());
        System.out.println(team[1].getName() + " " + team[1].getPoints());
    }
}

Kai 6
Lee 8

You now have three ways to traverse an array: an indexed for loop, a while loop, and an enhanced for loop. How do you choose? And if a program uses one kind, can you always switch to another?

Switching from an enhanced for loop to an indexed loop always works. The enhanced loop visits every element from first to last, and an indexed loop from 0 while i < arr.length does exactly the same. The trick is to recreate the loop variable: inside the body, wherever the enhanced loop used its variable, use arr[i]. The easiest way is to declare a variable with the same name and set it to arr[i] as the first line of the body; then the rest of the body does not change at all.

String[] colors = {"red", "teal", "gold"};

for (String c : colors)
{
    System.out.println("enhanced: " + c);
}

for (int i = 0; i < colors.length; i++)
{
    String c = colors[i];
    System.out.println("indexed: " + c);
}

int j = 0;
while (j < colors.length)
{
    String c = colors[j];
    System.out.println("while: " + c);
    j++;
}

enhanced: red
enhanced: teal
enhanced: gold
indexed: red
indexed: teal
indexed: gold
while: red
while: teal
while: gold

The other direction does not always work. An enhanced for loop cannot replace an indexed loop that needs the index. Use this to choose:

Calling a mutator on objects in the array works with any of the three, as 4.4.6 showed.

int[] ages = {15, 17, 16};
for (int i = 0; i < ages.length; i++)
{
    System.out.println(i);
}

0
1
2

    System.out.println(ages[i]);

This program uses every kind of traversal from the chapter on one array of Player objects (the same Player class as in 4.4.6). Before reading the explanation, predict the output.

class Player
{
    private String name;
    private int points;

    public Player(String playerName, int startPoints)
    {
        name = playerName;
        points = startPoints;
    }

    public String getName()
    {
        return name;
    }

    public int getPoints()
    {
        return points;
    }

    public void addPoints(int amount)
    {
        points += amount;
    }
}

public class RosterDay
{
    public static void main(String[] args)
    {
        Player[] roster = {new Player("Ada", 12), new Player("Bo", 9), new Player("Cy", 15)};

        for (Player p : roster)
        {
            p.addPoints(3);
        }

        roster[1] = new Player("Dee", 0);

        for (int i = 0; i < roster.length; i++)
        {
            System.out.println((i + 1) + ". " + roster[i].getName() + " " + roster[i].getPoints());
        }

        int k = roster.length - 1;
        while (k >= 0)
        {
            System.out.println(roster[k].getName());
            k--;
        }
    }
}

Call the three original objects A (Ada, 12), B (Bo, 9), and C (Cy, 15).

1. Ada 15
2. Dee 0
3. Cy 18
Cy
Dee
Ada

Each loop was chosen for its job. The bonus only needed each object, so the enhanced for loop was simplest; it worked because addPoints changes the objects, not the array. Replacing Bo needed an assignment to roster[1]. The numbered list needed the index, and printing in reverse needed an index that counts down. Bo’s object, now with 12 points, is lost because no element refers to it anymore.

• Traversing an array means using a loop to reach its elements in order, either all of them or a planned part.
• An indexed for or while loop reaches elements through their indexes. To visit every element, go from 0 while the index is less than the length; any other start, test, or update is fine as long as every index stays between 0 and length minus 1, or the program throws an ArrayIndexOutOfBoundsException.
• An enhanced for loop gives its variable a copy of each element, first to last, with no index. Assigning to that variable never changes the array.
• When the elements are object references, the enhanced for loop variable is an alias of each object, so calling a mutator on it changes the object, but the references stored in the array stay the same.
• Any enhanced for loop can be rewritten as an indexed for or while loop using arr[i]; tasks that need positions, a different order, or changes to the elements themselves require an indexed loop.

int[] vals = {1, 2, 3, 4, 5, 6};
for (int i = 1; i < vals.length; i += 2)
{
    vals[i] = vals[i] * 10;
}
for (int v : vals)
{
    v = 0;
}
for (int v : vals)
{
    System.out.println(v);
}

1
20
3
40
5
60

class Player
{
    private String name;
    private int points;

    public Player(String playerName, int startPoints)
    {
        name = playerName;
        points = startPoints;
    }

    public String getName()
    {
        return name;
    }

    public int getPoints()
    {
        return points;
    }

    public void addPoints(int amount)
    {
        points += amount;
    }
}

public class NullTeam
{
    public static void main(String[] args)
    {
        Player[] team = new Player[3];
        team[0] = new Player("Ada", 10);
        for (Player p : team)
        {
            p.addPoints(1);
            System.out.println(p.getName() + " " + p.getPoints());
        }
    }
}

class Scoreboard
{
    private int[] scores;

    public Scoreboard(int teams)
    {
        scores = new int[teams];
    }

    public void addScore(int team, int amount)
    {
        scores[team] += amount;
    }

    public void resetAll()
    {
        for (int s : scores)
        {
            s = 0;
        }
    }

    public int getScore(int team)
    {
        return scores[team];
    }
}

public class ScoreboardReset
{
    public static void main(String[] args)
    {
        Scoreboard board = new Scoreboard(3);
        board.addScore(0, 4);
        board.addScore(2, 7);
        board.resetAll();
        System.out.println(board.getScore(0) + " " + board.getScore(1) + " " + board.getScore(2));
    }
}

for (int i = 0; i < scores.length; i++)
{
    scores[i] = 0;
}

double[] prices = {2.5, 4.0, 1.25};
for (double price : prices)
{
    System.out.println(price);
}

int[] readings = {5, 8, -1, 4};
int i = 0;
while (i < readings.length && readings[i] >= 0)
{
    System.out.println(readings[i] * 2);
    i++;
}
System.out.println("i = " + i);

10
16
i = 2

int[] data = {10, 20, 30, 40, 50, 60, 70};
for (int i = data.length - 2; i >= 1; i -= 2)
{
    System.out.println(i + ": " + data[i]);
}

• I can write the header of an indexed for loop that visits every element, and explain why the test uses less than the length. Reread
• I can trace a traversal that goes backward, skips elements, or visits only part of an array. Reread
• I can traverse an array with a while loop and explain why the bounds test comes first in a two-part condition. Reread
• I can read an enhanced for loop and say what its variable holds on each pass. Reread
• I can explain why assigning to the enhanced for loop variable does not change the array. Reread
• I can predict whether a change made through the loop variable shows up in an array of objects. Reread
• I can rewrite an enhanced for loop as an indexed loop and choose the right loop for a task. Reread