Как реализован ArrayList в Java?

ArrayList в Java реализован как динамический массив (resizable array). Внутри он хранит элементы в обычном массиве объектов (Object[]), который автоматически пересоздаётся при необходимости.

Ключевые особенности реализации:

• Начальная ёмкость по умолчанию — 10 элементов.
• Увеличение размера: при заполнении внутреннего массива создаётся новый массив большего размера (обычно старыйРазмер * 1.5) и элементы копируются в него.
• Сложность операций:
  • Доступ по индексу (get, set) — O(1).
  • Добавление в конец (add) — амортизированная O(1).
  • Вставка/удаление в середину (add(index, element), remove(index)) — O(n), так как требует сдвига последующих элементов.

Пример:

import java.util.ArrayList;

ArrayList<String> list = new ArrayList<>(); // Внутри: Object[] размером 10
list.add("Java"); // Добавление в конец
String element = list.get(0); // Мгновенный доступ по индексу 0
list.add(0, "Python"); // O(n): все элементы сдвигаются вправо

Таким образом, ArrayList имеет линейную (массивную) структуру, а не древовидную, что обеспечивает быстрый произвольный доступ, но медленные модификации в середине.