Как происходит удаление элементов из ArrayList и как меняется его размер

Что проверяют

Знаете ли вы, что внутри ArrayList обычный массив, и различаете ли size и capacity. Именно это объясняет и стоимость удаления, и то, почему память после удаления не возвращается.

Как отвечать

• remove(int index) сдвигает хвост влево через System.arraycopy, обнуляет освободившуюся ячейку (elementData[--size] = null, иначе останется висячая ссылка на объект) и уменьшает size. Сложность O(n), удаление последнего элемента O(1).
• remove(Object o) сначала ищет элемент линейно по equals, затем делает тот же сдвиг, то есть тоже O(n).
• Внутренний массив никогда не сжимается сам. После удаления миллиона элементов capacity останется прежней, уменьшить её можно только вызовом trimToSize(). Растёт массив, наоборот, примерно в полтора раза: oldCapacity + (oldCapacity >> 1).
• Ловушка перегрузки: для List<Integer> вызов list.remove(1) удалит элемент с индексом 1, а не значение 1. Чтобы удалить значение, нужен list.remove(Integer.valueOf(1)).
• Удаление в цикле делают через removeIf или Iterator.remove(). Изменение списка внутри for-each бросит ConcurrentModificationException по счётчику modCount, а цикл по индексам вперёд молча пропустит соседний элемент, что хуже исключения.

list.removeIf(s -> s.startsWith("a"));                  // корректно, один проход
for (String s : list) if (s.isEmpty()) list.remove(s);  // ConcurrentModificationException

• Частые удаления из середины это сигнал сменить структуру: LinkedList при удалении через итератор, HashSet, когда важна проверка принадлежности.

Где спотыкаются

Говорят, что после удаления освобождается память. Освобождается только ссылка на объект, массив остаётся прежнего размера.

Забывают про перегрузку remove с int и Object, хотя это частый вопрос вдогонку про List<Integer>.

Считают ConcurrentModificationException гарантией. Это проверка best-effort, в многопоточном коде она может не сработать и синхронизацию не заменяет.

Уверенно называют рост массива в два раза. У ArrayList он в полтора раза, вдвое растёт, например, ArrayDeque.