Алгоритмы для ArrayList: фильтрация и ошибка удаления
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
1to a counter when the test is true. n % 2 == 0is true whennis even.n % 2 != 0is true whennis 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
addeach 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 adds1toiand 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.2is even, remove it. List becomes[4, 5]. - The
4slid down into index0. But the loop now setsi = 1. - At
i = 1we look at5, not4. The4was never checked. It stays in.
The fix: loop backwards
- Walk from the last index down to
0. - When you remove index
i, only items afterishift — 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 usually throws a
ConcurrentModificationException, and when it does not, items are silently skipped. Use an index loop instead. - For removing, always use the backward index loop above.
Common mistakes
- Removing while looping forward by index skips the next item (the remove bug).
- Loop backwards, or use an iterator, when removing.
Now you try
- Each task pre-fills the class skeleton — write your code inside main, or complete the method shown.
- Use Check answer to compile your code with the supplied tests and view the results. Keep the class and method interfaces shown in the starter.
- Your code compiles and runs on the server, so even the first run is fast.
Фильтрация списка
Удаление во время обхода сдвигает индексы — пройдите по шагам, чтобы понять почему.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Допишите countOdds(ArrayList<Integer> a), чтобы он возвращал количество нечетных чисел в списке. Число считается нечетным, когда x % 2 != 0.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Заполните keepPositives(ArrayList<Integer> a). Создайте и верните новый ArrayList<Integer>, содержащий только числа, большие 0, в их исходном порядке. Не изменяйте a.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Допишите removeEvens(ArrayList<Integer> a), чтобы он удалял все четные числа из самого a. Обходите обратно по индексам, чтобы не пропускать элементы. Ничего не возвращайте (void).
Нажмите Запустить, чтобы увидеть результат здесь.