Implementing ArrayList Algorithms - AP Computer Science A Study Guide

Getting Started

The ArrayList class provides a powerful way to manage dynamic collections of objects, where the size can grow or shrink as needed. However, simply storing data is not enough; we need to process it. This chapter focuses on implementing standard algorithms—step-by-step procedures—to traverse, search, summarize, and modify the data held within an ArrayList.

What You Should Be Able to Do

• Implement a traversal of an ArrayList using both an index-based for loop and an enhanced for loop.

• Write algorithms to compute the sum or find the minimum/maximum value in an ArrayList.

• Write code to insert or remove elements from an ArrayList based on specific criteria.

• Analyze and correct the common logical error that occurs when removing elements from an ArrayList during a forward traversal.

Key Concepts & Java Implementation

The Core Idea

An algorithm is a finite sequence of well-defined instructions to solve a problem. When working with an ArrayList, common problems include finding a specific item, calculating a total, or filtering the list to keep only certain elements.

The foundation for nearly all ArrayList algorithms is traversal, which is the process of systematically visiting, or accessing, each element in the list one by one. By traversing a list, we can inspect each element and decide whether to include it in a calculation, modify it, or remove it. The two primary methods for traversal in Java are the index-based for loop and the enhanced for loop.

Syntax & Implementation

Traversal

There are two main ways to loop through every element in an ArrayList. The one you choose depends on whether you need access to the element's index.

1. Enhanced for Loop (Read-Only Access)

Use this loop when you only need to access each element's value, not its position (index). It is simpler and less prone to error.

import java.util.ArrayList;


public class TraversalExample {

    public static void main(String[] args) {

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

        names.add("Alice");

        names.add("Bob");

        names.add("Charlie");


        // Enhanced for loop to print each name

        for (String name : names) {

            System.out.println(name);

        }

    }

}

2. Index-Based for Loop (Full Access & Modification)

Use this loop when you need the index of each element, which is essential for tasks like inserting or removing elements during the traversal.

import java.util.ArrayList;


public class TraversalExample2 {

    public static void main(String[] args) {

        ArrayList<Double> grades = new ArrayList<Double>();

        grades.add(98.5);

        grades.add(89.0);

        grades.add(72.7);


        // Index-based for loop to print each grade with its index

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

            // .get(i) retrieves the element at index i

            System.out.println("Element at index " + i + ": " + grades.get(i));

        }

    }

}

Standard Algorithms

Many algorithms follow a similar pattern: initialize a variable, traverse the list, and update the variable at each step.

Example: Calculating the Sum

This algorithm finds the sum of all numbers in an ArrayList of Integer objects.

import java.util.ArrayList;


public class AlgorithmSum {

    public static int getSum(ArrayList<Integer> numbers) {

        int sum = 0; // 1. Initialize a result variable

        

        // 2. Traverse the list

        for (Integer num : numbers) {

            sum = sum + num; // 3. Update the result with each element

        }

        

        return sum; // 4. Return the final result

    }


    public static void main(String[] args) {

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

        myNumbers.add(10);

        myNumbers.add(20);

        myNumbers.add(30);

        System.out.println("The sum is: " + getSum(myNumbers)); // Output: The sum is: 60

    }

}

Modifying an ArrayList During Traversal

Removing elements while traversing is a common task, but it contains a significant pitfall. If you traverse forward and remove an element, all subsequent elements shift to the left, changing their indices. This can cause your loop to "skip" the element that shifts into the current position.

Tracing & Analysis

The Problem: Skipping Elements

Consider this code that tries to remove all odd numbers from a list.

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

nums.add(1);

nums.add(7); // This element will be skipped!

nums.add(4);

nums.add(8);


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

    if (nums.get(i) % 2 != 0) { // If the number is odd...

        nums.remove(i); // ...remove it.

    }

}

// Final state of nums: [7, 4, 8] -> Incorrect!

Execution Trace:

Analysis:

When i is 0, the element 1 is removed. The ArrayList immediately shifts: 7 moves to index 0, 4 moves to index 1, and 8 moves to index 2. The loop then increments i to 1. It proceeds to check the element now at index 1, which is 4. The element 7 (which moved into the spot just vacated) was never checked.

The Solution: Decrement the Index

