Какая сложность добавления элемента в ArrayList в худшем случае?

Сложность добавления элемента в ArrayList

Краткий ответ: O(n) в худшем случае

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

Внутреннее устройство ArrayList

public class ArrayList<E> extends AbstractList<E> 
        implements List<E>, RandomAccess, Cloneable {
    
    private static final int DEFAULT_CAPACITY = 10;
    Object[] elementData;
    int size = 0;
    
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;
        return true;
    }
}

Сценарий 1: Добавление в конец (обычный случай) - O(1)

ArrayList<Integer> list = new ArrayList<>();
list.add(1);  // size=0, capacity=10 -> O(1)
list.add(2);  // size=1, capacity=10 -> O(1)
list.add(3);  // size=2, capacity=10 -> O(1)

Если в массиве есть свободное место, элемент просто добавляется в конец:

elementData[size] = element;  // O(1)
size++;

Сценарий 2: Расширение массива (реаллокация) - O(n)

// Когда массив полон, нужна реаллокация
ArrayList<Integer> list = new ArrayList<>(1);
list.add(1);  // size=1, capacity=1
list.add(2);  // size=1, capacity=1 -> НУЖНА РЕАЛЛОКАЦИЯ!

Внутренний процесс:

private void ensureCapacityInternal(int minCapacity) {
    if (minCapacity > elementData.length) {
        grow(minCapacity);
    }
}

private void grow(int minCapacity) {
    // Увеличиваем размер на 50% (capacity = oldCapacity + oldCapacity >> 1)
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    // Копируем все элементы в новый массив - O(n)!
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Процесс расширения:

1. Выделяется новый (больший) массив
2. Все старые элементы копируются в новый массив - O(n)
3. Старый массив помечается для сборки мусора
4. Новый элемент добавляется

Сценарий 3: Добавление в середину - O(n) худший случай

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);

// Добавляем в начало (худший случай)
list.add(0, 0);  // O(n)

Метод add(int index, E element):

public void add(int index, E element) {
    // Проверка индекса
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException();
    
    ensureCapacityInternal(size + 1);
    
    // Сдвиг всех элементов от index на одну позицию
    System.arraycopy(elementData, index, 
                     elementData, index + 1, 
                     size - index);  // O(n-index)
    
    elementData[index] = element;
    size++;
}

Визуализация:

// Было: [1, 2, 3]
// Добавляем 0 в позицию 0
// Этап 1: сдвиг элементов (O(n))
System.arraycopy(elementData, 0, elementData, 1, 3);
// Результат: [1, 1, 2, 3]
// Этап 2: вставка нового элемента
elementData[0] = 0;
// Результат: [0, 1, 2, 3]

Амортизированная сложность O(1)

Хотя реаллокация - это O(n), она происходит редко. При добавлении n элементов:

ArrayList<Integer> list = new ArrayList<>(1);

// Анализ:
// add(1) -> size=1, capacity=1 -> Реаллокация: 1 копирование
// add(2) -> size=2, capacity=1 (новая) -> Реаллокация: 2 копирования  
// add(3) -> size=3, capacity=3 -> Нет реаллокации
// add(4) -> size=4, capacity=3 -> Реаллокация: 3 копирования
// add(5) -> size=5, capacity=4 -> Нет реаллокации
// ...
// add(n) -> требует log(n) реаллокаций

// Общее количество копирований:
// 1 + 2 + 3 + 6 + 9 + ... ≈ O(n)
// n операций всего -> O(n)/n = O(1) в среднем (амортизированная)

Стратегия расширения

ArrayList увеличивает размер на 50% (или 1.5x):

int newCapacity = oldCapacity + (oldCapacity >> 1);

Это лучше, чем увеличение на 1:

// На 1: реаллокация при каждом добавлении -> O(n) каждый раз
// На 1.5x: экспоненциальный рост -> O(1) в среднем

Таблица сложности операций ArrayList

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

public class ArrayListComplexityDemo {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>(1);
        
        long startTime = System.nanoTime();
        for (int i = 0; i < 100_000; i++) {
            list.add(i);  // O(1) амортизированная
        }
        long endTime = System.nanoTime();
        
        // Линейное время ~O(n)
        System.out.println("Время: " + (endTime - startTime) / 1_000_000 + "ms");
        
        // Добавление в начало - намного медленнее
        startTime = System.nanoTime();
        list.add(0, -1);  // O(n) - нужно сдвинуть 100_000 элементов
        endTime = System.nanoTime();
        System.out.println("Добавление в начало: " + (endTime - startTime) / 1_000_000 + "ms");
    }
}

Выводы

✅ O(1) - добавление в конец (при наличии места или часто) ✅ O(n) амортизированная - повторяющиеся добавления ⚠️ O(n) - добавление в начало или середину ⚠️ O(n) - при необходимости реаллокации

Для операций вставки в начало лучше использовать LinkedList, где это O(1).