Как рассчитать время работы с LinkedList

# Как рассчитать время работы с LinkedList

Время работы операций с LinkedList зависит от позиции элемента в списке. Вот полный анализ.

1. Базовые операции и их сложность

LinkedList структура

Node1 ←→ Node2 ←→ Node3 ←→ Node4
head                          tail

Каждый Node имеет:

• Data (значение)
• Next указатель
• Previous указатель (для DoublyLinkedList)

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

2. Анализ сложности get(index)

public E get(int index) {
    checkElementIndex(index);  // O(1)
    
    // LinkedList оптимизирована: выбирает ближайший конец
    return node(index).item;   // O(n/2) → O(n)
}

private Node<E> node(int index) {
    // Если индекс ближе к началу — начиная с head
    if (index < size >> 1) {  // index < size/2
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;  // Одна итерация = O(1)
        return x;        // В итоге O(index)
    }
    // Если ближе к концу — начиная с tail
    else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;  // В итоге O(size - index)
        return x;
    }
}

3. Практический расчёт времени

Пример 1: Доступ к элементам

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

// Худший случай: доступ к середине
long start = System.nanoTime();
int element = list.get(500_000);  // O(n/2) = 500_000 операций
long duration = System.nanoTime() - start;

System.out.println("Time: " + duration + "ns");
// На современном компьютере: ~50-100ms

Пример 2: Iteation (правильный способ)

// ❌ НЕПРАВИЛЬНО: O(n²)
LinkedList<String> list = new LinkedList<>();
for (int i = 0; i < 10_000; i++) {
    list.add("item" + i);
}

long start = System.nanoTime();
for (int i = 0; i < list.size(); i++) {
    String item = list.get(i);  // O(n) для каждого элемента!
    // Всего: O(10_000 * 10_000 / 2) = 50 млн операций
}
long duration1 = System.nanoTime() - start;
System.out.println("get(i) loop: " + duration1 + "ns");  // ~1 секунда!

// ✅ ПРАВИЛЬНО: O(n)
start = System.nanoTime();
for (String item : list) {  // Iterator, O(1) для каждого
    // Всего: O(10_000) операций
}
long duration2 = System.nanoTime() - start;
System.out.println("Iterator loop: " + duration2 + "ns");  // ~10ms

// duration1 / duration2 ≈ 100x медленнее!

4. Iterator vs get()

Iterator реализация

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;  // Помнит текущую позицию
    private int nextIndex;
    
    public boolean hasNext() {
        return nextIndex < size;  // O(1)
    }
    
    public E next() {
        lastReturned = next;
        next = next.next;  // Просто переходим на следующий узел O(1)
        nextIndex++;
        return lastReturned.item;
    }
}

// Использование Iterator
LinkedList<String> list = new LinkedList<>();
for (String item : list) {
    // Это использует Iterator.next() — O(1) для каждого элемента
    // Всего O(n)
}

Сравнение

get(i):          head → node1 → node2 → ... → nodei  (O(i))
get(i+1):        head → node1 → node2 → ... → nodei → nodei+1  (O(i+1))
...
Всего для n элементов: O(n²)

Iterator:
node1.next() → node2  (O(1))
node2.next() → node3  (O(1))
...
Всего для n элементов: O(n)

5. Add vs Insert

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

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

long start = System.nanoTime();
for (int i = 0; i < 1_000_000; i++) {
    list.add(i);  // O(1) — добавляет в tail
}
long duration = System.nanoTime() - start;
System.out.println("Time: " + (duration / 1_000_000) + "ms");
// ~50ms для 1млн элементов

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

long start = System.nanoTime();
for (int i = 0; i < 100_000; i++) {
    list.add(0, i);  // O(1) для поиска начала, но...
                      // нужно обновить указатели — O(1)
                      // Всего O(n) из-за сдвига других узлов
}
long duration = System.nanoTime() - start;
System.out.println("Time: " + (duration / 1_000_000) + "ms");
// ~500ms для 100k элементов (из-за перестроения)

6. LinkedList vs ArrayList

Операция: get()

ArrayList<Integer> arrayList = new ArrayList<>();
LinkedList<Integer> linkedList = new LinkedList<>();

for (int i = 0; i < 1_000_000; i++) {
    arrayList.add(i);
    linkedList.add(i);
}

