Зависит ли время добавления элемента в ArrayList от количества имеющихся элементов

# Зависит ли время добавления элемента в ArrayList от количества элементов

Это классический вопрос на собеседованиях Java разработчиков, касающийся сложности и производительности структур данных.

Прямой ответ

Обычно НЕ зависит (в большинстве случаев — O(1) amortized), но есть исключение: если нужно расширить внутренний массив, то добавление может быть O(n).

Как работает ArrayList

public class ArrayList<E> extends AbstractList<E> implements List<E> {
    // Внутренний массив
    private Object[] elementData;
    // Текущий размер
    private int size;
    
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;
        return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        if (minCapacity - elementData.length > 0)
            grow(minCapacity); // Если нет места - расширяем!
    }
}

Две ситуации

Ситуация 1: Есть свободное место в массиве (O(1))

Если внутренний массив elementData еще имеет свободные слоты, добавление нового элемента — это просто присваивание значения:

ArrayList<Integer> list = new ArrayList<>();
list.add(1);  // Создается массив на 10 элементов
list.add(2);  // O(1) - просто добавляем в index 1
list.add(3);  // O(1) - просто добавляем в index 2
// ... и так до 10 элементов - все O(1)

Ситуация 2: Нет свободного места (O(n))

Когда массив полный, ArrayList расширяет его размер, создавая новый массив и копируя все старые элементы:

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

// Теперь массив полный! Следующее добавление:
list.add(10);  // O(n) - нужно скопировать все 10 элементов в новый массив!

Реализация расширения в Java

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // Новая емкость = старая * 1.5 + 1
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity < minCapacity)
        newCapacity = minCapacity;
    
    // Копируем все элементы в новый массив - O(n)!
    return elementData = Arrays.copyOf(elementData, newCapacity);
}

Анализ сложности (Amortized)

При добавлении N элементов:

Добавления 1-9:      O(1) каждое
Добавление 10:       O(1) + O(9) копирования = O(n)
Добавления 11-14:    O(1) каждое
Добавление 15:       O(1) + O(14) копирования = O(n)
...

Общая сложность добавления N элементов: O(n) amortized
В среднем на один элемент: O(1) amortized

Практическое значение

// Если вы знаете точный размер - используйте конструктор!
ArrayList<Integer> list = new ArrayList<>(10000);
for (int i = 0; i < 10000; i++) {
    list.add(i);  // Никакого расширения массива
}

Сравнение с LinkedList

// ArrayList: O(1) amortized добавление в конец
list.add(element);

// LinkedList: O(1) добавление в конец (но медленнее на практике)
linkedList.add(element);

// ArrayList: O(n) добавление в начало
list.add(0, element);

// LinkedList: O(1) добавление в начало (но нужен итератор)
linkedList.addFirst(element);

Итоговый ответ

В большинстве случаев время добавления в ArrayList НЕ зависит от количества элементов и составляет O(1).

Исключение: когда нужно расширить внутренний массив (примерно каждые 50% добавлений), операция становится O(n), но такие дорогостоящие операции происходят редко, поэтому amortized сложность остается O(1).

Это одна из причин, почему ArrayList — отличный выбор для последовательного добавления элементов в конец списка.