ArrayList algorithms: filter and the remove bug

English

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.

日本語

リスト全体に対する処理

今やデータは ArrayList に格納できる。次に処理する。
一般的な作業：ルールに一致するアイテムを カウント する、新しいリストへ フィルタリング する、あるいは一部のアイテムを削除する。
これらすべては、リストへのループを使用する。

English

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.

日本語

ルールに基づくカウント

リストを traversal し、各アイテムをテストし、テストが真の場合にカウンタに 1 を加算する。
n % 2 == 0 は n が偶数の場合に真となる。n % 2 != 0 は n が奇数の場合に真となる。
これはリストを 読み取る 操作のみであるため、強化された for ループでも問題ない。

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
    }
}

English

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.

日本語

新しいリストへのフィルタリング

フィルタリング は、テストに合格したアイテムのみを残すことである。
安全なパターン：空の新しいリストを作成し、テストに合格した各アイテムを add で追加する。
元のリストは変更されない。これにより、次に紹介するバグを防げる。

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]
    }
}

English

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.

日本語

反復中の削除バグ

容易に見えそうだが、前方へループして不要なアイテムを remove(i) で削除する。
しかし、remove(i) を削除すると、以降のすべてのアイテムが 1つ左にシフト する。その後、ループは 1 を i に加算し、古い位置に移動してきたアイテムを スキップ してしまう。
以下の例ではすべての偶数を削除しようと試みるが、1つを見逃してしまう。

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
    }
}

English

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.

日本語

スキップされる理由

開始時: [2, 4, 5], i = 0。2 は偶数なので削除する。リストは [4, 5] になる。
4 がインデックス 0 にスライドした。しかしループは i = 1 を設定する。
i = 1 で 5 を確認しているが、4 を確認していない。4 は チェックされていない。そのまま残ってしまう。

English

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.

日本語

修正法：逆方向へのループ

最後の インデックスから 0 まで下向きに traversal する。
インデックス i を削除した場合、i の後のみシフトするが、すでにProcessor した部分である。
まだ訪問していないインデックスは i より 小さい ため、どこかにズレが生じない。

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
    }
}

English

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.

日本語

強化された for ループに関する注記

for (int x : nums) 内で削除したいと誘惑されるかもしれない。
行わないでください。 強化された for ループ中にリストのサイズを変えると、ConcurrentModificationException がスローされ、プログラムが停止する。
削除については、常に上記の 逆方向インデックス ループを使用すること。

English

Common mistakes

Removing while looping forward by index skips the next item (the remove bug).
Loop backwards, or use an iterator, when removing.

日本語

よくあるミス

インデックスによる前方ループでの削除は、次のアイテムをスキップする（削除バグ）。
削除の際は、逆方向にループするか、イテレータを使用する。

English

Now you try

Each task pre-fills the class skeleton — write your code inside main, or complete the method shown.
Press Run to compile and run, then Check answer.
Your code compiles and runs on the server, so even the first run is fast.

日本語

あなたも試してみよう

各タスクはクラス骨組みを事前入力しています。main 内にコードを書くか、表示されたメソッドを完成させてください。
実行を押してコンパイル・実行し、その後 回答を確認 を押してください。
コードはサーバー上でコンパイル・実行されるため、初回実行でも高速です。

Explore · ⁨探索⁩

Filtering a list

Removing while looping shifts indices — step through to see why.

Complete countOdds(ArrayList<Integer> a) so it returns how many numbers in the list are odd. A number is odd when x % 2 != 0.

import java.util.ArrayList;

public class ListUtil {
    // Return how many numbers in a are odd.
    public static int countOdds(ArrayList<Integer> a) {
        return 0;   // change this
    }
}

Click Run to see the output here. · ⁨実行ボタンをクリックして出力を確認してください。⁩

Complete keepPositives(ArrayList<Integer> a). Build and return a new ArrayList<Integer> that holds only the numbers greater than 0, in their original order. Do not change a.

import java.util.ArrayList;

public class ListUtil {
    // Return a new list with only the numbers > 0.
    public static ArrayList<Integer> keepPositives(ArrayList<Integer> a) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        // add the positives here
        return result;
    }
}

Click Run to see the output here. · ⁨実行ボタンをクリックして出力を確認してください。⁩

Complete removeEvens(ArrayList<Integer> a) so it removes every even number from a itself. Loop backwards by index so you do not skip items. Return nothing (void).

import java.util.ArrayList;

public class ListUtil {
    // Remove every even number from a. Loop backwards!
    public static void removeEvens(ArrayList<Integer> a) {
        // your code here
    }
}

Click Run to see the output here. · ⁨実行ボタンをクリックして出力を確認してください。⁩

Doing work on a whole list

リスト全体に対する処理

Counting with a rule

ルールに基づくカウント

Filtering into a new list

新しいリストへのフィルタリング

The remove-while-iterating bug

反復中の削除バグ

Why it skips

スキップされる理由

The fix: loop backwards

修正法：逆方向へのループ

A note on the enhanced for-loop

強化された for ループに関する注記

Common mistakes

よくあるミス

Now you try

あなたも試してみよう

Filtering a list

Handout · ⁨プリント⁩

Log in or create account · ⁨ログインまたはアカウント作成⁩

Your subject · ⁨あなたの科目⁩

All sections · ⁨全セクション⁩

Feedback & help · ⁨フィードバック & ヘルプ⁩