Что лежит в основе ArrayList?

ArrayList хранит элементы во внутреннем массиве elementData. Размер списка (size) обычно меньше длины массива (ёмкости) — есть запас.

Из устройства следуют характеристики:

• доступ по индексу — O(1): адрес вычисляется арифметически;
• добавление в конец — обычно O(1). Когда массив заполнен, создаётся новый большего размера (в HotSpot — примерно в 1,5 раза) и элементы копируются. Копирование дорогое, но редкое, поэтому в среднем по серии операций добавление — амортизированное O(1);
• вставка и удаление в середине — O(n): все элементы правее нужно сдвинуть;
• поиск по значению (contains, indexOf) — O(n).

Практика: если размер известен, передать ёмкость в конструктор (new ArrayList<>(10_000)) — расширений не будет. Массив сам не уменьшается при удалении: для этого есть trimToSize().

ArrayList не потокобезопасен.