// get(500_000) — середина
long start1 = System.nanoTime();
int val1 = arrayList.get(500_000);  // O(1) — просто индекс
long time1 = System.nanoTime() - start1;

long start2 = System.nanoTime();
int val2 = linkedList.get(500_000);  // O(n/2) — половина итераций
long time2 = System.nanoTime() - start2;

System.out.println("ArrayList: " + time1 + "ns");  // ~10ns
System.out.println("LinkedList: " + time2 + "ns");  // ~1_000_000ns
// LinkedList на 100_000x медленнее!

Операция: add() в начало

long start1 = System.nanoTime();
for (int i = 0; i < 10_000; i++) {
    arrayList.add(0, i);  // O(n) — нужно сдвинуть все элементы
}
long time1 = System.nanoTime() - start1;

long start2 = System.nanoTime();
for (int i = 0; i < 10_000; i++) {
    linkedList.add(0, i);  // O(1) — просто обновить указатели
}
long time2 = System.nanoTime() - start2;

System.out.println("ArrayList: " + (time1 / 1_000_000) + "ms");  // ~1000ms
System.out.println("LinkedList: " + (time2 / 1_000_000) + "ms");  // ~10ms
// LinkedList на 100x быстрее!

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

Хорошо для:

• Операции с начало/конец (add(0), removeFirst())
• Частые вставки/удаления в середину (если есть Iterator)
• Случаи, когда неизвестен размер заранее

Плохо для:

• Случайный доступ по индексу (get(i))
• Иттерирование в цикле с get(i)
• Если нужна производительность (используй ArrayList)

8. Реальный пример: правильный паттерн

public class LinkedListAnalysis {
    
    // ❌ ПЛОХО: O(n²)
    public static void slowIteration(LinkedList<Integer> list) {
        for (int i = 0; i < list.size(); i++) {
            int val = list.get(i);  // O(i) для каждого
        }
    }
    
    // ✅ ХОРОШО: O(n)
    public static void fastIteration(LinkedList<Integer> list) {
        for (int val : list) {  // Использует Iterator
            // O(1) для каждого элемента
        }
    }
    
    // ✅ ХОРОШО: O(n)
    public static void fastIteratorIteration(LinkedList<Integer> list) {
        Iterator<Integer> it = list.iterator();
        while (it.hasNext()) {
            int val = it.next();  // O(1)
        }
    }
    
    // ❌ ПЛОХО: O(n²)
    public static void addBeginning(LinkedList<Integer> list) {
        for (int i = 0; i < 100_000; i++) {
            list.add(0, i);  // O(n) из-за перестроения
        }
    }
    
    // ✅ ХОРОШО: O(n)
    public static void addEnd(LinkedList<Integer> list) {
        for (int i = 0; i < 100_000; i++) {
            list.add(i);  // O(1) добавление в конец
        }
    }
}

9. Формула расчёта времени

Для LinkedList.get(index):
  Если index < size/2:
    Time = index * (time per node traversal)
  Иначе:
    Time = (size - index) * (time per node traversal)
  
На современном компьютере:
  Time per node traversal ≈ 100-200 ns
  
Пример:
  LinkedList размер 1млн, доступ к элементу 500k
  Time = 500_000 * 150ns = 75ms

10. Оптимизация

// Если часто нужен доступ по индексу — используй ArrayList
List<Integer> list = new ArrayList<>();

// Если часто добавляешь/удаляешь в начало — используй LinkedList с add(0)
// Но лучше переорганизовать логику

// Если нужна очередь (add в конец, remove из начала) — используй Queue
Queue<Integer> queue = new LinkedList<>();
queue.add(1);       // O(1)
int first = queue.poll();  // O(1)

// Если нужен стек (add в конец, remove из конца) — используй Deque
Deque<Integer> stack = new LinkedList<>();
stack.push(1);      // O(1)
int top = stack.pop();  // O(1)

Вывод

Время работы LinkedList зависит от операции:

1. get(index): O(n) — ищет от ближайшего конца
2. add()/remove() в конец: O(1) — быстро
3. add()/remove() в начало: O(1) для операции, но может быть O(n) для логики
4. Iterator/enhanced for: O(n) — используйте для полного обхода
5. get(i) в цикле: O(n²) — избегайте!

Правило: Используйте LinkedList для Queue/Deque, ArrayList для всего остального.