Краткий ответ

Для ArrayList вызов removeIf обычно выполняется за O(n) по числу элементов: список проходит один раз, а оставшиеся элементы компактно сдвигаются в массиве. Удаление большого числа элементов не превращается в последовательность отдельных дорогостоящих сдвигов, как при многократном вызове remove(index).

В данном примере предикат проверяется для всех элементов, после чего примерно половина значений сохраняется и массив уплотняется.

Исторический контекст

Метод Collection.removeIf появился как часть расширения коллекционного API в Java 8. Он позволяет выразить массовое удаление через условие, не заставляя разработчика вручную управлять итератором и индексами.

Общий метод интерфейса предоставляет корректное поведение для коллекций, но конкретная реализация может переопределить его ради лучшей производительности. ArrayList использует специализированный алгоритм обработки массива, потому что последовательные удаления из середины обычным способом требуют постоянного перемещения хвоста.

Постановка проблемы

Наивная реализация могла бы найти каждый подходящий элемент и немедленно удалить его. Для ArrayList удаление из середины требует сдвинуть все последующие элементы влево, поэтому серия таких операций способна привести к O(n²).

Это особенно заметно, когда совпадения расположены в начале списка или распределены по нему часто. Дополнительный риск ручного удаления во время обхода — пропуск элементов из-за изменения индексов либо получение ConcurrentModificationException при нарушении правил итератора.

Подробное решение

ArrayList хранит элементы в непрерывном массиве. При выполнении removeIf реализация проверяет элементы, определяет удаляемые позиции, а затем одним этапом или небольшим числом последовательных операций перемещает оставшиеся значения ближе к началу массива и очищает освободившиеся ссылки.

Поэтому суммарная работа включает проход по исходным элементам и уплотнение массива — O(n). Дополнительная память обычно составляет O(n) в худшем случае для служебной информации о выбранных позициях; это не означает создания второго списка с копиями элементов.

import java.util.ArrayList;

ArrayList<String> values = new ArrayList<>();
values.add("keep-1");
values.add("drop-1");
values.add("keep-2");
values.add("drop-2");

values.removeIf(value -> value.startsWith("drop-"));
System.out.println(values); // [keep-1, keep-2]

Важно, что сложность включает стоимость самого предиката. Если startsWith работает за время, зависящее от длины строки, полная оценка учитывает и эту стоимость; обозначение O(n) предполагает постоянную или ограниченную стоимость проверки одного элемента.

Ручной цикл с Iterator.remove() сохраняет корректность, но последовательные удаления из ArrayList могут выполнять множество сдвигов и в худшем случае иметь квадратичную сложность. Метод removeIf предпочтительнее, когда условие удаления можно выразить одним предикатом.

Для других коллекций гарантировать такую же оценку нельзя: сложность определяется их представлением и переопределением метода. Кроме того, предикат не должен изменять ту же коллекцию структурным образом — это нарушает ожидаемый контракт операции и может привести к исключению или неопределённому для прикладной логики поведению.

Ситуация из практики

В сервисе обрабатывался список из нескольких миллионов записей, из которого требовалось убрать просроченные элементы. Вариант с циклом по индексам и remove(i) оказался медленным: после каждого удаления хвост массива сдвигался, а индексы требовали отдельной корректировки.

Вариант с копированием подходящих записей в новый список имел линейное время, но временно удваивал объём ссылок и увеличивал давление на сборщик мусора. Вариант с Iterator.remove() был проще для точечного удаления, однако при большом количестве совпадений мог многократно сдвигать элементы.

Выбрали removeIf для ArrayList: условие проверялось один раз на элемент, а реализация выполняла массовое уплотнение. Это дало линейную оценку по размеру списка и меньшие накладные расходы, чем создание второго списка. Если же список после фильтрации почти полностью заменялся новым набором, отдельная генерация результирующего списка могла быть удобнее для читаемости и управления памятью.

Что кандидаты часто упускают

Всегда ли removeIf у любой коллекции имеет сложность O(n)?

Нет. O(n) характерно для данного сценария с ArrayList, но интерфейс Collection не превращает все реализации в массивы. У связного списка удаление найденного узла может быть дешёвым, но поиск и обход имеют свои характеристики; у специализированных или конкурентных коллекций есть дополнительные ограничения и собственные контракты. Сложность нужно выводить из реализации конкретного типа, а не только из имени метода.

Почему ручной вызов remove(i) в цикле может быть квадратичным даже при одном проходе по индексам?

Удаление из середины ArrayList требует сдвига всех элементов справа на одну позицию. Если удалять много элементов, суммарная длина сдвига может составить порядка n + (n - 1) + ..., то есть O(n²). Кроме того, после удаления размер списка уменьшается, поэтому неверное управление индексом способно пропустить следующий элемент.

Что произойдёт, если предикат изменяет сам список?

Например, добавление или удаление элементов внутри предиката — это структурное изменение во время выполнения операции обхода. Для ArrayList такое вмешательство нарушает ожидаемые условия работы и может привести к ConcurrentModificationException, некорректному результату или ошибке из-за рассинхронизации внутреннего алгоритма. Предикат должен вычислять условие по текущему элементу, а все изменения коллекции должна выполнять сама операция removeIf.