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

# Временная сложность операций LinkedList

LinkedList в Java — это двусвязный список, где каждый узел содержит данные и ссылки на следующий и предыдущий узлы. Это влияет на производительность разных операций.

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

Детальный анализ

O(1) операции

LinkedList<Integer> list = new LinkedList<>();
list.add(1);      // O(1) - добавляет в конец, только обновляет last
list.add(2);
list.add(3);

list.addFirst(0); // O(1) - просто обновляет head и first указатель
list.addLast(4);  // O(1) - просто обновляет last указатель

list.removeFirst(); // O(1) - удаляет первый элемент
list.removeLast();  // O(1) - удаляет последний элемент

int first = list.getFirst(); // O(1) - прямой доступ к head
int last = list.getLast();   // O(1) - прямой доступ к tail

O(n) операции

// get(int index) - ВАЖНО: O(n)
// LinkedList должен обойти список с начала или конца
int element = list.get(500); // Если список из 1000 элементов
// Если index < size/2, начинается с головы
// Если index >= size/2, начинается с хвоста
// В худшем случае 500 переходов

// add(int index, E element) - O(n)
list.add(500, 999); // Нужно найти позицию 500, затем вставить
// Это требует 500 переходов + вставка O(1)

// remove(int index) - O(n)
list.remove(500); // Найти позицию 500, затем удалить

// contains(Object o) - O(n)
boolean has = list.contains(500); // Проверяет каждый элемент

// indexOf(Object o) - O(n)
int pos = list.indexOf(500); // Линейный поиск

Внутренняя структура

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

private transient Node<E> first;  // Быстрый доступ к началу
private transient Node<E> last;   // Быстрый доступ к концу
private transient int size;

// Оптимизация: get() выбирает начало или конец
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
    if (index < (size >> 1)) {      // index < size/2?
        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;
    }
}

Сравнение с ArrayList

Операция              | LinkedList | ArrayList
----------------------|------------|----------
add() в конец         | O(1)       | O(1) amortized
add(index, element)   | O(n)       | O(n)
get(index)            | O(n)       | O(1)
remove(index)         | O(n)       | O(n)
remove(object)        | O(n)       | O(n)
contains()            | O(n)       | O(n)
iterator traversal    | O(n)       | O(n)
Memory per element    | 24 bytes   | 8 bytes (2 ref + item)

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

// ХОРОШО: Частые операции в начале/конце
LinkedList<String> queue = new LinkedList<>();
queue.addLast("first");      // O(1)
queue.addLast("second");     // O(1)
String removed = queue.removeFirst(); // O(1)

// Реализация очереди или стека
LinkedList<Integer> stack = new LinkedList<>();
stack.push(1);    // addFirst()
stack.push(2);
int top = stack.pop(); // removeFirst()

// ПЛОХО: Частые операции по индексу
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 10000; i++) {
    list.add(list.get(i % list.size()), i); // O(n) для каждого get!
}
// Лучше использовать ArrayList

Практический пример: очередь сообщений

public class MessageQueue {
    private LinkedList<String> messages = new LinkedList<>();
    
    // O(1)
    public void enqueue(String message) {
        messages.addLast(message);
    }
    
    // O(1)
    public String dequeue() {
        return messages.removeFirst();
    }
    
    // O(1)
    public String peek() {
        return messages.getFirst();
    }
    
    // O(1)
    public int size() {
        return messages.size();
    }
}

// Использование
MessageQueue queue = new MessageQueue();
queue.enqueue("msg1"); // O(1)
queue.enqueue("msg2"); // O(1)
queue.dequeue();       // O(1) - очень эффективно!

Вывод

LinkedList эффективен для:

• Операций в начале/конце (O(1))
• Очередей и стеков
• Итерации по всем элементам

LinkedList неэффективен для:

• Доступа по индексу (O(n))
• Больших наборов данных (память = 3x больше)
• Частых поисков (O(n))

Правило: Если нужны операции по индексу → ArrayList. Если нужны операции на концах → LinkedList.