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

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

Сложность добавления в ArrayList зависит от того, КУДА вы добавляете элемент. Это очень важный нюанс на собеседовании.

Добавление в конец (O(1) amortized)

Добавление в конец ArrayList — это O(1) амортизированная сложность:

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

Почему амортизированная? Потому что массив работает с резервной емкостью:

// Внутренне ArrayList как-то так работает:
private int[] elementData = new int[10]; // Емкость = 10
private int size = 0;

public void add(E e) {
    if (size == elementData.length) {
        // Нужно расширить массив - O(n) операция!
        elementData = Arrays.copyOf(elementData, elementData.length * 2);
    }
    elementData[size++] = e;
}

Мост раз добавление O(1), но когда массив переполняется, требуется O(n) копирование. Но это происходит редко (по логарифме), поэтому амортизированная сложность O(1).

ArrayList<String> list = new ArrayList<>();
// После каждого добавления показываю внутреннюю емкость

list.add("A");      // size=1, capacity=10 -> O(1)
list.add("B");      // size=2, capacity=10 -> O(1)
list.add("C");      // size=3, capacity=10 -> O(1)
// ...
list.add("J");      // size=10, capacity=10 -> O(1)
list.add("K");      // size=11, capacity=20 -> O(n)! Расширение
list.add("L");      // size=12, capacity=20 -> O(1)

Добавление в конкретную позицию (O(n))

Добавление в середину или начало — это O(n) худшем случае:

ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

list.add(0, "X"); // O(n) - нужно сдвинуть все элементы
// [X, A, B, C]

list.add(2, "Y"); // O(n) - сдвиг с позиции 2 до конца
// [X, A, Y, B, C]

Почему O(n)? Потому что нужно сдвинуть все элементы после позиции вставки:

public void add(int index, E element) {
    // ...
    // Сдвиг всех элементов на 1 позицию вправо - O(n)
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

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

До:   [A, B, C, D, E]
       ^  ^  ^  ^  ^
      0  1  2  3  4

Добавляем "X" на позицию 1:

Шаг 1: Сдвиг [B, C, D, E] на одну позицию вправо
       [A, ?, ?, ?, ?, E]
       
Шаг 2: Вставка X
       [A, X, B, C, D, E]

Удаление элемента (O(n))

Удаление также O(n) в худшем случае:

list.remove(0); // O(n) - нужно сдвинуть все элементы
list.remove(list.size() - 1); // O(1) - удаление с конца
list.remove(2); // O(n) - сдвиг элементов

Сравнение с LinkedList

Вот почему структура данных имеет значение:

ArrayList<String> arrayList = new ArrayList<>();
LinkedList<String> linkedList = new LinkedList<>();

// Добавление в конец
arrayList.add("A");       // O(1) amortized
linkedList.add("A");      // O(1)

// Добавление в начало
arrayList.add(0, "X");    // O(n) - сдвиг всех элементов
linkedList.add(0, "X");   // O(1) - просто создать новый узел

// Доступ по индексу
arrayList.get(5);         // O(1) - прямой доступ
linkedList.get(5);        // O(n) - нужно пройти 5 узлов

Таблица сложности

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

Хорошо - добавление в конец:

List<Integer> numbers = new ArrayList<>();
for (int i = 1; i <= 1000000; i++) {
    numbers.add(i);  // O(1) amortized - быстро!
}

Плохо - добавление в начало:

List<Integer> numbers = new ArrayList<>();
for (int i = 1000000; i >= 1; i--) {
    numbers.add(0, i);  // O(n) каждый раз - очень медленно!
}
// Лучше развернуть в конце, чем добавлять в начало

Оптимизация с LinkedList:

// Если часто добавляем в начало, используй LinkedList
List<Integer> queue = new LinkedList<>();
for (int i = 1000000; i >= 1; i--) {
    queue.add(0, i);  // O(1) - быстро
}

Важные нюансы

1. Амортизированная сложность — в среднем O(1), но иногда одна операция O(n)
2. Worst case — если часто добавлять в середину, это будет медленнее
3. Разрастание массива — обычно в 1.5 раза (зависит от реализации)
4. Удаление в конец — O(1), но удаление в начало O(n)

Заключение

• Добавление в конец ArrayList: O(1) амортизированная
• Добавление в середину: O(n)
• Удаление: O(n) в худшем случае
• Амортизированная сложность означает, что в среднем быстро, но иногда бывает медленно
• Выбирайте LinkedList, если часто добавляете/удаляете в начало/середину