ArrayList Traversals - AP Computer Science A Study Guide

Getting Started

Once we have a collection of data stored in an ArrayList, a fundamental task is to access each item within it. Whether we need to print every value, search for a specific item, or calculate a total, we need a systematic way to visit every element. This process, known as traversal, is a cornerstone of working with any data structure in Java.

What You Should Be Able to Do

• Implement a standard for loop using an index to access every element in an ArrayList.

• Implement an enhanced for loop (for-each loop) to access every element in an ArrayList.

• Identify loop conditions that can cause an IndexOutOfBoundsException.

• Explain the consequences of adding or removing elements from an ArrayList while traversing it.

• Write code that safely removes elements from an ArrayList during a traversal.

Key Concepts & Java Implementation

The Core Idea

Traversal is the process of systematically visiting, or iterating over, each element in a collection. For an ArrayList, which is an ordered list, this typically means starting with the element at the first position (index 0) and proceeding sequentially until the last element has been accessed.

This operation is essential for many common algorithms. For example, to find the highest score in a list of grades, you must traverse the list, examining each grade one by one. To print a list of contacts, you must traverse the list and print each name. Java provides two primary loop structures for traversing an ArrayList: the indexed for loop and the enhanced for loop.

Syntax & Implementation

There are two standard ways to traverse an ArrayList. The method you choose depends on whether you need access to the element's index.

Method 1: The Indexed for Loop

This is the traditional way to loop through an ordered list. It uses a counter variable, called an index, to keep track of the current position. You use the ArrayList's .get(index) method to retrieve the element at each position. This loop gives you full control, which is especially important if you need to modify the list during traversal.

An index is an integer that specifies an element's position in an ordered list. In Java, indexing starts at 0.

// Create and populate an ArrayList of student names.

ArrayList<String> students = new ArrayList<String>();

students.add("Alice");

students.add("Bob");

students.add("Charlie");


// Traverse the list using an indexed for loop.

// The loop runs as long as the index 'i' is less than the list's size.

System.out.println("Student Roster:");

for (int i = 0; i < students.size(); i++) {

    // Get the element at the current index 'i'.

    String name = students.get(i);

    // Print the element.

    System.out.println((i + 1) + ". " + name);

}

Method 2: The Enhanced for Loop (For-Each Loop)

When you only need to access each element and do not need its index, the enhanced for loop provides a cleaner, more readable syntax. It iterates over each item in the collection directly, assigning it to a temporary variable you declare.

This loop is best for "read-only" operations like printing, searching, or performing calculations where the element's position doesn't matter.

// Create and populate an ArrayList of scores.

ArrayList<Integer> scores = new ArrayList<Integer>();

scores.add(95);

scores.add(88);

scores.add(72);

scores.add(100);


// Traverse the list using an enhanced for loop.

int sum = 0;

// For each 'score' of type Integer in the 'scores' list...

for (Integer score : scores) {

    // The 'score' variable holds the current element.

    sum += score;

}


System.out.println("The sum of all scores is: " + sum);

Tracing & Analysis

Execution Trace

Let's trace the execution of an indexed for loop to see how the variables change.

Code:

ArrayList<Integer> numbers = new ArrayList<Integer>();

numbers.add(10);

numbers.add(20);

numbers.add(30);

for (int i = 0; i < numbers.size(); i++) {

    System.out.println(numbers.get(i));

}

Trace Table:

Analysis: Modifying During Traversal

Modifying an ArrayList while traversing it can lead to unexpected behavior or errors.

1. Removing with an Indexed for Loop: If you remove an element, all subsequent elements shift to the left, and the list's size decreases. If you simply let the loop increment the index (i++), you will skip the element that shifted into the current position.

   The Solution: When you remove an element at index i, you must also decrement i to ensure the next loop iteration re-evaluates the element that just shifted into the current position.

   
   ArrayList<String> words = new ArrayList<String>();
   
   words.add("apple");
   
   words.add("banana"); // This will be removed
   
   words.add("cherry");
   
   words.add("date");
   
   
   // Remove all words of length 6.
   
   for (int i = 0; i < words.size(); i++) {
   
       if (words.get(i).length() == 6) {
   
           words.remove(i);
   
           i--; // IMPORTANT: Decrement index to re-check this position.
   
       }
   
   }
   
   // Final list: ["apple", "cherry", "date"]
   

2. Modifying with an Enhanced for Loop: You should not add or remove elements from an ArrayList when traversing it with an enhanced for loop. Doing so will throw a ConcurrentModificationException, which is a runtime error indicating that the collection was changed improperly during iteration.

Java Syntax Quick-Reference

A summary of the key syntax used for ArrayList traversals.

Core Code Examples & Terminology

• Traversal: The process of accessing each element in a collection, typically in a sequential order, to perform an operation.

• Index: An integer value that specifies the position of an element within an ordered collection like an ArrayList, starting from 0 for the first element.

• IndexOutOfBoundsException: A runtime error that occurs when a program attempts to access an element at an index that is outside the valid range (i.e., less than 0 or greater than or equal to the list's size).

• Core Snippet 1 (Indexed for Loop Traversal):

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

  This loop uses an integer index i to access each element of myList by its position.

• Core Snippet 2 (Enhanced for Loop Traversal):

  
  for (String item : myStringList) {
  
      System.out.println(item);
  
  }
  

  This loop iterates through each String in myStringList without using an index.

• Core Snippet 3 (Safe Removal During Traversal):

  
  for (int i = 0; i < scores.size(); i++) {
  
      if (scores.get(i) < 60) {
  
          scores.remove(i);
  
          i--; // Adjust index to prevent skipping the next element.
  
      }
  
  }
  

  This loop safely removes failing scores by decrementing the index after each removal.

Core Skill Check

• Code Tracing: What is the final value of total after this Java code runs: ArrayList<Integer> vals = new ArrayList<>(); vals.add(5); vals.add(10); vals.add(2); int total = 0; for (int v : vals) { total += v; }?

• Debugging: Identify the runtime error in this Java code: ArrayList<String> names = new ArrayList<>(); names.add("A"); names.add("B"); for (int i = 0; i <= names.size(); i++) { System.out.println(names.get(i)); }.

• Application: Write a single line of Java code that gets the last element of an ArrayList named items, assuming it is not empty.

Common Misconceptions & Errors

• Off-by-One Errors: Using i <= list.size() as the condition in an indexed for loop. The last valid index is list.size() - 1, so accessing list.get(list.size()) will always cause an IndexOutOfBoundsException. The correct condition is i < list.size().

• Forgetting to Adjust Index After Removal: When removing an element from an ArrayList inside an indexed for loop, failing to decrement the index (i--) will cause the loop to skip over the element that shifts into the now-vacant spot.

• Modifying with an Enhanced for Loop: Attempting to call .add() or .remove() on an ArrayList from within an enhanced for loop that is iterating over it. This is not permitted and will result in a ConcurrentModificationException.

• Assuming the Enhanced Loop Provides an Index: The enhanced for loop abstracts away the index. The loop variable holds the element itself, not its position. If you need the index, you must use a standard indexed for loop.

Summary

Traversing an ArrayList is a fundamental operation for accessing and processing its elements. Java offers two primary methods for this task. The indexed for loop provides fine-grained control by using an integer index to access elements with .get(), making it suitable for situations where the element's position is important or when the list must be modified during traversal. The enhanced for loop (for-each loop) offers a more concise and readable syntax for read-only access when the index is not needed. Understanding the correct use of each loop, especially the rules for modifying a list during iteration, is crucial for writing correct and robust code that avoids common runtime errors like IndexOutOfBoundsException and ConcurrentModificationException.