4.10 Implementing ArrayList Algorithms

What you need to know

• All the array algorithms (min/max, sum, count, any/all, duplicates, reverse) apply — swap arr[i] for list.get(i), length for size().
• Filter into a new list: create an empty ArrayList, traverse the original, add matches. The original is unchanged.
• Insert in sorted position: traverse until you find an element bigger than the new one, add(i, value) there; if none, add(value) at the end.
• Remove all matches: backward traversal with remove(i) (4.9).
• Traversing a list of objects: call accessors on each element (list.get(i).getName()). This is FRQ 3's shape: a class is given, and you process an ArrayList of its objects.
• Returning a new list vs. modifying the parameter: read the prompt. "Returns a list of…" → build and return a new one. "Removes from the list…" → mutate the parameter.

Worked example

// FRQ 3-style: return names of students with gpa above a threshold
public static ArrayList<String> honorRoll(ArrayList<Student> roster, double min)
{
    ArrayList<String> result = new ArrayList<String>();
    for (Student s : roster)
    {
        if (s.getGpa() >= min)
        {
            result.add(s.getName());
        }
    }
    return result;
}

// insert keeping ascending order
public static void insertSorted(ArrayList<Integer> list, int v)
{
    for (int i = 0; i < list.size(); i++)
    {
        if (v < list.get(i))
        {
            list.add(i, v);
            return;
        }
    }
    list.add(v);
}

Going deeper

The nuance, edge cases, and connections that turn a 3 into a 5.

• Translation from arrays: arr.length → list.size(); arr[i] → list.get(i); arr[i] = x → list.set(i, x). Everything from 4.5 carries over.
• New with ArrayLists: insert in sorted position (add(i, x) at the first i where x < get(i), else append), remove all matches (backward loop), build a filtered result list (new ArrayList, add matches), merge two lists.
• FRQ 3 shape: you're given a class (say Song with getTitle(), getDuration()) and asked to write methods over an ArrayList<Song>: find the longest, count those over a threshold, return a list of titles, remove those matching a condition. Every one is a loop + accessor calls + accumulator or result list.
• Return a new list vs. modify in place: read the verb. "Returns a list of…" → build and return new. "Removes from…" or "updates…" → modify the parameter, return void. Doing the wrong one earns zero on that part.
• Accessor calls on elements: list.get(i).getTitle() — get the element, then call its method. With an enhanced for, s.getTitle(). Chaining is normal.
• Comparing elements for max/min: the comparison uses a field: if (s.getDuration() > longest.getDuration()) longest = s;. Initialize longest to list.get(0).
• Rubric reality: points typically go to the loop over all elements, the correct accessor call, the correct condition, the correct action (add/remove/update), and the correct return. Each independently. A structurally correct answer with one wrong comparison still scores most points.

Mistakes that cost points

• Modifying when asked to return new (or vice versa). Read the prompt's verb.
• Not returning the result list. Built it, forgot return result;.
• Comparing objects with == or <. Compare their fields via accessors.
• Forward-loop removal (again). Backward.

Practice questions

Written in the style of the real exam. Try each one before revealing the answer.

public static int f(ArrayList<Integer> list)
{
    int r = list.get(0);
    for (int i = 1; i < list.size(); i++)
    {
        if (list.get(i) < r) r = list.get(i);
    }
    return r;
}