Как работает ArrayList при добавлении нового элемента?

ArrayList хранит элементы во внутреннем массиве. При добавлении элемента происходит следующее:

1. Проверяется, достаточно ли места во внутреннем массиве (elementData).
2. Если места нет, запускается процесс увеличения емкости (resize):
   • Создается новый массив большего размера.
   • Формула роста: новая_емкость = старая_емкость + (старая_емкость >> 1) (примерно в 1.5 раза).
   • Все существующие элементы копируются в новый массив.
3. Элемент помещается в следующую свободную позицию.

Пример и сложность:

ArrayList<String> list = new ArrayList<>(2); // Внутренний массив размером 2
list.add("A"); // O(1) - простое присваивание
list.add("B"); // O(1)
list.add("C"); // O(n) - происходит resize и копирование 2 элементов

Важно:

• Добавление в конец (add(E)): амортизированное O(1), но отдельная операция resize стоит O(n).
• Вставка по индексу (add(int index, E)): O(n), так как требует сдвига всех последующих элементов.
• Инициализация с начальной capacity помогает избежать частых операций resize.