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

# Время добавления элемента в LinkedList

Ответ зависит от способа добавления. Это часто задаваемый вопрос, который проверяет глубокое понимание структуры данных LinkedList.

Краткий ответ

• Добавление в конец (append): O(1) амортизированная сложность
• Добавление в начало: O(1)
• Добавление по индексу: O(n)
• Поиск элемента для добавления: O(n)

Детальное объяснение

1. Добавление в конец (самый частый случай)

LinkedList<Integer> list = new LinkedList<>();
list.add(10);      // O(1) - добавляет в tail
list.add(20);      // O(1)
list.add(30);      // O(1)

Внутренняя реализация в Java:

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

private transient Node<E> first;  // голова
private transient Node<E> last;   // хвост - прямая ссылка!

public boolean add(E e) {
    linkLast(e);  // O(1) - просто обновляет last
    return true;
}

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;
}

Ключевой момент: LinkedList хранит прямую ссылку на последний элемент (last), поэтому добавление в конец не требует обхода всех элементов.

2. Добавление в начало

LinkedList<Integer> list = new LinkedList<>();
list.addFirst(10);  // O(1)
list.addFirst(20);  // O(1) - работает через first

public void addFirst(E e) {
    linkFirst(e);  // O(1)
}

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;
}

3. Добавление по индексу - O(n)!

LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 1000; i++) {
    list.add(i);
}

list.add(500, 999);  // O(n) - требует обхода на индекс 500!

Именно здесь появляется зависимость от количества элементов:

public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        linkLast(element);      // O(1)
    else
        linkBefore(element, node(index));  // O(n) для поиска node(index)
}

Node<E> node(int index) {
    // Оптимизация: начинаем с конца, если индекс > size/2
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;  // O(n) обход
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;  // O(n) обход в обратном направлении
        return x;
    }
}

4. Сравнение с ArrayList

// ArrayList
ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
    arrayList.add(i);  // O(1) amortized
}
arrayList.add(5000, 999);  // O(n) - сдвиг элементов

// LinkedList
LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 10000; i++) {
    linkedList.add(i);  // O(1) ✓ быстрее
}
linkedList.add(5000, 999);  // O(n) - поиск элемента

Практический пример проблемы

public void badExample() {
    LinkedList<String> list = new LinkedList<>();
    
    // Заполняем 10000 элементов
    for (int i = 0; i < 10000; i++) {
        list.add("Item " + i);  // O(1) каждый раз
    }
    
    // Плохо! O(n^2) сложность
    for (int i = 0; i < 10000; i++) {
        list.add(i, "New");  // O(n) каждый раз! ❌
    }
}

public void goodExample() {
    LinkedList<String> list = new LinkedList<>();
    
    for (int i = 0; i < 10000; i++) {
        list.add("Item " + i);  // O(1)
    }
    
    // Хорошо! O(n) сложность
    for (int i = 0; i < 10000; i++) {
        list.addFirst("New");  // O(1) ✓
    }
}

Оптимизация в Java 21+

LinkedList<String> list = new LinkedList<>();

// Используй ListIterator для вставок в середину
ListIterator<String> iter = list.listIterator(list.size());
for (int i = 0; i < 1000; i++) {
    iter.add("Item " + i);  // Быстрее на 50+%
}

Итоговая таблица

Выводы

1. Не добавляй в конец — LinkedList может быть медленнее ArrayList
2. Избегай операций по индексу — они O(n)
3. Используй ListIterator — для вставок в середину
4. LinkedList хорош для — очередей (Queue), стеков (Deque) с операциями на концах
5. Измеряй реальность — часто ArrayList быстрее из-за кэширования CPU

Это типичный вопрос, где многие путают теорию с практикой Java!