To fix this, if you remove an element at index i, you must also decrement i so that the next loop iteration re-evaluates the element that shifted into the current position.

import java.util.ArrayList;


public class RemovalSolution {

    public static void main(String[] args) {

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

        nums.add(1);

        nums.add(7);

        nums.add(4);

        nums.add(8);


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

            if (nums.get(i) % 2 != 0) {

                nums.remove(i);

                i--; // Decrement i to re-check the current index

            }

        }

        System.out.println(nums); // Output: [4, 8] -> Correct!

    }

}

Java Syntax Quick-Reference

A compact reference for the ArrayList methods and loop structures used in these algorithms.

Core Code Examples & Terminology

• ArrayList: A class in java.util that provides a resizable-array implementation. It can dynamically grow and shrink to accommodate its elements.

• Traversal: The process of systematically visiting each element in a data structure, typically with a loop, to inspect or operate on it.

• Algorithm: A well-defined, step-by-step procedure for solving a computational problem, such as finding the maximum value in a list.

• Core Snippet 1 (Enhanced for loop):

  
  // Prints every item in a list of Strings
  
  for (String item : shoppingList) {
  
      System.out.println(item);
  
  }
  

  This loop provides a simple, readable way to access every element when the index is not needed.

• Core Snippet 2 (Finding a Minimum Value):

  
  // Finds the minimum value in a non-empty list of Integers
  
  int minVal = numbers.get(0);
  
  for (int i = 1; i < numbers.size(); i++) {
  
      if (numbers.get(i) < minVal) {
  
          minVal = numbers.get(i);
  
      }
  
  }
  

  This algorithm initializes the minimum with the first element and then traverses the rest of the list, updating the minimum whenever a smaller value is found.

• Core Snippet 3 (Correct Element Removal):

  
  // Removes all elements with a value of zero
  
  for (int i = 0; i < data.size(); i++) {
  
      if (data.get(i) == 0) {
  
          data.remove(i);
  
          i--; // Prevents skipping the next element
  
      }
  
  }
  

  This loop correctly removes elements by decrementing the loop counter i immediately after a removal.

Core Skill Check

• Code Tracing: What is the final value of count after this Java code runs?

  ArrayList<Integer> vals = new ArrayList<>(); vals.add(5); vals.add(10); vals.add(5); int count = 0; for(Integer v : vals) { if(v == 5) { count++; } }

  Answer: 2

• Debugging: Identify the logical error in this Java code intended to remove all strings of length 3.

  ArrayList<String> words = new ArrayList<>(); words.add("a"); words.add("cat"); words.add("dog"); words.add("ox"); for(int i=0; i<words.size(); i++) { if(words.get(i).length() == 3) { words.remove(i); } }

  Answer: The code will skip the string "dog". After "cat" is removed at index 1, "dog" shifts to index 1, but the loop proceeds to i=2, missing it.

• Application: Write a single line of Java code that adds the string "apple" to the beginning of an ArrayList named fruits.

  Answer: fruits.add(0, "apple");

Common Misconceptions & Errors

• Off-by-One Errors: Using i <= list.size() in an index-based for loop condition will cause an IndexOutOfBoundsException because the valid indices are from 0 to list.size() - 1. Always use i < list.size().

• Skipping Elements on Removal: The most common logical error. Forgetting to decrement the loop counter (i--) after removing an element in a forward for loop will cause the loop to skip over the element that shifts into the now-empty spot.

• Modifying with an Enhanced for Loop: You should not add or remove elements from an ArrayList while traversing it with an enhanced for loop. Doing so will result in a ConcurrentModificationException at runtime. Use an index-based for loop for modifications.

• Forgetting to Import: Using ArrayList requires the statement import java.util.ArrayList; at the top of your Java file. Forgetting it will cause a compile-time error.

Summary

Implementing algorithms for ArrayLists is a fundamental skill in Java programming. The core of most algorithms is traversal, which can be done with an enhanced for loop for simple access or an index-based for loop when the element's position is needed. Standard algorithms for finding sums, averages, or minimums/maximums follow a predictable pattern of initializing a variable and updating it within a loop. The most critical concept is handling modifications during traversal. When removing elements using a forward, index-based loop, you must decrement the loop counter after each removal to prevent skipping elements as the list shifts. Mastering this pattern is key to writing correct and robust ArrayList code.