ArrayList Traversals

A music app keeps a playlist in an ArrayList<String>. To show the playlist on screen, the app has to look at every song, one after another. In Topic 4.8 you could reach one element at a time with get, but writing songs.get(0), songs.get(1), songs.get(2), … by hand only works if you know exactly how many songs there are. A playlist can have 4 songs today and 40 tomorrow.

You solved the same problem for arrays in Topic 4.4: let a loop variable count through the indices, and use it to reach each element in turn. The same plan works for an ArrayList. Only two details change:

• An array tells you its length with .length (no parentheses). An ArrayList tells you how many elements it holds with the method call size().
• An array element is scores[i]. An ArrayList element is songs.get(i).

Using a loop to visit all the elements of a list, or an ordered run of them (for example, every other one, or the last three), is called traversing the list. One such pass is a traversal.

import java.util.ArrayList;

public class PlaylistIndexed
{
    public static void main(String[] args)
    {
        ArrayList<String> songs = new ArrayList<String>();
        songs.add("Sunrise");
        songs.add("Rain Song");
        songs.add("Night Drive");
        songs.add("Echoes");

        for (int i = 0; i < songs.size(); i++)
        {
            System.out.println(i + ": " + songs.get(i));
        }
    }
}

0: Sunrise
1: Rain Song
2: Night Drive
3: Echoes

A traversal does not have to start at the front or visit every element. Because the loop header is an ordinary for loop from Topic 2.8, you can change the start, the test, and the update to walk through the list in a different order.

import java.util.ArrayList;

public class PlaylistBackward
{
    public static void main(String[] args)
    {
        ArrayList<String> songs = new ArrayList<String>();
        songs.add("Sunrise");
        songs.add("Rain Song");
        songs.add("Night Drive");
        songs.add("Echoes");

        for (int i = songs.size() - 1; i >= 0; i--)
        {
            System.out.println(songs.get(i));
        }
    }
}

Echoes
Night Drive
Rain Song
Sunrise

import java.util.ArrayList;

public class PlaylistWhile
{
    public static void main(String[] args)
    {
        ArrayList<String> songs = new ArrayList<String>();
        songs.add("Sunrise");
        songs.add("Rain Song");
        songs.add("Night Drive");
        songs.add("Echoes");
        songs.add("Last Call");

        int i = 0;
        while (i < songs.size())
        {
            System.out.println(songs.get(i));
            i += 2;
        }
    }
}

import java.util.ArrayList;

public class ListLength
{
    public static void main(String[] args)
    {
        ArrayList<String> songs = new ArrayList<String>();
        songs.add("Sunrise");
        songs.add("Echoes");

        for (int i = 0; i < songs.length; i++)
        {
            System.out.println(songs[i]);
        }
    }
}

ListLength.java:11: error: cannot find symbol
  symbol:   variable length
ListLength.java:13: error: array required, but ArrayList<String> found

import java.util.ArrayList;

public class PrizeTrace
{
    public static void main(String[] args)
    {
        ArrayList<String> prizes = new ArrayList<String>();
        prizes.add("pen");
        prizes.add("mug");
        prizes.add("hat");
        prizes.add("bag");
        prizes.add("cap");

        for (int i = 1; i < prizes.size(); i += 2)
        {
            System.out.println(i + " " + prizes.get(i));
        }
    }
}

1 mug
3 bag

The loop in 4.9.1 stopped at exactly the right moment. What happens if a loop goes one step too far? With a String in Topic 1.15, asking for a character past the end crashed the program. With arrays in Topic 4.3, asking for a missing index crashed it too. An ArrayList follows the same rule, for the same reason: there is no element there to return, and Java refuses to make one up.

When a program calls get, set, or remove with an index less than 0 or greater than size() - 1, Java stops the program with an IndexOutOfBoundsException, a runtime error meaning “that index is outside the list.” The program compiles, because the compiler cannot know how big the list will be when the line runs. The problem only appears when the line actually runs with a bad index.

import java.util.ArrayList;

