4.9 ArrayList Traversals

1. Traversing an ArrayList

Traversing an ArrayList means using iteration (loops) or recursive statements to access all of the elements, or an ordered sequence of them 4.9.A.1. The loops look like array loops with two changes: size() instead of length, and get(i) instead of [i].

ArrayList<Integer> steps = new ArrayList<Integer>();
steps.add(5200);
steps.add(8100);
steps.add(7400);

for (int i = 0; i < steps.size(); i++)          // indexed for
{
    System.out.print(steps.get(i) + " ");
}
System.out.println();

int total = 0;
for (int s : steps)                             // enhanced for (unboxing to int)
{
    total += s;
}
System.out.println("Total: " + total);

int k = steps.size() - 1;                       // while, backward
while (k >= 0)
{
    System.out.print(steps.get(k) + " ");
    k--;
}
System.out.println();

Output:

5200 8100 7400 
Total: 20700
7400 8100 5200 

To change elements, use set in an indexed loop (assigning to the enhanced for loop variable changes nothing, as with arrays):

ArrayList<String> tags = new ArrayList<String>();
tags.add("java");
tags.add("loop");

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

Output:

[#java, #loop]

Preview: a traversal can also be recursive: a method handles one element and then calls itself for the rest. Recursion is covered in topic 4.16; here is a small example to trace.

public static void printFrom(ArrayList<String> list, int index)
{
    if (index < list.size())
    {
        System.out.print(list.get(index) + " ");
        printFrom(list, index + 1);
    }
}

ArrayList<String> stops = new ArrayList<String>();
stops.add("Park");
stops.add("Museum");
stops.add("Harbor");
printFrom(stops, 0);
System.out.println();

Output:

Park Museum Harbor 

2. Removing during a traversal: the skipping bug

Deleting elements during a traversal of an ArrayList requires special techniques to avoid skipping elements 4.9.A.2. The reason: remove(i) shifts every later element one place left, so the next element moves into index i. If the loop then does i++, that element is never checked.

Goal: remove every score below 50.

ArrayList<Integer> scores = new ArrayList<Integer>();
scores.add(72);
scores.add(40);
scores.add(35);
scores.add(90);

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

Output:

[72, 35, 90]

35 survived. Trace it:

i	list at the start of the pass	get(i)	action
0	[72, 40, 35, 90]	72	keep
1	[72, 40, 35, 90]	40	remove(1); 35 shifts to index 1
2	[72, 35, 90]	90	keep (35, now at index 1, was skipped)

3. Two safe ways to remove

Technique 1: only move forward when nothing was removed.

ArrayList<Integer> scores = new ArrayList<Integer>();
scores.add(72);
scores.add(40);
scores.add(35);
scores.add(90);

int i = 0;
while (i < scores.size())
{
    if (scores.get(i) < 50)
    {
        scores.remove(i);       // the next element is now at index i: check it next
    }
    else
    {
        i++;
    }
}
System.out.println(scores);

Output:

[72, 90]

(The same idea in a for loop is to write i--; right after remove(i), so the i++ in the header cancels it out.)

Technique 2: traverse backward. Removing at index i only shifts elements after i, and a backward loop has already checked those.

ArrayList<Integer> scores = new ArrayList<Integer>();
scores.add(72);
scores.add(40);
scores.add(35);
scores.add(90);

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

Output:

[72, 90]

i	list at the start of the pass	get(i)	action
3	[72, 40, 35, 90]	90	keep
2	[72, 40, 35, 90]	35	remove(2)
1	[72, 40, 90]	40	remove(1)
0	[72, 90]	72	keep

4. Adding during a traversal

Adding has the opposite shift. add(i, obj) pushes the current element to index i + 1, so a forward loop meets it again on the next pass. Goal: put a “warm up” before every “run”.

ArrayList<String> plan = new ArrayList<String>();
plan.add("run");
plan.add("rest");
plan.add("run");

for (int i = 0; i < plan.size(); i++)
{
    if (plan.get(i).equals("run"))
    {
        plan.add(i, "warm up");
        i++;                    // skip past the "run" that just moved to i + 1
    }
}
System.out.println(plan);

Output:

[warm up, run, rest, warm up, run]

Without the extra i++, the loop would find the same “run” at index i + 1, insert again, and keep going until the program runs out of memory.

5. IndexOutOfBoundsException

Attempting to access an index value outside the range 0 to size() - 1 results in an IndexOutOfBoundsException 4.9.A.3. Two ways it happens in traversals:

ArrayList<String> names = new ArrayList<String>();
names.add("Ada");
names.add("Ben");

for (int i = 0; i <= names.size(); i++)        // <= is one pass too many
{
    System.out.println(names.get(i));
}

Output:

Ada
Ben
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 2 out of bounds for length 2

Saving the size in a variable before a loop that removes elements also fails, because the list gets shorter but the saved number does not:

ArrayList<Integer> nums = new ArrayList<Integer>();
nums.add(4);
nums.add(-1);
nums.add(6);

int n = nums.size();                            // 3, and it stays 3
for (int i = 0; i < n; i++)
{
    if (nums.get(i) < 0)
    {
        nums.remove(i);
    }
}
System.out.println(nums);

Output:

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 2 out of bounds for length 2

i	list at the start of the pass	get(i)	action
0	[4, -1, 6]	4	keep
1	[4, -1, 6]	-1	remove(1); the size is now 2
2	[4, 6]	get(2)	exception: n is still 3, but index 2 no longer exists

Write i < nums.size() in the condition so the loop sees the current size (and combine it with a technique from section 3).

6. ConcurrentModificationException

Changing the size of an ArrayList while traversing it with an enhanced for loop can result in a ConcurrentModificationException 4.9.A.4. So when you use an enhanced for loop on an ArrayList, you should not add or remove elements 4.9.A.4.

ArrayList<String> cart = new ArrayList<String>();
cart.add("apple");
cart.add("soda");
cart.add("bread");
cart.add("soda");

for (String item : cart)
{
    if (item.equals("soda"))
    {
        cart.remove(1);
    }
}
System.out.println(cart);

Output:

Exception in thread "main" java.util.ConcurrentModificationException

The code compiles; the exception happens when the loop tries to move to the next element after the list has changed size. Adding inside an enhanced for loop fails the same way. Use one of the indexed techniques from section 3 instead.

Loop type	Read elements	Replace with set	Remove or add
indexed for / while	yes	yes	yes, with a special technique
enhanced for	yes	no (no index)	no: ConcurrentModificationException