Сколько стоит удаление элемента из середины ArrayList и почему?
O(n): хвост сдвигается влево через System.arraycopy, последняя ячейка обнуляется. Удаление в цикле — квадратичная работа.
- Удаление с конца — O(1)
- Много удалений — removeIf: один проход и один сдвиг
- Удалять по индексу вперёд в цикле — пропуск соседних элементов
А ещё Порядок не важен — поменять с последним и удалить последний за O(1)
Подробно
Список обязан быть плотным, поэтому после удаления хвост копируется на одну позицию влево, а последняя ячейка обнуляется, чтобы не удерживать объект от сборки. Отсюда практическое следствие: удаление в цикле превращает линейную задачу в квадратичную. Классическая же ошибка — идти по индексам вперёд и удалять: после удаления элементы сдвигаются, а индекс увеличивается, поэтому каждый второй элемент пропускается. Правильные способы — removeIf, iterator.remove() или проход по индексам с конца.
Что хотят услышать
- Сдвиг хвоста и сложность.
- Последствия для удаления в цикле и removeIf.
Частые ошибки
- Удалять в цикле по возрастающему индексу и пропускать элементы.
- Строить алгоритм на массовом удалении из середины списка.
Проверьте себя
Один верный вариант. Подумайте, потом откройте ответ.
Показать варианты и ответ
- ✗O(1): на месте удалённого элемента остаётся null, который потом пропускается
- ✓O(n): элементы правее сдвигаются влево через System.arraycopy
- ✗O(log n): позиция ищется двоичным поиском
- ✗O(1) амортизированно, как и добавление в конец
Что спросят дальше
- Почему removeIf эффективнее серии remove?
- Чем в этом сценарии поможет другая структура данных?
Разбор темы
- ArrayList: динамический массив изнутри
Бэкенд-массив, рост в 1.5×, амортизированная O(1), стоимость вставки/удаления и когда массив лучше.
Связанные вопросы
Разбор собеседования с sotto
После собеседования sotto разбирает разговор: оценка, каждый вопрос — хорошо, частично или слабо, чего не хватило в ответе и над чем поработать к следующему разу. Первые 30 минут бесплатно.