public class ScoresTooFar
{
    public static void main(String[] args)
    {
        ArrayList<Integer> scores = new ArrayList<Integer>();
        scores.add(88);
        scores.add(73);
        scores.add(95);

        for (int i = 0; i <= scores.size(); i++)
        {
            System.out.println(scores.get(i));
        }
        System.out.println("Done");
    }
}

88
73
95
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 3 out of bounds for length 3

The same mistake can happen at the other end of a backward traversal. Change one thing from the backward loop in 4.9.1: start at size() instead of size() - 1.

import java.util.ArrayList;

public class BackwardFromSize
{
    public static void main(String[] args)
    {
        ArrayList<Integer> scores = new ArrayList<Integer>();
        scores.add(88);
        scores.add(73);
        scores.add(95);

        for (int i = scores.size(); i >= 0; i--)
        {
            System.out.println(scores.get(i));
        }
    }
}

import java.util.ArrayList;

public class ShiftedStart
{
    public static void main(String[] args)
    {
        ArrayList<String> colors = new ArrayList<String>();
        colors.add("red");
        colors.add("blue");
        colors.add("green");
        colors.add("gold");

        for (int i = 1; i <= colors.size(); i++)
        {
            System.out.println(colors.get(i));
        }
    }
}

Many traversals never use the index at all. Printing each song only needs the song, not its position. In Topic 4.4 you met a shorter loop for exactly this job on arrays, the enhanced for loop. It works on an ArrayList in the same way, and it removes the chance of an index mistake, because there is no index to get wrong.

Here is the form, read aloud as “for each song in songs”:

for (String song : songs)

• String is the type of each element. It must match the list’s element type, the E in ArrayList<E>.
• song is the enhanced for loop variable. On each pass, Java assigns it the next element of the list, starting with the element at index 0.
• The colon separates the variable from the list being traversed.

import java.util.ArrayList;

public class PlaylistEnhanced
{
    public static void main(String[] args)
    {
        ArrayList<String> songs = new ArrayList<String>();
        songs.add("Sunrise");
        songs.add("Rain Song");
        songs.add("Night Drive");
        songs.add("Echoes");

        for (String song : songs)
        {
            System.out.println("Now playing: " + song);
        }
    }
}

For a list of Integer, the loop variable can be an int. Each Integer element is unboxed into an int as it is assigned, which is the unboxing from Topic 4.7.

import java.util.ArrayList;

public class TempsEnhanced
{
    public static void main(String[] args)
    {
        ArrayList<Integer> temps = new ArrayList<Integer>();
        temps.add(64);
        temps.add(71);
        temps.add(58);

        for (int temp : temps)
        {
            int fahrenheitAboveFreezing = temp - 32;
            System.out.println(temp + " is " + fahrenheitAboveFreezing + " above freezing");
        }
    }
}

64 is 32 above freezing
71 is 39 above freezing
58 is 26 above freezing

What the loop variable can and cannot change

The loop variable is a separate variable that is handed a copy of each element. That one fact explains two behaviors that look contradictory until you see it.

Assigning to the loop variable changes only the variable. In the next program, the goal is to make every word uppercase. (Printing an ArrayList with println shows its elements in square brackets, separated by commas.)

import java.util.ArrayList;

public class ShoutWrong
{
    public static void main(String[] args)
    {
        ArrayList<String> words = new ArrayList<String>();
        words.add("go");
        words.add("team");
        words.add("win");

        for (String word : words)
        {
            word = word.toUpperCase();
        }
        System.out.println(words);
    }
}

[go, team, win]

Nothing changed. On each pass, line 14 builds a new uppercase String (Strings are immutable, Topic 1.15) and stores its reference in word. The list still refers to the original lowercase strings; word was only a copy of the reference, so pointing it at a new string leaves the list’s slot alone. This matches the array rule from Topic 4.4.

To replace what is stored in the list, you need the slot’s index so you can call set. That calls for an indexed loop:

import java.util.ArrayList;

public class ShoutFixed
{
    public static void main(String[] args)
    {
        ArrayList<String> words = new ArrayList<String>();
        words.add("go");
        words.add("team");
        words.add("win");

        for (int i = 0; i < words.size(); i++)
        {
            words.set(i, words.get(i).toUpperCase());
        }
        System.out.println(words);
    }
}

