Какая сложность получения элемента в середине в LinkedList?

Какая сложность получения элемента в середине в LinkedList?

Прямой ответ: O(n)

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

Почему O(n)?

LinkedList — это связный список, не массив:

ArrayList (массив):     LinkedList (связный список):
index:  0  1  2  3      node: A  B  C  D
value: 10 20 30 40      value: 10 20 30 40
                        links: A->B->C->D

get(2) = O(1)           get(2) = O(n) нужно пройти
(прямой доступ по       через A, B, C
индексу в памяти)

Анализ операции get(int index)

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;  // node() — O(n)
}

private Node<E> node(int index) {
    // Оптимизация: если index < size/2, ищем с начала
    // иначе ищем с конца
    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; i > index; i--) {
            x = x.prev;  // Проход в обратном направлении
        }
        return x;
    }
}

Практический пример

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

// Получение элемента в конце
int element = list.get(999);  // O(n/2) - проход от конца

// Получение элемента в начале
int element = list.get(0);    // O(1) - вершина

// Получение элемента в середине
int element = list.get(500);  // O(n/2) - проход половину

Сравнение LinkedList vs ArrayList

❌ Антипаттерн: Итерация по LinkedList через get()

// МЕДЛЕННО: O(n²)
for (int i = 0; i < linkedList.size(); i++) {
    int value = linkedList.get(i);  // get() каждый раз O(n)
    System.out.println(value);
}
// Итого: O(1 + 2 + 3 + ... + n) = O(n²)
// Для 1000 элементов: 500,000 операций!

✓ Правильный способ: Iterator

// БЫСТРО: O(n)
Iterator<Integer> iterator = linkedList.iterator();
while (iterator.hasNext()) {
    int value = iterator.next();  // O(1)
    System.out.println(value);
}

// Или for-each (использует Iterator)
for (Integer value : linkedList) {  // O(n)
    System.out.println(value);
}

Почему Iterator быстрее?

// Iterator хранит текущую позицию
private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned = null;
    private Node<E> next;  // Текущая позиция
    
    public E next() {
        lastReturned = next;  // O(1) - просто переходим к следующему
        next = next.next;     // O(1) - по ссылке
        return lastReturned.item;
    }
}

// vs get(index) каждый раз ищет с начала
// get(0) - от первого элемента
// get(1) - снова от первого! (не помнит где был)
// get(2) - снова от первого!

Выводы

LinkedList.get(index):

• ✗ O(n) сложность
• ✗ Никогда не используй в цикле по индексам
• ✓ Используй Iterator для итерации
• ✓ Хорош для add/remove в начало/конец

Используй LinkedList для:

• Очередей (Queue, Deque)
• Частого добавления/удаления в начало/конец
• Итерации через Iterator

Используй ArrayList для:

• Случайного доступа по индексу
• Большинства других случаев