Implementing ArrayList Algorithms

Alright, let's dive into the common recipes, or algorithms, you'll use with ArrayLists. Almost all of them start with the same basic idea: a traversal. A traversal is just a fancy word for visiting every element in the list, usually with a for loop or a for-each loop.

Think of it like walking down a line of lockers. You start at the first one and check each one until you reach the end. What you do at each locker is what defines the algorithm.

"Read-Only" Algorithms: Just Looking

These algorithms inspect the data in the ArrayList without changing it.

Finding a Minimum or Maximum Value

Let's say you have an ArrayList of high scores from an arcade game. How do you find the highest one?

You can't just assume the max score is 0. What if all the scores are negative? (Tough game!) The safest way is to assume the first element is the maximum, and then challenge that assumption as you loop through the rest.

// Finds the highest score in a list of integers
public int findMax(ArrayList<Integer> scores) {
    // 1. Assume the first score is the highest
    int maxScore = scores.get(0);

    // 2. Loop through the rest of the list
    for (int i = 1; i < scores.size(); i++) {
        // 3. If we find a higher score, update our max
        if (scores.get(i) > maxScore) {
            maxScore = scores.get(i);
        }
    }
    return maxScore;
}

Finding the minimum is the exact same logic, just with the > flipped to a <.

Computing a Sum or Average

To get the sum, you initialize a counter to zero, loop through the list, and add each element's value to your counter.

To get the average, you first find the sum, then divide by the total number of elements (list.size()).

// Calculates the average of a list of numbers
public double calculateAverage(ArrayList<Integer> nums) {
    double sum = 0.0; // Use a double for the sum to avoid integer division later
    for (int num : nums) {
        sum += num;
    }

    if (nums.size() == 0) {
        return 0.0; // Avoid dividing by zero!
    }

    return sum / nums.size(); // double / int = double
}

Checking for Properties

Sometimes you just need a yes/no answer about the list.

• Does at least one element have a property?
  (e.g., "Is there at least one failing grade?")

  • Start with a boolean flag set to false.
  • Loop through the list. If you find an element that meets the condition, set the flag to true and you can break out of the loop immediately. There's no need to keep looking.
• Do all elements have a property?
  (e.g., "Are all temperatures above freezing?")

  • This one is a bit counter-intuitive. Start by assuming the answer is true.
  • Loop through the list looking for a counterexample—any one element that fails the condition.
  • If you find one, you can immediately set your flag to false and break.

"Read-Write" Algorithms: Changing the List

These algorithms modify the ArrayList by adding, removing, or reordering elements. This is where things get tricky.

An ArrayList is like a tightly packed line of people. If someone in the middle leaves, everyone behind them has to take one step forward to fill the gap. This changes their position, or index.

Deleting Elements

If you loop forwards while removing elements, you'll skip items! Imagine you remove the element at index 3. The element that was at index 4 immediately shuffles into index 3. But your loop counter moves on to i = 4, completely skipping the element that just moved.

The solution is to traverse backwards.

// Removes all scores below 60 from a list
public void removeFailing(ArrayList<Integer> scores) {
    // Loop from the end of the list to the beginning
    for (int i = scores.size() - 1; i >= 0; i--) {
        if (scores.get(i) < 60) {
            scores.remove(i); // This is safe now!
        }
    }
}

When you remove an element at index i, the elements you've already checked (at i+1, i+2, etc.) are unaffected. Your next stop is i-1, which is exactly where it should be.

Reversing the Order

To reverse a list, you can swap the first element with the last, the second with the second-to-last, and so on, until you meet in the middle. This is a classic "two-pointer" approach.

public void reverseList(ArrayList<String> items) {
    int left = 0;
    int right = items.size() - 1;

    while (left < right) {
        // Swap the elements at the left and right pointers
        String temp = items.get(left);
        items.set(left, items.get(right));
        items.set(right, temp);

        // Move the pointers closer to the middle
        left++;
        right--;
    }
}

Special Traversals

Accessing Consecutive Pairs

What if you need to compare an element with the one right after it? For example, to find the biggest jump in temperature day-over-day.

The key is to stop your loop one element early to avoid an IndexOutOfBoundsException. Your loop should go up to list.size() - 1.

// Finds the largest increase between consecutive days
for (int i = 0; i < temperatures.size() - 1; i++) {
    int temp1 = temperatures.get(i);
    int temp2 = temperatures.get(i + 1);
    int difference = temp2 - temp1;
    // ... do something with the difference
}

Traversing Multiple Lists

Sometimes you need to work with two lists at once. For example, let's say you have two ArrayLists of student names, classA and classB, and you want to find students who are in both. A simple way is with nested loops: for each student in classA, loop through all of classB to see if you find a match.

ArrayList<String> classA = ...;
ArrayList<String> classB = ...;
ArrayList<String> commonStudents = new ArrayList<String>();

for (String studentA : classA) {
    for (String studentB : classB) {
        if (studentA.equals(studentB)) {
            commonStudents.add(studentA);
        }
    }
}

This covers the fundamental patterns. The AP exam will ask you to apply these patterns to new situations, but the core logic of traversing, checking, and modifying remains the same.

Let's walk through a few problems to see these algorithms in action.

public int countAboveAverage(ArrayList<Integer> scores) {
    if (scores.size() == 0) {
        return 0;
    }

    // --- Pass 1: Calculate Average ---
    double sum = 0.0;
    for (int score : scores) {
        sum += score;
    }
    double average = sum / scores.size();

    // --- Pass 2: Count Scores Above Average ---
    int numAboveAverage = 0;
    for (int score : scores) {
        if (score > average) {
            numAboveAverage++;
        }
    }

    return numAboveAverage;
}

public ArrayList<String> removeDuplicates(ArrayList<String> contacts) {
    ArrayList<String> uniqueContacts = new ArrayList<String>();

    for (String name : contacts) {
        // If the new list doesn't already have this name, add it.
        if (!uniqueContacts.contains(name)) {
            uniqueContacts.add(name);
        }
    }
    return uniqueContacts;
}

Ready to try a couple on your own? Don't worry about getting it perfect on the first try. The goal is to think through the logic.

Problem 1: Shift Left

Write a method shiftLeft(ArrayList<String> words) that "rotates" all elements one position to the left. The element that was at index 0 should move to the end of the list.

For example, if the list is ["a", "b", "c", "d"], after the method runs it should be ["b", "c", "d", "a"].

Problem 2: Is it a Palindrome?

Write a boolean method isPalindrome(ArrayList<Integer> nums) that returns true if the list reads the same forwards and backwards, and false otherwise.

For example, [1, 2, 3, 2, 1] is a palindrome. [1, 2, 3, 4, 5] is not.