ArrayList algorithms: filter and the remove bug · ⁨Алгоритмы для ArrayList: фильтрация и ошибка удаления⁩

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.

Русский

Подсчёт по правилу

Пройдите по списку, проверьте каждый элемент и добавьте 1 к счётчику, если проверка прошла успешно.
n % 2 == 0 истинно, когда n чётное. n % 2 != 0 истинно, когда n нечётное.
Поскольку здесь только чтение списка, подходит enhanced 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 к 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);   // 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, поэтому ничего не移出 под вас (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
    }
}

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.

Русский

Заметка о enhanced for-цикле

Вас может соблазнить удалить элемент внутри for (int x : nums).
Не делайте этого. Изменение размера списка во время enhanced 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 или дополните показанный метод.
Нажмите Run (Выполнить), чтобы скомпилировать и запустить, затем Check answer (Проверить ответ).
Ваш код компилируется и выполняется на сервере, поэтому даже первый запуск происходит быстро.

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: фильтрация и ошибка удаления⁩

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

Заметка о enhanced for-цикле

Common mistakes

Распространенные ошибки

Now you try

Теперь попробуйте сами

Filtering a list · ⁨Фильтрация списка⁩

Handout · ⁨Раздаточный материал⁩

Log in or create account · ⁨Войти или создать аккаунт⁩

Your subject · ⁨Ваш предмет⁩

All sections · ⁨Все разделы⁩

Feedback & help · ⁨Обратная связь и помощь⁩