Какой будет скорость доступа к элементу LinkedList?

Скорость доступа к элементам в LinkedList

Временная сложность

Доступ к элементам в LinkedList имеет O(n) временную сложность, где n — это позиция элемента в списке. Это существенно медленнее, чем в ArrayList с его O(1).

Почему LinkedList медленнее?

LinkedList — это двусвязный список (doubly linked list), где каждый элемент содержит:

• Значение (data)
• Ссылку на следующий элемент (next)
• Ссылку на предыдущий элемент (prev)

Чтобы получить элемент по индексу, Java должна пройти по цепочке ссылок от начала (или конца) списка до нужного элемента. Это требует O(n) операций.

Пример: как работает поиск элемента

LinkedList<Integer> list = new LinkedList<>();
list.add(10);  // [10]
list.add(20);  // [10] -> [20]
list.add(30);  // [10] -> [20] -> [30]
list.add(40);  // [10] -> [20] -> [30] -> [40]

// Доступ к элементу по индексу:
Integer element = list.get(3);  // O(n) — требуется пройти 3 узла

Для получения элемента с индексом 3:

1. Начинаем с первого узла (10)
2. Переходим на второй узел (20)
3. Переходим на третий узел (30)
4. Переходим на четвёртый узел (40) — нашли!

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

Практический пример производительности

import java.util.*;

public class ListPerformance {
    public static void main(String[] args) {
        int size = 100000;
        
        // Создаём ArrayList
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            arrayList.add(i);
        }
        
        // Создаём LinkedList
        LinkedList<Integer> linkedList = new LinkedList<>(arrayList);
        
        // Тест доступа к элементам
        long startArray = System.nanoTime();
        for (int i = 0; i < size; i++) {
            int value = arrayList.get(i);
        }
        long endArray = System.nanoTime();
        
        long startLinked = System.nanoTime();
        for (int i = 0; i < size; i++) {
            int value = linkedList.get(i);
        }
        long endLinked = System.nanoTime();
        
        System.out.println("ArrayList: " + (endArray - startArray) + " нс");
        System.out.println("LinkedList: " + (endLinked - startLinked) + " нс");
        System.out.println("LinkedList медленнее в " + 
            ((double)(endLinked - startLinked) / (endArray - startArray)) + " раз");
    }
}

Обычно LinkedList медленнее в 100-1000 раз для последовательного доступа к элементам по индексу.

Оптимизация: итератор вместо get(i)

Если нужна итерация по LinkedList, используй Iterator вместо get(i):

LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");

// ❌ Плохо: O(n²) для цикла по индексам
for (int i = 0; i < list.size(); i++) {
    String element = list.get(i);  // O(n) для каждого элемента!
}

// ✅ Хорошо: O(n) для итератора
for (String element : list) {  // использует Iterator
    System.out.println(element);
}

// ✅ Хорошо: явный Iterator
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String element = it.next();
    System.out.println(element);
}

Итератор работает за O(1) на каждый элемент, потому что просто следует по ссылкам next.

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

LinkedList полезен когда:

• Частые вставки/удаления в начало или конец — O(1) против O(n) у ArrayList
• Не нужен случайный доступ — используешь Iterator
• Реализуешь Queue или Deque — LinkedList имеет методы addFirst(), removeLast()

// LinkedList как очередь (Queue)
Queue<Integer> queue = new LinkedList<>();
queue.add(1);      // O(1)
queue.remove();    // O(1)
queue.peek();      // O(1)

// LinkedList как двусторонняя очередь (Deque)
Deque<String> deque = new LinkedList<>();
deque.addFirst("A");   // O(1)
deque.addLast("B");    // O(1)
deque.removeFirst();   // O(1)
deque.removeLast();    // O(1)

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

ArrayList предпочтителен когда:

• Нужен случайный доступ — get(i) за O(1)
• Мало операций вставки/удаления в начало
• Нужна лучшая производительность в целом
• Нужно экономить память — ArrayList компактнее

Резюме

Доступ к элементу по индексу в LinkedList — это O(n) операция, так как требуется проход по ссылкам от начала списка. Для случайного доступа всегда используй ArrayList. Для LinkedList лучше использовать Iterator или операции с началом/концом списка.