Topic 4.10 Notes – Implementing ArrayList Algorithms

What ArrayList Algorithms Are

An ArrayList algorithm processes elements using traversal, usually with:

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

Key reminders:

• Valid indices go from 0 to size() - 1
• get(i) and set(i, value) access elements
• add(index, value) and remove(index) shift elements

Most algorithms are:

• Single pass (O(n)) → process each element once
• Nested loops (O(n²)) → compare elements to each other

If you recognize the pattern, you know how the loop should look before writing code.

Standard ArrayList Algorithm Patterns

Here’s the full set you’re expected to write and trace.

Minimum and Maximum

This is the “best so far” pattern. You keep track of the largest value you’ve seen as you move left to right through the list.

Structure:

1. Assume the list is non-empty (or check first).
2. Set max (or min) to list.get(0).
3. Loop from index 1.
4. Update when you find something better.

Common mistake:
Initializing max = 0. That fails if all numbers are negative.

Sum, Average, and Counting

This uses an accumulator variable.

int sum = 0;
for (int i = 0; i < list.size(); i++) {
    sum += list.get(i);
}

Variations:

• Average → (double) sum / list.size()
• Count with condition → increment inside if
• At least one → return true immediately when found
• All elements → return false immediately when one fails

Placement of return is where students lose points.
If you return too early in an “all” problem, you break the logic.

Consecutive Pairs

You compare i and i + 1. Each step forms a pair of neighbors.

Loop condition:

for (int i = 0; i < list.size() - 1; i++)

If you go to size(), you’ll crash with out-of-bounds.

Detecting Duplicates

This requires nested loops.

for (int i = 0; i < list.size(); i++) {
    for (int j = i + 1; j < list.size(); j++) {
        if (list.get(i).equals(list.get(j))) {
            return true;
        }
    }
}

Why j = i + 1?

• Avoid comparing element to itself
• Avoid checking the same pair twice

Time complexity is O(n²). If you see two loops comparing elements, expect quadratic behavior.

Shifting and Rotating

Right shift steps:

1. Save last element
2. Move elements right (backward loop)
3. Put saved value at index 0

Backward loop is critical:

for (int i = list.size() - 1; i > 0; i--) {
    list.set(i, list.get(i - 1));
}

Forward loop would overwrite values.

Reversing

This uses the two-pointer swap pattern. You swap the first with the last, then move inward.

Loop until i < size() / 2, swapping:

• i
• size() - 1 - i

Insert and Delete

• add(index, value) → shifts right
• remove(index) → shifts left

If removing during traversal:

• Traverse backward, or
• Decrement i after removal

Otherwise, you skip elements. This shows up constantly in FRQ grading.

Traversing Multiple Lists Simultaneously

Some algorithms compare two lists element-by-element.

for (int i = 0; i < list1.size(); i++) {
    if (!list1.get(i).equals(list2.get(i))) {
        return false;
    }
}

Be careful:

• Use the correct list’s size()
• If sizes might differ, check first

Parallel traversal questions are common in code-tracing MCQs.

Edge Cases You Must Mentally Test

Before you’re done, think about:

• Empty list
• One element
• No matches
• Removing while looping
• Peak/min at index 0 or last index

A classic crash:

int max = list.get(0);  // fails if empty

Even when the question says “assume non-empty,” you should notice the risk.