[GO, TEAM, WIN]

Calling a method on the loop variable can change the object. When the list holds references to mutable objects, the loop variable refers to the very same object as the list does. They are aliases, as when a reference is passed to a method in Topic 3.6. Calling a mutator through the loop variable changes that shared object.

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.

import java.util.ArrayList;

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 = points + amount;
    }
}

public class TeamBonus
{
    public static void main(String[] args)
    {
        ArrayList<Player> team = new ArrayList<Player>();
        team.add(new Player("Ada", 10));
        team.add(new Player("Ben", 7));

        for (Player p : team)
        {
            p.addPoints(5);
        }

        for (Player p : team)
        {
            System.out.println(p.getName() + " " + p.getPoints());
        }
    }
}

Ada 15
Ben 12

import java.util.ArrayList;

public class DoubleLoopVar
{
    public static void main(String[] args)
    {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(4);
        nums.add(3);
        nums.add(5);

        for (int n : nums)
        {
            n = n * 2;
            System.out.println(n);
        }
        System.out.println(nums);
    }
}

8
6
10
[4, 3, 5]

A teacher keeps quiz scores in an ArrayList<Integer> and wants to drop every score below 70. In Topic 4.8 you removed one element at a known index with remove(i). Here the program has to look at each score and decide, so remove goes inside a traversal. The obvious loop looks right, compiles, and runs without crashing, yet it sometimes gives the wrong answer.

The problem comes from what remove does to the list, which you saw in Topic 4.8: every element after the removed one slides one place to the left, and size() drops by 1. So the element that was at index i + 1 is now at index i. If the loop then does i++, it moves on to index i + 1, and the element that just slid into index i is never checked. It has been skipped.

Picture a line of people being checked by a guard who steps forward one position after each check. If the person in front of the guard leaves, everyone behind shuffles forward. The guard still steps forward one place, so the person who shuffled into the spot in front of the guard is never checked.

import java.util.ArrayList;

public class RemoveSkip
{
    public static void main(String[] args)
    {
        ArrayList<Integer> scores = new ArrayList<Integer>();
        scores.add(85);
        scores.add(62);
        scores.add(58);
        scores.add(90);

        for (int i = 0; i < scores.size(); i++)
        {
            if (scores.get(i) < 70)
            {
                scores.remove(i);
            }
        }
        System.out.println(scores);
    }
}

[85, 58, 90]

There are two common ways to remove without skipping. Both make sure that every element is checked exactly once, even after a shift.

import java.util.ArrayList;

public class RemoveBackward
{
    public static void main(String[] args)
    {
        ArrayList<Integer> scores = new ArrayList<Integer>();
        scores.add(85);
        scores.add(62);
        scores.add(58);
        scores.add(90);

        for (int i = scores.size() - 1; i >= 0; i--)
        {
            if (scores.get(i) < 70)
            {
                scores.remove(i);
            }
        }
        System.out.println(scores);
    }
}

[85, 90]

import java.util.ArrayList;

public class RemoveStayPut
{
    public static void main(String[] args)
    {
        ArrayList<Integer> scores = new ArrayList<Integer>();
        scores.add(85);
        scores.add(62);
        scores.add(58);
        scores.add(90);

        int i = 0;
        while (i < scores.size())
        {
            if (scores.get(i) < 70)
            {
                scores.remove(i);
            }
            else
            {
                i++;
            }
        }
        System.out.println(scores);
    }
}

[85, 90]

import java.util.ArrayList;

public class WordsSkip
{
    public static void main(String[] args)
    {
        ArrayList<String> words = new ArrayList<String>();
        words.add("the");
        words.add("an");
        words.add("apple");
        words.add("of");
        words.add("pie");

        for (int i = 0; i < words.size(); i++)
        {
            if (words.get(i).length() < 4)
            {
                words.remove(i);
            }
        }
        System.out.println(words);
    }
}

[an, apple, pie]

import java.util.ArrayList;

