Unit 4.9: ArrayList Traversal

Traversing an ArrayList

Traversing an ArrayList occurs when iteration or recursive statements are used to access all or an ordered sequence of the elements in an ArrayList.

Task: Traversing an ArrayList using both indexed and enhanced for loops.

import java.util.ArrayList;

public class TraversalExample 
{
    public static void main(String[] args) 
    {
        ArrayList<String> fruits = new ArrayList<String>();
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Cherry");

        // Traversal with an indexed for loop
        for (int i = 0; i < fruits.size(); i++) 
        {
            System.out.println(fruits.get(i));
        }

        // Traversal with an enhanced for loop
        for (String fruit : fruits) 
        {
            System.out.println(fruit);
        }
    }
}

Deleting Elements During Traversal

Deleting elements during a traversal of an ArrayList requires the use of special techniques to avoid skipping elements. Because ArrayList indices shift left immediately after a removal, a standard forward-moving loop will skip the element that moves into the current index.

Task: Demonstrating the logic error when removing elements during a forward traversal.

// UNSAFE: Standard forward loop
// If list is ["A", "B", "B", "C"], this will result in ["A", "B", "C"]
for (int i = 0; i < list.size(); i++) 
{
    if (list.get(i).equals("B")) 
    {
        list.remove(i); // Logic error: The second "B" shifts to index i and is skipped
    }
}

Common Techniques for Safe Removal

1. Backward Traversal: Start from size() - 1 and move toward index 0. Shifting only affects indices higher than the current i, which have already been processed.
2. Manual Index Adjustment: In a forward loop, decrement the index variable (i--) immediately after a removal.

Task: Safely removing elements using a backward traversal.

ArrayList<String> list = new ArrayList<>();
list.add("A"); list.add("B"); list.add("B"); list.add("C");

// SAFE: Backward Traversal
for (int i = list.size() - 1; i >= 0; i--) 
{
    if (list.get(i).equals("B")) 
    {
        list.remove(i);
    }
}

Task: Safely removing elements in a forward loop with manual index adjustment.

// SAFE: Forward with index adjustment
for (int i = 0; i < list.size(); i++) 
{
    if (list.get(i).equals("B")) 
    {
        list.remove(i);
        i--; // Adjust index to check the new element at this position
    }
}

IndexOutOfBoundsException

Attempting to access an index value outside of its range (0 to size() - 1) will result in an IndexOutOfBoundsException.

Task: Attempting to access an invalid index in an ArrayList.

ArrayList<Integer> nums = new ArrayList<>();
nums.add(5);
// System.out.println(nums.get(1)); // RUN-TIME ERROR: IndexOutOfBoundsException

ConcurrentModificationException

Changing the size of an ArrayList (by adding or removing elements) while traversing it using an enhanced for loop can result in a ConcurrentModificationException.

Task: Attempting to modify the size of a list during an enhanced for loop traversal.

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

// DANGEROUS: This will throw ConcurrentModificationException
// because the list size is modified while the enhanced for loop
// is using an internal iterator to traverse it.
for (String name : names) 
{
    if (name.equals("Alice")) 
    {
        names.add("Charlie"); // ERROR: Structural modification
    }
}