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

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

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

Интерфейс List предоставляет удаление элемента по значению независимо от конкретной реализации списка. Для динамического массива это означает последовательный просмотр элементов: структура оптимизирована для доступа по индексу, но не хранит отдельный индекс для поиска произвольного значения.

Такой компромисс позволяет ArrayList занимать мало дополнительной памяти и быстро обращаться к элементам по индексу. Цена этого решения — линейный поиск и необходимость сдвига элементов при удалении из середины.

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

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

Есть и практическая ловушка с перегруженными методами. Для списка чисел вызов с аргументом типа int трактуется как удаление по индексу, а не как удаление числового значения.

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

При удалении по значению ArrayList сравнивает элементы с искомым объектом через equals. Поиск останавливается на первом совпадении; если совпадения нет, список не изменяется.

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

В результате:

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

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

import java.util.ArrayList;
import java.util.List;

List<Integer> values = new ArrayList<>();
values.add(10);
values.add(20);
values.add(30);

values.remove(Integer.valueOf(20)); // удаляет значение 20
values.remove(0);                  // удаляет элемент по индексу 0

В первом вызове выбирается remove(Object), поэтому выполняются поиск по equals и сдвиг элементов. Во втором вызывается remove(int), поскольку аргумент имеет примитивный тип int; это удаление по индексу, а не поиск значения.

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

Сервис получает список из нескольких сотен тысяч идентификаторов и должен удалить из него набор запрещённых идентификаторов, сохранив порядок остальных. Последовательный вызов удаления по значению для каждого запрещённого элемента может привести к многократным проходам и сдвигам, то есть к плохой совокупной производительности.

Вариант с LinkedList уменьшает стоимость физического удаления найденного узла, но не устраняет линейный поиск значения и обычно проигрывает массиву по локальности доступа. Вариант с HashSet для исходных данных меняет семантику: исчезают порядок и дубликаты, поэтому он подходит не всегда.

Практичное решение — собрать запрещённые значения в HashSet, затем одним проходом отфильтровать исходный ArrayList через removeIf или создать новый список. Проверка принадлежности к множеству в среднем близка к O(1), поэтому полный пакетный сценарий обычно приближается к O(n + m), где n — размер списка, а m — число запрещённых значений.

Так сохраняются порядок и дубликаты разрешённых элементов, а вместо множества отдельных сдвигов выполняется компактирование списка. При этом следует учитывать качество hashCode и equals элементов, а также расход памяти на множество запрещённых значений.

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

Удаляется ли один или все совпадающие элементы при удалении по значению?

Удаляется только первое найденное совпадение. Это следует из поведения List.remove(Object): поиск идёт от начала списка и завершается после удаления первого элемента, равного аргументу. Чтобы удалить все совпадения, нужен отдельный проход, например фильтрация через removeIf; повторные вызовы remove могут иметь существенно худшую совокупную сложность.
Всегда ли удаление по значению из ArrayList требует сдвига элементов?

Нет. Если найденный элемент находится в конце списка, сдвиг не нужен. Но поиск до последнего элемента всё равно может занять O(n), поэтому общая асимптотическая оценка операции остаётся линейной. Для элемента в начале или середине дополнительно перемещается хвост внутреннего массива.
Можно ли считать remove(Object) безопасным для объектов с изменяемыми полями?

Сравнение выполняется в момент вызова, поэтому изменяемое состояние само по себе не нарушает структуру ArrayList. Однако после изменения полей результат поиска может измениться: объект, который раньше был равен искомому значению, может перестать ему соответствовать.

Это отличается от ситуации с HashMap или HashSet, где изменение полей, участвующих в equals и hashCode, нарушает поиск по хеш-таблице. В ArrayList нет размещения по хешу, но полагаться на изменяемое состояние как на стабильный критерий поиска всё равно рискованно для корректности бизнес-логики.