Когда лучше использовать LinkedList?

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

Основные различия

ArrayList - динамический массив с случайным доступом (O(1)). LinkedList - двусвязный список с последовательным доступом (O(n)).

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

Сравнение производительности

public class ListPerformanceComparison {
    static final int SIZE = 100_000;
    
    public static void main(String[] args) {
        // ArrayList: быстрый доступ по индексу
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();
        
        // Заполнение: O(n) для обоих
        for (int i = 0; i < SIZE; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }
        
        // ДОСТУП ПО ИНДЕКСУ: ArrayList O(1), LinkedList O(n)
        long start = System.nanoTime();
        int element = arrayList.get(SIZE - 1);  // ~1 микросекунда
        long arrayTime = System.nanoTime() - start;
        
        start = System.nanoTime();
        element = linkedList.get(SIZE - 1);     // ~10,000 микросекунд!
        long linkedTime = System.nanoTime() - start;
        
        System.out.println("ArrayList access: " + arrayTime + " ns");
        System.out.println("LinkedList access: " + linkedTime + " ns");
        System.out.println("LinkedList в " + (linkedTime / arrayTime) + "x медленнее");
    }
}

Когда LinkedList работает ЛУЧШЕ?

1. Частые операции вставки/удаления в начале или конце

public class LinkedListAdvantage {
    // СЦЕНАРИЙ 1: Queue (очередь) - вставка в конец, удаление из начала
    public static void queueExample() {
        LinkedList<String> queue = new LinkedList<>();
        
        // addLast() - O(1) для LinkedList
        queue.add("task1");
        queue.add("task2");
        queue.add("task3");
        
        // removeFirst() - O(1) для LinkedList
        String task = queue.removeFirst(); // O(1) - БЫСТРО!
        
        // ArrayList.remove(0) - O(n) потому что нужно сдвинуть все элементы
        // ArrayList эффективнее для добавления в конец, но удаление с начала медленное
    }
    
    // СЦЕНАРИЙ 2: Deque (двусторонняя очередь)
    public static void dequeExample() {
        LinkedList<Integer> deque = new LinkedList<>();
        
        // Все операции на обоих концах - O(1)
        deque.addFirst(1);      // O(1)
        deque.addLast(2);       // O(1)
        int first = deque.removeFirst();  // O(1)
        int last = deque.removeLast();    // O(1)
        
        // ArrayList - только addLast() и removeLast() - O(1)
        // removeFirst() - O(n)
    }
    
    // СЦЕНАРИЙ 3: Удаление элементов из середины при итерации
    public static void removeMidIteration() {
        LinkedList<String> items = new LinkedList<>(Arrays.asList(
            "a", "b", "c", "d", "e"
        ));
        
        // LinkedList: удаление элемента - O(1) если есть Iterator
        Iterator<String> iter = items.iterator();
        while (iter.hasNext()) {
            String item = iter.next();
            if (item.equals("c")) {
                iter.remove();  // O(1) для LinkedList!
            }
        }
        
        // ArrayList.remove() during iteration - может быть медленнее
        // и рискует ConcurrentModificationException
    }
}

Когда LinkedList работает ХУЖЕ?

public class LinkedListDisadvantage {
    // ❌ ПЛОХО: Частой доступ по индексу
    public void badExample1() {
        LinkedList<Integer> list = new LinkedList<>();
        // добавление элементов
        
        // Каждый get() проходит по списку с начала - O(n)!
        for (int i = 0; i < list.size(); i++) {
            int value = list.get(i);  // O(n) для каждого элемента!
            // Общая сложность: O(n^2) !!!
        }
    }
    
    // ✅ ХОРОШО: Итератор вместо индексов
    public void goodExample1() {
        LinkedList<Integer> list = new LinkedList<>();
        
        // Итератор работает эффективно - O(1) для каждого элемента
        for (Integer value : list) {  // O(n) всего
            // process value
        }
    }
    
    // ❌ ПЛОХО: Вставка в конец огромного списка
    public void badExample2() {
        LinkedList<Integer> list = new LinkedList<>();
        
        // Доступ к последнему элементу если хранится неправильно
        // Оверхед по памяти: каждый узел хранит 2 ссылки + данные
        for (int i = 0; i < 1_000_000; i++) {
            list.add(i);  // O(1), но больше памяти чем ArrayList
        }
    }
}

Сравнение операций

Практические сценарии

Используй LinkedList если:

1. Реализуешь Queue/Deque

   Queue<Task> taskQueue = new LinkedList<>();
   taskQueue.offer(task);  // add в конец - O(1)
   Task next = taskQueue.poll();  // remove из начала - O(1)
   

2. Частые вставки/удаления в начале

   LinkedList<String> messages = new LinkedList<>();
   messages.addFirst(urgentMessage);  // O(1)
   

3. Удаление из итератора во время обхода

   LinkedList<Item> items = new LinkedList<>();
   Iterator<Item> iter = items.iterator();
   while (iter.hasNext()) {
       if (shouldRemove(iter.next())) {
           iter.remove();  // O(1)
       }
   }
   

Используй ArrayList в 99% случаев:

1. Доступ по индексу
2. Итерация элементов
3. Добавление в конец
4. Когда не знаешь, что использовать - ArrayList!\n

Реальный пример - неправильное использование LinkedList

// ❌ МЕДЛЕННО: O(n^2)
public List<Integer> slowReverseWithLinkedList(LinkedList<Integer> list) {
    List<Integer> reversed = new LinkedList<>();
    for (int i = list.size() - 1; i >= 0; i--) {
        reversed.add(list.get(i));  // get() - O(n) для LinkedList!
    }
    return reversed;  // O(n^2) всего
}

// ✅ БЫСТРО: O(n)
public List<Integer> fastReverse(LinkedList<Integer> list) {
    List<Integer> reversed = new LinkedList<>();
    Iterator<Integer> iter = list.descendingIterator();  // Итератор - O(1)
    while (iter.hasNext()) {
        reversed.add(iter.next());
    }
    return reversed;  // O(n) всего
}

Вывод

LinkedList - специализированная структура данных:

• Отлично работает для Queue и Deque операций
• Хорош для вставки/удаления в начале
• Плохой выбор для случайного доступа
• Больше памяти на элемент (две ссылки)

В 95% приложений используй ArrayList. LinkedList имеет смысл только если ты точно знаешь, что тебе нужно Queue или Deque поведение.