Introduction

Just as we traverse arrays to process elements systematically, we must traverse ArrayLists. However, ArrayLists introduce special considerations—particularly when adding or removing elements during traversal. Topic 4.9 covers ArrayList traversal techniques and the pitfalls to avoid.

Traversing an ArrayList is when iteration or recursive statements are used to access all or an ordered sequence of the elements in an ArrayList. While traversal patterns mirror array traversal, the dynamic nature of ArrayLists creates unique challenges, especially with modification during iteration.

Basic Traversal: Indexed For Loop

Standard pattern using indices:

Key points:

Example: Doubling All Values

ArrayList<Integer> values = new ArrayList<Integer>();
values.add(5);
values.add(10);
values.add(15);

for (int i = 0; i < values.size(); i++) 
{
    values.set(i, values.get(i) * 2);
}
// [10, 20, 30]

Enhanced For Loop Traversal

Simpler syntax when you don't need indices:

ArrayList<String> names = new ArrayList<String>();
names.add("Alice");
names.add("Bob");
names.add("Charlie");

for (String name : names) 
{
    System.out.println(name);
}

Limitation: Cannot modify the ArrayList structure (add/remove) during enhanced for loop.

IndexOutOfBoundsException

Attempting to access an index value outside of its range will result in an IndexOutOfBoundsException.

IndexOutOfBoundsException.
ArrayList<Integer> nums = new ArrayList<Integer>();
nums.add(10);
nums.add(20);
// Valid indices: 0, 1

nums.get(2);   // ERROR: index 2 doesn't exist
nums.get(-1);  // ERROR: negative index

Common causes:

Modifying ArrayLists During Traversal

Deleting elements during a traversal of an ArrayList requires the use of special techniques to avoid skipping elements.

The Problem: Skipping Elements

// WRONG - skips elements!
ArrayList<Integer> nums = new ArrayList<Integer>();
nums.add(1);
nums.add(2);
nums.add(3);
nums.add(4);

for (int i = 0; i < nums.size(); i++) 
{
    if (nums.get(i) % 2 == 0) 
    {
        nums.remove(i);  // Problem: elements shift!
    }
}

What happens:

Solution 1: Traverse Backwards

// CORRECT - traverse backwards
for (int i = nums.size() - 1; i >= 0; i--) 
{
    if (nums.get(i) % 2 == 0) 
    {
        nums.remove(i);
    }
}

Why this works: Removing elements only affects indices to the right, which we've already processed.

Solution 2: Decrement After Removal

// CORRECT - adjust index after removal
for (int i = 0; i < nums.size(); i++) 
{
    if (nums.get(i) % 2 == 0) 
    {
        nums.remove(i);
        i--;  // Check same index again
    }
}

Why this works: Decrementing i counteracts the automatic increment, so we check the same index again (which now contains the next element).

ConcurrentModificationException

Changing the size of an ArrayList while traversing it using an enhanced for loop can result in a ConcurrentModificationException.

Therefore, when using an enhanced for loop to traverse an ArrayList, you should not add or remove elements.

ArrayList<Integer> numbers = new ArrayList<Integer>();
numbers.add(10);
numbers.add(20);
numbers.add(30);

// WRONG - throws ConcurrentModificationException
for (Integer num : numbers) 
{
    if (num == 20) 
    {
        numbers.remove(num);  // ERROR!
    }
}

Why? The enhanced for loop maintains an internal counter. Modifying the ArrayList structure invalidates this counter, causing the exception.

Solution: Use indexed loop instead:

for (int i = numbers.size() - 1; i >= 0; i--) 
    {
    if (numbers.get(i) == 20) 
    {
        numbers.remove(i);  // OK with indexed loop
    }
}

Safe Modification Patterns

Pattern 1: Backwards Traversal for Removal

ArrayList<String> words = new ArrayList<String>();
words.add("apple");
words.add("banana");
words.add("apricot");
words.add("cherry");

// Remove all words starting with 'a'
for (int i = words.size() - 1; i >= 0; i--) 
{
    if (words.get(i).charAt(0) == 'a') 
    {
        words.remove(i);
    }
}
// Result: ["banana", "cherry"]

Pattern 2: Building New ArrayList

ArrayList<Integer> original = new ArrayList<Integer>();
original.add(5);
original.add(10);
original.add(15);
original.add(20);

// Keep only values > 10
ArrayList<Integer> filtered = new ArrayList<Integer>();
for (Integer num : original) // Safe - not modifying original
{  
    if (num > 10) 
    {
        filtered.add(num);
    }
}
// filtered: [15, 20]

Pattern 3: Inserting Elements

When inserting during traversal:

ArrayList<Integer> nums = new ArrayList<Integer>();
nums.add(1);
nums.add(3);
nums.add(5);

// Insert 0 before each element
for (int i = 0; i < nums.size(); i += 2) 
{
    nums.add(i, 0);
}
// Result: [0, 1, 0, 3, 0, 5]

Note: Increment by 2 to skip inserted elements.

Common Traversal Algorithms

Finding Maximum

ArrayList<Integer> scores = new ArrayList<Integer>();
scores.add(85);
scores.add(92);
scores.add(78);

int max = scores.get(0);
for (int i = 1; i < scores.size(); i++) 
{
    if (scores.get(i) > max) 
    {
        max = scores.get(i);
    }
}
System.out.println("Max: " + max);  // 92

Calculating Sum

ArrayList<Double> prices = new ArrayList<Double>();
prices.add(19.99);
prices.add(25.50);
prices.add(10.00);

double total = 0.0;
for (Double price : prices) 
{
    total += price;
}
System.out.println("Total: " + total);  // 55.49

Counting with Condition

ArrayList<String> words = new ArrayList<String>();
words.add("apple");
words.add("banana");
words.add("apricot");

int count = 0;
for (String word : words) 
{
    if (word.startsWith("a")) 
    {
        count++;
    }
}
System.out.println("Words starting with 'a': " + count);  // 2

Practice Problems