Как работает ArrayList в Java

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

Знаете ли вы устройство изнутри: массив, ёмкость, расширение и цена операций. Заодно проверяют, помните ли вы, на сколько именно растёт массив.

Как отвечать

Внутри обычный массив плюс поле с числом реально занятых элементов. Различайте размер (сколько элементов) и ёмкость (сколько помещается без расширения).

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

Стоимость операций:

• доступ по индексу за константу, это главное преимущество;
• добавление в конец амортизированно за константу: обычно просто запись, изредка расширение с копированием;
• вставка и удаление в середину линейные, потому что хвост сдвигается;
• поиск значения линейный, с вызовом equals.

Что ещё стоит назвать:

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

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

Говорят, что массив растёт вдвое.

Удаляют элементы в цикле по индексу вперёд и пропускают элементы из-за сдвига.

Используют ArrayList как очередь с удалением из начала, получая линейную операцию на каждый шаг, где нужен ArrayDeque.