Какие сложности основных операций LinkedList

Сложность основных операций в LinkedList

LinkedList — это важная структура данных в Java Collections Framework. Давайте разберём временную сложность (Big O) её операций.

Структура LinkedList

LinkedList представляет собой двусвязный список, где каждый элемент содержит ссылку на предыдущий и следующий элементы:

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

Основные операции и их сложность

1. Добавление элементов (add)

В начало списка — O(1)

LinkedList<Integer> list = new LinkedList<>();
list.addFirst(10);  // O(1) — просто добавить в начало
list.addFirst(20);  // O(1)
list.addFirst(30);  // O(1)
// list: [30, 20, 10]

// или
list.add(0, 40);    // O(1) — добавить на позицию 0

В конец списка — O(1)

list.addLast(50);   // O(1) — просто добавить в конец
list.add(100);      // O(1) — добавить в конец

В середину списка — O(n)

list.add(5, 999);   // O(n) — нужно пройти до позиции 5
// Худший случай: добавление в середину = O(n/2) ≈ O(n)

// Почему так долго?
// 1. Нужно найти позицию 5 — проход через 5 элементов
// 2. Нужно изменить ссылки на этой позиции

2. Удаление элементов (remove)

Удаление первого элемента — O(1)

list.removeFirst();  // O(1) — просто удалить начало
list.remove();       // O(1) — удалить первый элемент (FIFO)

Удаление последнего элемента — O(1)

list.removeLast();   // O(1) — просто удалить конец

Удаление элемента по индексу — O(n)

list.remove(5);      // O(n) — нужно найти позицию 5
// LinkedList должен пройти через 5 элементов для доступа

Удаление конкретного элемента — O(n)

list.remove("target");  // O(n) — нужно найти элемент
list.removeFirstOccurrence("target");  // O(n)
list.removeLastOccurrence("target");   // O(n)

3. Доступ к элементам (get)

Доступ по индексу — O(n)

Integer first = list.get(0);     // O(1) — первый элемент (оптимизировано)
Integer second = list.get(1);    // O(1) или O(2) (оптимизировано)
Integer middle = list.get(500);  // O(500) — нужно пройти
Integer last = list.get(999);    // O(1) — последний элемент (оптимизировано)

Почему так медленно? LinkedList должен начать с начала и пройти по всем элементам до нужного:

Список: [A] ← prev/next → [B] ← → [C] ← → [D]

Доступ к C:
1. Начало: A
2. Следующий: B
3. Следующий: C ← нашли (3 шага для индекса 2)

Оптимизация в Java (Java оптимизирует для начала и конца):

private Node<E> node(int index) {
    if (index < (size >> 1)) {  // Если менее чем половина
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {  // Если больше чем половина
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

4. Поиск элемента (indexOf, contains)

Поиск элемента — O(n)

int index = list.indexOf("target");      // O(n) — может быть в конце
boolean contains = list.contains("target");  // O(n)
list.lastIndexOf("target");              // O(n)

В худшем случае нужно проверить все элементы:

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

5. Итерация (iteration)

Итерация всех элементов — O(n)

// Правильно — O(n)
for (Integer value : list) {
    System.out.println(value);  // Используется iterator
}

// Неправильно — O(n²)!
for (int i = 0; i < list.size(); i++) {
    Integer value = list.get(i);  // get() для каждого элемента = O(i)
}

Почему неправильный способ O(n²)?

get(0) = 1 шаг
get(1) = 2 шага
get(2) = 3 шага
...
get(n-1) = n шагов

Общо: 1 + 2 + 3 + ... + n = n(n+1)/2 ≈ n² шагов

6. Операции очереди (Queue Interface)

// O(1) операции
list.offer(element);     // O(1) — добавить в конец
list.poll();             // O(1) — удалить из начала
list.peek();             // O(1) — посмотреть начало
list.pollFirst();        // O(1)
list.peekFirst();        // O(1)

// O(1) операции для стека
list.push(element);      // O(1) — добавить в начало
list.pop();              // O(1) — удалить из начала

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

Когда использовать LinkedList

Хорошо для LinkedList:

Queue<String> queue = new LinkedList<>();
queue.offer("first");   // O(1)
queue.poll();           // O(1)

Stack<Integer> stack = new LinkedList<>();
stack.push(1);          // O(1)
stack.pop();            // O(1)

// Частые вставки/удаления в начало/конце
LinkedList<String> list = new LinkedList<>();
for (String item : items) {
    list.addLast(item);  // O(1) для каждой
}

Плохо для LinkedList:

LinkedList<Integer> list = new LinkedList<>();
// ... 1000000 элементов ...

// Плохо — O(500000) на каждый вызов
for (int i = 0; i < list.size(); i++) {
    Integer value = list.get(i);  // МЕДЛЕННО
}

// Хорошо — используй Iterator
for (Integer value : list) {
    // O(n) в сумме
}

Сравнение с ArrayList

*ArrayList: O(1) средний случай, O(n) при увеличении ёмкости

Рекомендации

1. Используй ArrayList для частого доступа по индексу
2. Используй LinkedList для Queue/Stack или частых вставок в начало
3. Никогда не используй list.get(i) в цикле для LinkedList
4. Используй Iterator или for-each для LinkedList итерации
5. Profile ваш код если сомневаетесь в производительности

Понимание сложности операций критично для выбора правильной структуры данных при разработке производительных приложений.