Как происходит вставка элемента в ArrayList если size равен capacity

Механизм вставки элемента при size == capacity

Когда происходит попытка добавления нового элемента в ArrayList и его текущий размер (size) равен ёмкости (capacity), это означает, что внутренний массив заполнен. В этот момент срабатывает механизм динамического расширения (resizing), который является ключевой особенностью ArrayList для обеспечения амортизированной константной сложности O(1) операций добавления в среднем.

Подробный процесс вставки

1. Проверка условия переполнения
   При вызове методов add(E element) или add(int index, E element) сначала проверяется, достаточно ли места во внутреннем массиве:

   public boolean add(E e) {
       ensureCapacityInternal(size + 1); // Проверка ёмкости
       elementData[size++] = e;
       return true;
   }
   

2. Вызов ensureCapacityInternal
   Метод вычисляет минимальную требуемую ёмкость и вызывает ensureExplicitCapacity():

   private void ensureCapacityInternal(int minCapacity) {
       if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
       }
       ensureExplicitCapacity(minCapacity);
   }
   

3. Проверка необходимости расширения
   Если требуемая ёмкость превышает длину текущего массива, запускается процесс роста:

   private void ensureExplicitCapacity(int minCapacity) {
       modCount++;
       if (minCapacity - elementData.length > 0)
           grow(minCapacity); // Вызов расширения
   }
   

4. Метод grow() - ядро расширения
   Здесь определяется новый размер массива и выполняется его пересоздание:

   private void grow(int minCapacity) {
       int oldCapacity = elementData.length;
       int newCapacity = oldCapacity + (oldCapacity >> 1); // Увеличение в 1.5 раза
       if (newCapacity - minCapacity < 0)
           newCapacity = minCapacity;
       if (newCapacity - MAX_ARRAY_SIZE > 0)
           newCapacity = hugeCapacity(minCapacity);
       elementData = Arrays.copyOf(elementData, newCapacity); // Ключевая операция
   }
   

Ключевые аспекты расширения

Коэффициент расширения

• По умолчанию массив увеличивается в 1.5 раза (старая ёмкость + старая ёмкость / 2)
• Для пустого ArrayList с дефолтной ёмкостью 10: 10 → 15 → 22 → 33 и т.д.
• При явном указании начальной ёмкости через конструктор ArrayList(int initialCapacity) расширение также происходит в 1.5 раза

Производительность операции

• Операция Arrays.copyOf() создает новый массив и копирует все элементы из старого
• Временная сложность: O(n), где n - текущее количество элементов
• Несмотря на линейную сложность отдельной операции расширения, амортизированная сложность добавления остается O(1) благодаря редкому выполнению расширений

Практический пример

ArrayList<String> list = new ArrayList<>(3); // capacity = 3
list.add("A"); // size = 1, capacity = 3
list.add("B"); // size = 2, capacity = 3
list.add("C"); // size = 3, capacity = 3
list.add("D"); // size == capacity, требуется расширение!

// Внутри grow():
// oldCapacity = 3
// newCapacity = 3 + (3 >> 1) = 3 + 1 = 4
// Создается новый массив размером 4
// Элементы "A", "B", "C" копируются в новый массив
// "D" добавляется на позицию 3
// Теперь size = 4, capacity = 4

Важные особенности

Модификатор modCount
При каждом изменении структуры (включая расширение) увеличивается счетчик modCount, что важно для работы итераторов и механизма fail-fast.

Стратегия предварительного выделения
Для минимизации количества расширений можно использовать метод ensureCapacity():

ArrayList<Integer> list = new ArrayList<>();
list.ensureCapacity(1000); // Однократное расширение до 1000
// 1000 добавлений без дополнительных расширений

Память и производительность
Частые расширения могут вызывать:

• Дополнительную нагрузку на сборщик мусора (старые массивы становятся мусором)
• Временные задержки при копировании больших массивов
• Избыточное потребление памяти (массив может быть заполнен лишь частично)

Сравнение с массивом фиксированного размера

В отличие от обычного массива, ArrayList:

• Автоматически управляет расширением
• Позволяет динамически менять размер
• Абстрагирует разработчика от ручного управления памятью
• Добавляет небольшие накладные расходы на проверки и копирование

Понимание механизма расширения критически важно для написания эффективных Android-приложений, где неправильное использование ArrayList с частыми расширениями может привести к просадкам производительности и излишнему потреблению памяти, особенно при работе с большими коллекциями данных.