Какие плюсы и минусы хранения элементов в LinkedList?

Плюсы и минусы LinkedList в Java

LinkedList часто вызывает путаницу у junior разработчиков. Многие думают, что это универсальная альтернатива ArrayList, но это далеко не так. Давайте разберёмся, когда его стоит использовать, а когда это будет катастрофой.

Что такое LinkedList

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

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

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;  // Двусвязный список
    
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Плюсы LinkedList

1. Быстрое добавление/удаление в начало и конец

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

// O(1) — очень быстро!
list.addFirst("Element");
list.addLast("Element");
list.removeFirst();
list.removeLast();

public void addFirst(E e) {
    linkFirst(e);  // Всего пара операций
}

В ArrayList это было бы O(n) из-за сдвига элементов.

2. Быстрое добавление/удаление в середину (если у вас есть итератор)

ListIterator<Integer> it = list.listIterator(50);
it.add(999);      // O(1) если у вас уже есть итератор
it.remove();      // O(1) если у вас уже есть итератор

Это намного быстрее, чем вызывать list.add(50, 999) в ArrayList.

3. Реализует Deque (double-ended queue)

// LinkedList — это Queue и Deque
LinkedList<Integer> queue = new LinkedList<>();
queue.offer(1);    // Добавить в конец
queue.poll();      // Удалить из начала

// Идеально для очередей

4. Эффективен при удалении во время итерации

LinkedList<Integer> list = new LinkedList<>(Arrays.asList(1,2,3,4,5));

for (Iterator<Integer> it = list.iterator(); it.hasNext(); ) {
    Integer val = it.next();
    if (val % 2 == 0) {
        it.remove();  // O(1) удаление через итератор
    }
}
// Результат: [1, 3, 5]

Минусы LinkedList (и они серьёзные!)

1. Доступ по индексу O(n) вместо O(1)

LinkedList<Integer> list = new LinkedList<>(Arrays.asList(1,2,3,4,5));

// ArrayList: O(1)
int value = arrayList.get(3);  // Мгновенно

// LinkedList: O(n) !!!
int value = linkedList.get(3);  // Проходит по 3 элементам

// Для 1,000,000 элементов это будет тошнотворно медленно

Внутри LinkedList.get() проходит по всему списку:

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;  // node() проходит по всем элементам!
}

Node<E> node(int index) {
    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 - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

2. Больше памяти на элемент

ArrayList: один элемент занимает только место самого объекта
LinkedList: один элемент занимает место объекта + 2 ссылки (next, prev)

На 64-битной JVM:
ArrayList: 8 bytes для ссылки на объект
LinkedList: 8 + 8 + 8 = 24 bytes для Node

Для 1,000,000 элементов:
ArrayList: ~8 MB
LinkedList: ~24 MB + overhead на сами объекты Node

3. Плохая локальность кэша

// ArrayList: элементы в памяти рядом, CPU кэш работает отлично
int[] data = new int[1000];
for (int i = 0; i < 1000; i++) {
    sum += data[i];  // Cache hit! Очень быстро
}

// LinkedList: элементы разбросаны в памяти
// CPU кэш постоянно промахивается
LinkedList<Integer> list = new LinkedList<>();
for (Integer val : list) {
    sum += val;  // Cache miss! Медленно
}

4. Итерация немного медленнее

for (int i = 0; i < list.size(); i++) {
    process(list.get(i));  // ОЧЕНЬ медленно в LinkedList!
}

// Правильный способ:
for (Integer val : list) {
    process(val);  // Использует итератор, O(1) на элемент
}

5. Сложнее отладить

По моему опыту, LinkedList часто становятся источником performance issues, потому что это невидимо. Код выглядит правильно, но работает мучительно медленно.

Таблица сравнения

Операция        ArrayList    LinkedList
-------------------------------------
get(i)          O(1)         O(n)
add/remove конец O(1)         O(1)
add/remove нач.  O(n)        O(1)
add/remove сер.  O(n)        O(n) без итератора
Память          Меньше       Больше в 3 раза
Кэш             Отличный     Плохой

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

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

• Часто добавляешь/удаляешь в начало или конец
• Реализуешь Queue или Deque
• Удаляешь элементы через Iterator
• Размер фиксирован или очень мал (< 100 элементов)

LinkedList<Task> taskQueue = new LinkedList<>();
taskQueue.addLast(new Task("Job 1"));
Task next = taskQueue.removeFirst();

❌ НЕ используй, если:

• Часто обращаешься по индексу
• Размер большой (> 1000 элементов)
• Нужна максимальная производительность
• Просто хранишь данные и читаешь их

// ПЛОХО!
LinkedList<Integer> list = new LinkedList<>(1000000 элементов);
for (int i = 0; i < list.size(); i++) {
    int val = list.get(i);  // Ужасная производительность!
}

Мой совет

В 95% случаев используй ArrayList. LinkedList нужен только для специфических сценариев, когда ты явно работаешь с очередями или часто модифицируешь начало/конец списка. Если ты не уверен, что тебе нужен LinkedList — ты не нуждаешься в нём.

Запомни: преждевременная оптимизация — корень всех зол, но незнание сложности операций — корень всех performance issues.