Класс LinkedList в Java

Цикл for (int i = 0; i < list.size(); i++) { list.get(i); } выглядит безобидно, но на LinkedList из 100 000 элементов он делает около 2,5 миллиарда переходов по ссылкам: каждый вызов get(i) заново идёт к нужному узлу от начала или конца списка. Тот же обход циклом for-each делает 100 000 шагов. Причина — в том, как устроен этот класс.

LinkedList (java.util.LinkedList) — это реализация двусвязного списка (linked list) в Java: каждый элемент хранится в отдельном узле со ссылками на предыдущий и следующий узлы. Класс реализует сразу два интерфейса — List и Deque, поэтому работает как список, очередь, двусторонняя очередь и стек. Добавление и удаление на концах выполняется за O(1), доступ по индексу — за O(n). LinkedList допускает любые значения, в том числе null, и не потокобезопасен.

Реализация LinkedList в Java: узлы Node

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

Так выглядит фрагмент исходного кода LinkedList в современном JDK (Java 7 и новее, включая Java 8, 17 и 21):

public class LinkedList<E> extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable {

    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;

    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;
        }
    }
    // ...
}

Node — хороший пример статического вложенного класса: узлу не нужна ссылка на объект списка, поэтому он объявлен static. У первого узла prev == null, у последнего next == null.

Графически LinkedList из четырёх элементов A, B, C и D можно представить так (стрелки — ссылки next и prev):

Как работает get(index) в LinkedList

Метод get(index) не может сразу перейти к нужной ячейке, как массив: он идёт по ссылкам от узла к узлу. Чтобы сократить путь, JDK начинает с ближнего конца — с first, если индекс в первой половине, и с last, если во второй:

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;
    }
}

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

ArrayList vs LinkedList: в чём разница

ArrayList хранит элементы в массиве и даёт доступ по индексу за O(1), а LinkedList хранит их в связанных узлах: доступ по индексу у него O(n), зато вставка и удаление на найденной позиции не сдвигают остальные элементы. В большинстве задач быстрее ArrayList, а LinkedList выбирают для частых операций на обоих концах или вставок через итератор.

Удаление элемента B из середины связного списка сводится к перезаписи двух ссылок: A.next теперь указывает на C, а C.prev — на A. Остальные узлы не трогаются:

Но чтобы удалить B вызовом remove(1) или remove("B"), его сначала нужно найти, а это проход по цепочке за O(n). O(1) получается только тогда, когда узел уже под рукой: на концах списка или в текущей позиции итератора.

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

Конструкторы LinkedList

У LinkedList два конструктора: без параметров — пустой список — и с коллекцией, элементы которой копируются в новый список в порядке её итератора. Конструктора с начальной ёмкостью нет: массива внутри нет, и резервировать место заранее не нужно.

Переменную, как и для других коллекций, объявляют типом интерфейса: List<String> list = new LinkedList<>(); — если нужны методы списка, или Deque<String> deque = new LinkedList<>(); — если очереди.

Методы LinkedList: пример и сложность

Методы LinkedList приходят из двух интерфейсов: из List — работа по индексу (add(i, e), get(i), set(i, e), remove(i)), из Deque — работа с концами (addFirst(), addLast(), removeFirst(), removeLast(), peek(), poll()). Методы на концах выполняются за O(1), методы с индексом — за O(n).

В примере ниже переменная объявлена классом LinkedList, а не интерфейсом. В обычном коде так не делают, но здесь это сделано специально: через тип LinkedList доступны и методы List, и методы Deque одновременно.

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();

        list.add("F");
        list.add("B");
        list.add("D");
        list.add("E");
        list.add("C");
        list.addLast("Z");
        list.addFirst("A");
        list.add(1, "A2");
        System.out.println("Содержимое: " + list);

        list.remove("F");
        list.remove(2);
        list.removeFirst();
        list.removeLast();
        System.out.println("Содержимое после удаления: " + list);

        String val = list.get(2);
        list.set(2, val + "+");
        System.out.println("Содержимое после изменения: " + list);
    }
}

Вывод:

Содержимое: [A, A2, F, B, D, E, C, Z]
Содержимое после удаления: [A2, D, E, C]
Содержимое после изменения: [A2, D, E+, C]

Разберём по шагам:

• add() добавляет F, B, D, E, C в конец списка в том же порядке; addLast("Z") — тоже в конец, addFirst("A") — в начало, а add(1, "A2") вставляет A2 в позицию 1 (индексация с нуля).
• remove("F") удаляет объект F, после чего список — [A, A2, B, D, E, C, Z]; remove(2) удаляет элемент с индексом 2, то есть B. Затем removeFirst() убирает A, а removeLast() — Z.
• get(2) возвращает E, а set(2, "E+") заменяет его, не меняя размер списка.

Сложность основных методов и их поведение на пустом списке:

Методы getFirst(), removeFirst() и родственные были у LinkedList всегда (из Deque); с Java 21 они объявлены и в List через SequencedCollection (подробнее). Методы, общие для всех списков, разобраны в уроке Интерфейс List и ArrayList.

LinkedList как очередь и стек

LinkedList реализует Deque, поэтому один и тот же объект может работать как очередь FIFO (offer() в хвост, poll() из головы) и как стек LIFO (push() и pop() в голове). При этом он остаётся списком: в любой момент доступны индексы и toString() показывает элементы от головы к хвосту.

Что выведет этот код?

import java.util.LinkedList;

public class LinkedListDequeExample {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);        // в конец
        list.push(2);       // в начало, как в стек
        list.offer(3);      // в конец, как в очередь
        list.addFirst(4);   // в начало
        System.out.println(list);

        System.out.println(list.pop());
        System.out.println(list.poll());
        System.out.println(list.peekLast());
        System.out.println(list);
    }
}

Вывод:

[4, 2, 1, 3]
4
2
3
[1, 3]

Здесь легко ошибиться: push() добавляет в начало, а add() и offer() — в конец. И pop(), и poll() забирают элемент из головы, поэтому сначала вышла 4, затем 2. peekLast() только смотрит на хвост, не удаляя его. Полный перечень методов очередей и разница между парами offer/add и poll/remove — в уроке Интерфейсы Queue и Deque.

Как перебирать LinkedList и вставлять в середину

LinkedList перебирают циклом for-each, методом forEach() или явным итератором — каждый из этих способов проходит список за O(n). Цикл for с get(i) для LinkedList не подходит: каждый вызов ищет узел заново, и обход превращается в O(n²).

Отсюда и цифра из начала урока. Для списка из n элементов get(i) делает примерно min(i, n − i) шагов, а в сумме по всем индексам это около n²/4: для 100 000 элементов — около 2,5 миллиарда переходов по ссылкам. Итератор же просто запоминает текущий узел и на каждом шаге переходит к next.

Итератор нужен и для того, чтобы получить настоящую вставку и удаление за O(1): ListIterator стоит на найденном узле, и его методы add() и remove() меняют только соседние ссылки.

import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class LinkedListIteratorExample {
    public static void main(String[] args) {
        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]

Элемент B2 вставлен сразу после B, а C удалён — и всё за один проход, без повторного поиска позиции. Если вместо it.add() и it.remove() вызвать list.add() или list.remove() внутри цикла, следующий it.next() бросит ConcurrentModificationException. Все методы ListIterator (previous(), set(), nextIndex()) описаны в уроке Интерфейс ListIterator.