Как внутренне организовано хранение элементов в ArrayList?

ArrayList в Java хранит свои элементы во внутреннем массиве (Object[]), объявленном как transient Object[] elementData. Это фундаментальная деталь реализации, обеспечивающая быстрый доступ по индексу.

Внутренняя механика:

1. Инициализация: При создании new ArrayList<>() выделяется массив начальной емкости (default capacity = 10).
2. Добавление элементов: Метод add(E e) помещает элемент в первую свободную ячейку массива.
3. Динамическое расширение: При попытке добавить элемент в заполненный массив срабатывает grow():
   • Создается новый массив размером *старая_емкость 1.5** (старая емкость + старая емкость >> 1).
   • Все элементы копируются из старого массива в новый (Arrays.copyOf).
   • Ссылка elementData начинает указывать на новый массив.

Ключевые аспекты:

• Доступ: get(int index) и set(int index, E element) работают за O(1), так как это прямое обращение к элементу массива.
• Вставка/удаление: add(int index, E element) и remove(int index) требуют O(n), так как необходимо сдвигать часть массива.
• Сериализация: Поле elementData объявлено transient. При сериализации записываются только реальные элементы (до size), а не весь массив, что экономит место.

Пример, иллюстрирующий расширение:

ArrayList<Integer> list = new ArrayList<>(2); // Внутренний массив length=2
list.add(1); // elementData[0] = 1
list.add(2); // elementData[1] = 2
list.add(3); // Массив заполнен! Создается новый массив length=3 (2 * 1.5)
             // Старые элементы копируются, затем добавляется 3.

Рекомендация: Если известен ожидаемый размер коллекции, используйте конструктор ArrayList(int initialCapacity), чтобы избежать многократных операций копирования при заполнении.