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

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

Ответ: O(n)

Вставка элемента в начало ArrayList имеет линейную временную сложность O(n), где n — количество элементов в списке.

Почему O(n)?

Структура ArrayList:

public class ArrayList<E> extends AbstractList<E> implements List<E> {
    private Object[] elementData;  // Внутренний массив
    private int size;              // Количество элементов
}

Вставка в начало требует:

1. Сдвига всех элементов на одну позицию вправо — это O(n)
2. Помещения нового элемента на позицию 0 — это O(1)

Визуальная демонстрация

Исходный список: [A, B, C, D, E]

Вставляем X в начало:
1. Сдвигаем элементы: [_, A, B, C, D] (E теряется)
2. Вставляем X:        [X, A, B, C, D]

Все 5 элементов нужно было переместить → O(n)

Код операции add(0, element)

public void add(int index, E element) {
    rangeCheckForAdd(index);
    
    // Проверка, нужна ли расширение массива
    if (size == elementData.length)
        elementData = grow();  // O(n) — создание нового массива и копирование
    
    // Сдвиг элементов
    System.arraycopy(elementData, index, 
                     elementData, index + 1,  // Вся операция O(n)
                     size - index);
    
    elementData[index] = element;  // O(1)
    size++;
}

System.arraycopy — встроенная функция, которая:

• Требует скопировать все элементы от index до конца
• Для вставки в начало (index=0) скопирует ВСЕ элементы
• Это занимает O(n) времени

Примеры разных операций

ArrayList<String> list = new ArrayList<>();
list.add("A");  // add("A")      → O(1) амортизированный
list.add("B");  // add("B")      → O(1) амортизированный
list.add("C");  // add("C")      → O(1) амортизированный
list.add("D");
list.add("E");

// Текущее состояние: [A, B, C, D, E]

list.add(0, "X");   // add(0, "X")   → O(n) — все сдвигаются!
list.add(2, "Y");   // add(2, "Y")   → O(n) — элементы с индекса 2 сдвигаются
list.add(5, "Z");   // add(5, "Z")   → O(1) или O(n)?

Анализ add(5, "Z"):

Текущее состояние: [X, A, B, Y, C, D, E]  (размер = 7, индекс 5 указывает на D)

Операция: System.arraycopy(data, 5, data, 6, 7-5)

Это скопирует элементы 5 и 6 (то есть D и E) на позиции 6 и 7
Сложность: O(2) = O(1) для небольшого количества элементов
Но в общем случае это O(n - index)

Сравнение операций

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

// Добавление в конец
for (int i = 0; i < 10000; i++) {
    list.add(i);  // O(1) амортизированный
}
// Общее время: ~O(10000)

// Добавление в начало (ПЛОХО!)
ArrayList<Integer> badList = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
    badList.add(0, i);  // O(n) на каждой итерации!
}
// Общее время: O(1 + 2 + 3 + ... + 10000) = O(n²) ← Очень плохо!

LinkedList — лучше для вставки в начало

LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 10000; i++) {
    linkedList.addFirst(i);  // O(1) — просто создаёт новый узел
}
// Общее время: O(10000)

ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
    arrayList.add(0, i);  // O(n) на каждой итерации
}
// Общее время: O(n²) = O(100_000_000) ← Медленнее!

Измерение производительности

import java.util.*;

public class ListPerformanceTest {
    public static void main(String[] args) {
        int size = 10000;
        
        // ArrayList
        long startTime = System.currentTimeMillis();
        List<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            arrayList.add(0, i);  // Вставка в начало
        }
        long arrayListTime = System.currentTimeMillis() - startTime;
        
        // LinkedList
        startTime = System.currentTimeMillis();
        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            linkedList.add(0, i);  // Вставка в начало
        }
        long linkedListTime = System.currentTimeMillis() - startTime;
        
        System.out.println("ArrayList добавление в начало: " + arrayListTime + "ms");
        System.out.println("LinkedList добавление в начало: " + linkedListTime + "ms");
        // Вывод примерно:
        // ArrayList добавление в начало: 1500ms  ← O(n²)
        // LinkedList добавление в начало: 15ms   ← O(n)
    }
}

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

Операция                ArrayList    LinkedList
─────────────────────────────────────────────────
add(E)                 O(1)*        O(1)
add(0, E)              O(n)         O(1)
add(n-1, E)            O(1)*        O(n)
get(int)               O(1)         O(n)
remove(int)            O(n)         O(n)*
remove(0)              O(n)         O(1)
contains(E)            O(n)         O(n)

* амортизированный или в худшем случае

Правильный способ: используй LinkedList или переверни список

Вариант 1: LinkedList для частых вставок в начало

List<Integer> list = new LinkedList<>();
for (int i = 0; i < 10000; i++) {
    list.add(0, i);  // O(1) для LinkedList
}

Вариант 2: Добавь в конец, потом переверни

List<Integer> list = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
    list.add(i);  // O(1) — быстро добавляем в конец
}
Collections.reverse(list);  // O(n) — один раз переворачиваем

Вариант 3: Используй Stack (вместо add(0, x))

Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < 10000; i++) {
    stack.push(i);  // O(1) — эффективнее
}
// Итерировать нужно в обратном порядке
while (!stack.isEmpty()) {
    int value = stack.pop();
    // ...
}

Ключевые моменты

• Вставка в начало ArrayList: O(n) из-за необходимости сдвига всех элементов
• Вставка в конец ArrayList: O(1) амортизированный — нет сдвига
• LinkedList для вставок в начало: O(1) — просто создание нового узла
• Не делай циклов с add(0, x) на ArrayList — это будет O(n²)!
• Используй LinkedList, если часто вставляешь в начало/конец