ArrayList algorithms: filter and the remove bug

Doing work on a whole list

• Now you can store data in an ArrayList. Next we process it.
• Common jobs: count items that match a rule, filter them into a new list, and remove some of them.
• All of these use a loop over the list.

Counting with a rule

• Walk the list, test each item, and add 1 to a counter when the test is true.
• n % 2 == 0 is true when n is even. n % 2 != 0 is true when n is odd.
• This only reads the list, so an enhanced for-loop is fine.

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(4);
        nums.add(7);
        nums.add(10);
        nums.add(3);

        int evens = 0;
        for (int x : nums) {
            if (x % 2 == 0) {
                evens = evens + 1;
            }
        }
        System.out.println(evens);   // 2
    }
}

Filtering into a new list

• Filtering keeps only the items that pass a test.
• A safe pattern: make an empty new list, then add each item that passes.
• The old list is not changed. This avoids the bug we see next.

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(4);
        nums.add(7);
        nums.add(10);
        nums.add(3);

        ArrayList<Integer> bigOnes = new ArrayList<Integer>();
        for (int x : nums) {
            if (x >= 5) {
                bigOnes.add(x);
            }
        }
        System.out.println(bigOnes);   // [7, 10]
    }
}

The remove-while-iterating bug

• It looks easy: loop forward and remove(i) the items you do not want.
• But remove(i) shifts every later item one place left. The loop then adds 1 to i and skips the item that moved into the old spot.
• The example below tries to remove all evens but misses one.

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(2);
        nums.add(4);   // this one gets skipped!
        nums.add(5);

        // BUGGY: forward loop while removing
        for (int i = 0; i < nums.size(); i++) {
            if (nums.get(i) % 2 == 0) {
                nums.remove(i);
            }
        }
        System.out.println(nums);   // [4, 5]  -- wrong, 4 was missed
    }
}

Why it skips

• Start: [2, 4, 5], i = 0. 2 is even, remove it. List becomes [4, 5].
• The 4 slid down into index 0. But the loop now sets i = 1.
• At i = 1 we look at 5, not 4. The 4 was never checked. It stays in.

The fix: loop backwards

• Walk from the last index down to 0.
• When you remove index i, only items after i shift — and you have already passed those.
• The indexes you still need to visit are smaller than i, so nothing moves out from under you.

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(2);
        nums.add(4);
        nums.add(5);

        // SAFE: backward loop while removing
        for (int i = nums.size() - 1; i >= 0; i--) {
            if (nums.get(i) % 2 == 0) {
                nums.remove(i);
            }
        }
        System.out.println(nums);   // [5]  -- correct
    }
}

A note on the enhanced for-loop

• You may be tempted to remove inside for (int x : nums).
• Do not. Changing the list size during an enhanced for-loop throws a ConcurrentModificationException and stops the program.
• For removing, always use the backward index loop above.