public class WordsFixed
{
    public static void main(String[] args)
    {
        ArrayList<String> words = new ArrayList<String>();
        words.add("the");
        words.add("an");
        words.add("apple");
        words.add("of");
        words.add("pie");

        for (int i = words.size() - 1; i >= 0; i--)
        {
            if (words.get(i).length() < 4)
            {
                words.remove(i);
            }
        }
        System.out.println(words);
    }
}

An enhanced for loop would seem like a tidy way to remove items: “for each task, do it, then take it off the list.” But the enhanced for loop keeps track of where it is in the list behind the scenes, and it assumes the list keeps the same length for the whole traversal. If the loop body adds or removes an element, the loop’s idea of “the next element” no longer matches the real list.

Rather than quietly skipping or repeating elements, Java checks for this. When the enhanced for loop goes to fetch the next element and finds that the list’s size was changed during the traversal, it stops the program with a ConcurrentModificationException. “Concurrent modification” means the list was modified while it was being traversed.

import java.util.ArrayList;

public class TaskListCrash
{
    public static void main(String[] args)
    {
        ArrayList<String> tasks = new ArrayList<String>();
        tasks.add("email");
        tasks.add("laundry");
        tasks.add("homework");

        for (String task : tasks)
        {
            System.out.println("Done: " + task);
            tasks.remove(0);
        }
        System.out.println("All tasks finished");
    }
}

Done: email
Exception in thread "main" java.util.ConcurrentModificationException

import java.util.ArrayList;

public class TaskListFixed
{
    public static void main(String[] args)
    {
        ArrayList<String> tasks = new ArrayList<String>();
        tasks.add("email");
        tasks.add("laundry");
        tasks.add("homework");

        while (tasks.size() > 0)
        {
            System.out.println("Done: " + tasks.get(0));
            tasks.remove(0);
        }
        System.out.println("All tasks finished");
    }
}

Done: email
Done: laundry
Done: homework
All tasks finished

Adding is just as much of a problem as removing. Change one thing: the loop body adds an element instead of removing one.

import java.util.ArrayList;

public class CartAddCrash
{
    public static void main(String[] args)
    {
        ArrayList<String> cart = new ArrayList<String>();
        cart.add("milk");
        cart.add("eggs");
        cart.add("rice");

        for (String item : cart)
        {
            System.out.println(item);
            if (item.equals("milk"))
            {
                cart.add("cereal");
            }
        }
    }
}

import java.util.ArrayList;

public class CartAddFixed
{
    public static void main(String[] args)
    {
        ArrayList<String> cart = new ArrayList<String>();
        cart.add("milk");
        cart.add("eggs");
        cart.add("rice");

        for (int i = 0; i < cart.size(); i++)
        {
            System.out.println(cart.get(i));
            if (cart.get(i).equals("milk"))
            {
                cart.add("cereal");
            }
        }
    }
}

milk
eggs
rice
cereal

Java does not promise to catch every size change in an enhanced for loop; occasionally such a loop just ends early with no exception. You cannot count on either outcome, so the rule is simple.

import java.util.ArrayList;

public class GuestAdd
{
    public static void main(String[] args)
    {
        ArrayList<String> guests = new ArrayList<String>();
        guests.add("Ana");
        guests.add("Kim");
        guests.add("Lu");

        for (String guest : guests)
        {
            System.out.println(guest);
            if (guest.equals("Kim"))
            {
                guests.add("Kim's friend");
            }
        }
    }
}

A weather station records one temperature reading per hour in an ArrayList<Integer>. When the sensor fails, it records -999 instead of a real reading. This program prints the raw readings with their positions, removes every failed reading, and prints what is left. It uses three different traversals, each chosen for its job. Predict the output before reading the trace.

import java.util.ArrayList;

public class SensorCleanup
{
    public static void main(String[] args)
    {
        ArrayList<Integer> readings = new ArrayList<Integer>();
        readings.add(72);
        readings.add(-999);
        readings.add(-999);
        readings.add(68);
        readings.add(75);
        readings.add(-999);

        System.out.println("Raw readings:");
        for (int i = 0; i < readings.size(); i++)
        {
            System.out.println(i + ": " + readings.get(i));
        }

        for (int i = readings.size() - 1; i >= 0; i--)
        {
            if (readings.get(i) == -999)
            {
                readings.remove(i);
            }
        }

        System.out.println("Clean readings:");
        for (int reading : readings)
        {
            System.out.println(reading);
        }
        System.out.println("Readings kept: " + readings.size());
    }
}

