ArrayList algorithms: filter and the remove bug · ⁨ArrayList 算法:筛选与删除的 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 了。接下来我们处理(process)它。
常见的工作:统计(count)符合规则的元素、把它们筛选(filter)到一个新列表里、以及删除(remove)其中一些。
这些都用一个遍历列表的循环来完成。

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.

中文

按规则统计

走遍列表,测试每个元素,当测试为真时给计数器加 1。
当 n 是偶数时 n % 2 == 0 为真。当 n 是奇数时 n % 2 != 0 为真。
这只是读取列表,所以用增强 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.

中文

筛选到一个新列表

筛选(filter)只保留通过测试的元素。
一个安全的写法:新建一个空的列表,然后把每个通过的元素 add 进去。
旧列表不会被改变。这样就能避免我们接下来要看的那个 bug。

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.

中文

边遍历边删除的 bug

它看起来很简单:向前循环,把不要的元素 remove(i) 掉。
但是 remove(i) 会把后面每个元素向左移动一位。然后循环给 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。
当你删除下标 i 时,只有 i 后面的元素会移动 —— 而那些你已经走过了。
你还要访问的下标都比 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.

中文

常见错误

用下标正向遍历时删除会漏掉下一个(remove bug)。
删除时倒着遍历,或用迭代器。

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. · ⁨完成 countOdds(ArrayList<Integer> a),让它返回列表里有多少个奇数。当 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. · ⁨完成 keepPositives(ArrayList<Integer> a)。创建并返回一个新的 ArrayList<Integer>,里面只保留大于 0 的数,并保持原来的顺序。不要改变 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). · ⁨完成 removeEvens(ArrayList<Integer> a),让它从 a 本身删除每一个偶数。用下标倒着循环,这样才不会跳过元素。不返回任何东西(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. · ⁨点击“运行”查看此处输出。⁩

ArrayList algorithms: filter and the remove bug · ⁨ArrayList 算法:筛选与删除的 bug⁩

Doing work on a whole list

对整个列表进行处理

Counting with a rule

按规则统计

Filtering into a new list

筛选到一个新列表

The remove-while-iterating bug

边遍历边删除的 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 · ⁨反馈与帮助⁩