Почему сложность добавления элемента в начало и в конец List равна константе?

Почему сложность добавления элемента в начало и конец List равна константе?

Этот вопрос проверяет понимание различных реализаций List в Java и алгоритмической сложности операций.

Уточнение: О какой List идёт речь?

Важно: это НЕ верно для всех List реализаций:

• LinkedList: добавление в начало O(1), в конец O(1)
• ArrayList: добавление в начало O(n), в конец O(1) амортизированно
• CopyOnWriteArrayList: добавление O(n)

Скорее всего, вопрос о LinkedList.

LinkedList: Почему O(1)?

LinkedList состоит из узлов (nodes), связанных друг с другом:

public class LinkedList<E> {
    private Node<E> first;
    private Node<E> last;
    private int size;
    
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}

Добавление в конец:

public boolean add(E e) {
    linkLast(e);  // Добавляет в конец
    return true;
}

private void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
}

Здесь мы:

1. Берём ссылку на последний узел O(1) — поле last
2. Создаём новый узел O(1)
3. Обновляем ссылки O(1)
4. Увеличиваем size O(1)

Всё операции O(1), поэтому суммарно O(1).

Добавление в начало:

public void addFirst(E e) {
    linkFirst(e);
}

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
}

То же самое: O(1).

Почему ArrayList это НЕ может делать эффективно?

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

Когда вы добавляете в начало ArrayList:

• index = 0
• size - index = size (все элементы!)
• Нужно скопировать ВСЕ элементы на одну позицию вправо
• Это O(n)

List<Integer> list = new ArrayList<>();
for (int i = 0; i < 1000000; i++) {
    list.add(0, i);  // Добавляем в начало 1000000 раз
    // Каждый раз копируются все элементы!
    // Общая сложность: O(n²)
}

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

long start = System.nanoTime();
List<Integer> linked = new LinkedList<>();
for (int i = 0; i < 100000; i++) {
    linked.add(0, i);  // Добавление в начало
}
long linkedTime = System.nanoTime() - start;

start = System.nanoTime();
List<Integer> array = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
    array.add(0, i);  // Добавление в начало
}
long arrayTime = System.nanoTime() - start;

System.out.println("LinkedList: " + linkedTime);
System.out.println("ArrayList: " + arrayTime);
// ArrayList примерно в 1000+ раз медленнее!

Правильный ответ

LinkedList позволяет добавлять элементы в начало и конец за O(1), потому что:

1. Он использует двусвязный список (doubly-linked list)
2. Хранит ссылки на first и last узлы
3. Добавление требует только обновления нескольких ссылок

ArrayList не может этого делать:

1. Требует смещение всех элементов
2. O(n) для добавления в начало
3. O(1) амортизированно только для конца

Кейс использования

Используй LinkedList если:

// Часто добавляешь/удаляешь из начала или конца
Queue<Task> queue = new LinkedList<>();
Deque<Page> history = new LinkedList<>();

Используй ArrayList если:

// Часто обращаешься по индексу
List<User> users = new ArrayList<>();
int user = users.get(i);  // O(1)

// Часто добавляешь в конец
users.add(newUser);  // O(1) амортизировано

Итоги

• LinkedList: O(1) для добавления в начало и конец благодаря ссылкам на first/last
• ArrayList: O(1) только для конца, O(n) для начала
• Запомни: LinkedList хорош для очередей/стеков, ArrayList хорош для случайного доступа