Чем обусловлен худший случай добавления элемента в ArrayList?

ArrayList: Худший случай при добавлении элемента

ArrayList — это динамический массив, который автоматически увеличивает свой размер при необходимости. Операция добавления элемента имеет разные временные сложности в зависимости от ситуации. Давайте разберёмся, почему худший случай имеет сложность O(n).

Общее понимание

ArrayList внутри использует обычный Java массив.

public class ArrayList<E> extends AbstractList<E> implements List<E> {
    private transient Object[] elementData;  // Внутренний массив
    private int size;                         // Текущее кол-во элементов
    private static final int DEFAULT_CAPACITY = 10;
    // ...
}

Обычное добавление в конец (Best case)

ArrayList<Integer> list = new ArrayList<>();  // capacity = 10
list.add(1);   // O(1) - место есть
list.add(2);   // O(1) - место есть
list.add(3);   // O(1) - место есть
// ...
list.add(10);  // O(1) - место есть

Сложность: O(1) amortized

Добавление в конец работает за константное время, пока внутренний массив не переполнится.

Добавление при переполнении (Expansion case)

Когда количество элементов равно capacity и нужно добавить ещё один:

До расширения:
elementData = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]  (capacity = 10, size = 10)

Добавляем 11:
1. Проверка: size (10) == capacity (10)? Да
2. Расчёт новой capacity: newCapacity = 10 + (10 >> 1) = 10 + 5 = 15
3. Создание нового массива: newArray = new Object[15]
4. Копирование старых элементов: System.arraycopy()
   [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, null, null, null, null, null]
5. Добавление нового элемента в конец
6. Замена: elementData = newArray

Сложность в момент расширения: O(n)

где n — текущий размер списка (все элементы нужно скопировать)

Добавление в произвольную позицию (Worst case)

Это истинный worst case для ArrayList:

ArrayList<Integer> list = new ArrayList<>();
// Добавляем 1000 элементов
for (int i = 1; i <= 1000; i++) {
    list.add(i);
}

// Теперь вставляем элемент в начало!
list.add(0, -1);  // O(n) - ужасно!

Что происходит при add(0, -1):

До вставки:
indexes: [0]    [1]    [2]    ... [999]
values:  [1]    [2]    [3]    ... [1000]

После вставки (нужно сдвинуть все элементы!):
indexes: [0]    [1]    [2]    [3]    ... [1000]
values:  [-1]   [1]    [2]    [3]    ... [1000]
          ↑     (shift) (shift) (shift)
         вставлен

Сложность: O(n), потому что:

1. Проверяем, есть ли место в массиве
2. Если нет — расширяем (как выше)
3. Сдвигаем ВСЕ элементы на одну позицию вправо (System.arraycopy)
4. Вставляем новый элемент

Реальная реализация из Java source

public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);
    // Сдвиг элементов: копируем элементы от index до size-1
    // в позиции от index+1 до size
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);  // ← O(n) операция!
    elementData[index] = element;
    size++;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);  // 1.5x увеличение
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    elementData = Arrays.copyOf(elementData, newCapacity);  // ← O(n) копирование
}

Анализ System.arraycopy

System.arraycopy — это native метод, который копирует элементы массива. Он работает очень быстро благодаря оптимизациям JVM, но это всё равно O(n) операция.

// System.arraycopy(src, srcPos, dest, destPos, length)
// копирует length элементов из src начиная с srcPos
// в dest начиная с destPos

System.arraycopy(elementData, 0, elementData, 1, size - 0);
// Копирует все size элементов на одну позицию вправо
// сложность = O(size) = O(n)

Примеры худших случаев

// ❌ Худший случай 1: вставка в начало в цикле
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
    list.add(0, i);  // O(n) x 1000 = O(n²)
}
// Общая сложность: O(n²) !!!

// ❌ Худший случай 2: вставка в конец при частых расширениях
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
    list.add(i);  // обычно O(1), но иногда O(n)
}
// Амортизированная сложность: O(1)
// Но есть "пики" при каждом расширении

// ✅ Хороший случай: добавление в конец без вставок
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
    list.add(i);  // O(1) амортизировано
}

Почему расширение нужно вообще?

Java массивы имеют фиксированный размер. ArrayList обманывает пользователя, предоставляя динамический размер. Для этого используется стратегия exponential growth:

Шаг 1: capacity = 10, add элемент 11 → expand → capacity = 15
Шаг 2: capacity = 15, add элемент 16 → expand → capacity = 22
Шаг 3: capacity = 22, add элемент 23 → expand → capacity = 33
...

Расширение на 50% (в Java 8+) лучше, чем удвоение, потому что экономит память.

Анализ сложности для разных операций

Как избежать проблем

// ❌ Плохо: вставка в начало в цикле
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
    list.add(0, i);  // O(n²)
}

// ✅ Хорошо: используем LinkedList если много вставок в начало
List<Integer> list = new LinkedList<>();  // O(1) вставка
for (int i = 0; i < 1000; i++) {
    list.add(0, i);  // O(1)
}

// ✅ Хорошо: собираем в конец, потом переворачиваем
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
    list.add(i);  // O(1)
}
Collections.reverse(list);  // O(n)

// ✅ Хорошо: задаём capacity заранее
List<Integer> list = new ArrayList<>(2000);  // capacity = 2000
for (int i = 0; i < 1000; i++) {
    list.add(i);  // Никогда не расширится
}

Ключевые выводы

1. Добавление в конец: O(1) amortized — обычно работает быстро
2. Добавление в произвольное место: O(n) — нужно сдвинуть элементы
3. Добавление в начало: O(n) — самый плохой случай вставки
4. Расширение массива: O(n) — копирование всех элементов
5. Амортизированная сложность расширений: O(1) amortized за добавление

Арray-листы оптимальны для чтения и добавления в конец, но плохи для вставок в произвольное место или начало. Если нужны частые вставки в начало/середину — используйте LinkedList.