Класс LinkedList в Java - Вопросы

LinkedList — двусвязный список, массива внутри нет. Каждый элемент лежит в отдельном объекте-узле Node — статическом вложенном классе с полями item (сам элемент), next (следующий узел) и prev (предыдущий узел). Сам список хранит только ссылки на первый (first) и последний (last) узлы и количество элементов (size). У первого узла prev == null, у последнего next == null.

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

В старых книгах узел называется Entry с полем element, а список замкнут в кольцо через пустой узел header — так было до Java 6 включительно. С Java 7 используются Node, first и last; принцип двусвязного списка не изменился.

get(index) не может сразу перейти к нужной ячейке, как массив: внутренний метод node() идёт по ссылкам от узла к узлу. Чтобы сократить путь, он начинает с ближнего конца — с first, если индекс в первой половине, и с last, если во второй. Поэтому get(0) и get(size() - 1) выполняются сразу, а элемент в середине ищется до n/2 шагов — это O(n). Через тот же node() работают set(i, e), add(i, e) и remove(i).

Цикл for (int i = 0; i < list.size(); i++) list.get(i); ищет каждый узел заново, и обход становится O(n²): в сумме около n²/4 переходов, для 100 000 элементов — около 2,5 миллиарда. For-each, forEach() и явный итератор запоминают текущий узел и проходят список за O(n) — те же 100 000 шагов.

Только когда узел уже найден. Сама перелинковка стоит O(1): чтобы удалить B из A–B–C, достаточно переписать A.next на C и C.prev на A, остальные узлы не трогаются. Но add(i, e), remove(i) и remove(Object) сначала ищут узел проходом по цепочке, поэтому в сумме это O(n).

Настоящее O(1) бывает в двух случаях: на концах списка (addFirst(), addLast(), removeFirst(), removeLast()) и в текущей позиции ListIterator, который уже стоит на узле:

List<String> list = new LinkedList<>(List.of("A", "B", "C", "D"));
ListIterator<String> it = list.listIterator();
while (it.hasNext()) {
    String s = it.next();
    if (s.equals("B")) it.add("B2");     // вставка после B за O(1)
    else if (s.equals("C")) it.remove(); // удаление C за O(1)
}
System.out.println(list); // [A, B, B2, D]

ArrayList хранит элементы в массиве Object[], а LinkedList — в связанных узлах Node. Отсюда разница в сложности:

• get(i), set(i, e): у ArrayList O(1), у LinkedList O(n), до n/2 переходов;
• add(0, e), remove(0): у ArrayList O(n) (сдвиг массива), у LinkedList O(1);
• add(i, e), remove(i) в середине: O(n) у обоих (у LinkedList — на поиск узла);
• вставка/удаление через ListIterator: у ArrayList O(n), у LinkedList O(1).

На практике ArrayList часто быстрее даже там, где у LinkedList оценка лучше: элементы массива лежат в памяти подряд и хорошо попадают в кэш процессора, а System.arraycopy() сдвигает ссылки очень быстро. Узел LinkedList занимает около 24 байт, узлы разбросаны по куче, и каждый переход по next — возможный промах кэша.

Поэтому по умолчанию для списка берут ArrayList, а LinkedList — для частых вставок и удалений через итератор или на обоих концах, когда преимущество подтверждено замером. Даже автор класса Джошуа Блох признался: «I wrote it, and I never use it».

Конструкторов два. LinkedList() создаёт пустой список (first == last == null, size == 0), узлы появляются только при добавлении. LinkedList(Collection<? extends E> c) копирует элементы c в порядке её итератора; при c == null бросается NullPointerException, а null-элементы внутри c допускаются. Конструктора с ёмкостью нет: new LinkedList<>(100) не компилируется.

LinkedList реализует сразу List и Deque, поэтому переменную объявляют тем интерфейсом, который нужен: List<String> list = new LinkedList<>(); — для работы по индексу, Deque<String> deque = new LinkedList<>(); — для очереди или стека. Через переменную типа List методы Deque (push(), pollLast()) недоступны. В роли стека push() и pop() работают с головой, а add() и offer() добавляют в хвост.

null хранить можно: элемент лежит в поле item отдельного узла, и null там ничему не мешает (в отличие от ArrayDeque, который отмечает пустые ячейки массива значением null). contains(null) и indexOf(null) его находят. Но в роли очереди это рискованно: poll() и peekFirst() возвращают null и для пустого списка, и отличить одно от другого нельзя.

Потокобезопасности нет: при одновременной записи из нескольких потоков ссылки узлов могут разойтись, и элементы потеряются. Простой вариант — Collections.synchronizedList(new LinkedList<>()), для очереди между потоками лучше ConcurrentLinkedDeque или LinkedBlockingDeque.

Итераторы LinkedList — fail-fast: если внутри обхода вызвать list.add() или list.remove(), следующий it.next() бросит ConcurrentModificationException. Изменять список во время обхода нужно методами самого итератора.