Raw readings:
0: 72
1: -999
2: -999
3: 68
4: 75
5: -999
Clean readings:
72
68
75
Readings kept: 3

• Traversing an ArrayList by index works like traversing an array, with size() in place of .length and get(i) in place of [i]. Changing the start, test, and update lets a for or while loop go backward or visit only some elements.
• Valid indices run from 0 to size() - 1. Using size() itself, or any other index outside that range, throws an IndexOutOfBoundsException at run time.
• An enhanced for loop visits every element front to back with no index. Its variable holds a copy of each element: assigning to it never changes the list, but calling a mutator through it changes the shared object.
• Removing at index i slides later elements left, so a forward loop that always does i++ skips elements. Traverse backward, or advance only when nothing was removed.
• Adding or removing elements inside an enhanced for loop can throw a ConcurrentModificationException. When the size will change, use an indexed for loop or a while loop.

import java.util.ArrayList;

public class BackStopsA
{
    public static void main(String[] args)
    {
        ArrayList<String> stops = new ArrayList<String>();
        stops.add("Main");
        stops.add("Oak");
        stops.add("Pine");

        for (int i = stops.size() - 1; i >= 0; i--)
        {
            System.out.println(stops.get(i));
        }
    }
}

import java.util.ArrayList;

public class SeatsSkip
{
    public static void main(String[] args)
    {
        ArrayList<String> seats = new ArrayList<String>();
        seats.add("x");
        seats.add("x");
        seats.add("Ana");
        seats.add("x");
        seats.add("Bo");

        for (int i = 0; i < seats.size(); i++)
        {
            if (seats.get(i).equals("x"))
            {
                seats.remove(i);
            }
        }
        System.out.println(seats);
    }
}

[x, Ana, Bo]

import java.util.ArrayList;

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 = points + amount;
    }
}

public class TeamReset
{
    public static void main(String[] args)
    {
        ArrayList<Player> team = new ArrayList<Player>();
        team.add(new Player("Ada", 10));
        team.add(new Player("Ben", 7));

        for (Player p : team)
        {
            p = new Player(p.getName(), 0);
        }

        for (Player p : team)
        {
            p.addPoints(2);
        }

        for (Player p : team)
        {
            System.out.println(p.getName() + " " + p.getPoints());
        }
    }
}

import java.util.ArrayList;

public class ScoresEnhancedRemove
{
    public static void main(String[] args)
    {
        ArrayList<Integer> scores = new ArrayList<Integer>();
        scores.add(85);
        scores.add(62);
        scores.add(90);
        scores.add(77);

        int index = 0;
        for (int score : scores)
        {
            if (score < 70)
            {
                scores.remove(index);
            }
            index++;
        }
        System.out.println(scores);
    }
}

import java.util.ArrayList;

public class ScoresEnhancedFixed
{
    public static void main(String[] args)
    {
        ArrayList<Integer> scores = new ArrayList<Integer>();
        scores.add(85);
        scores.add(62);
        scores.add(90);
        scores.add(77);

        for (int i = scores.size() - 1; i >= 0; i--)
        {
            if (scores.get(i) < 70)
            {
                scores.remove(i);
            }
        }
        System.out.println(scores);
    }
}

Check each statement. If the answer is “not yet,” reread the linked subsection.

• I can traverse an ArrayList with an indexed for loop or a while loop, forward, backward, or by steps. Reread
• I can explain why an index of size() or more causes an IndexOutOfBoundsException, and fix the loop. Reread
• I can traverse an ArrayList with an enhanced for loop and say when it can and cannot change the list. Reread
• I can explain why a forward loop skips elements when removing, and remove without skipping. Reread
• I can explain why adding or removing in an enhanced for loop can cause a ConcurrentModificationException. Reread