Основы связных списков

Список как цепочка узлов

Связный список состоит из узлов. В простейшем варианте каждый узел хранит значение и ссылку next на следующий узел. Ссылка на первый узел обычно называется head, а у последнего узла next == null.

class Node {
    int value;
    Node next;

    Node(int value) {
        this.value = value;
    }
}

Сам список не обязан хранить элементы в одном непрерывном участке памяти. Порядок задаётся ссылками: какой узел указан в next, тот и считается следующим.

Доступ только по цепочке

Чтобы получить третий элемент, нельзя обратиться к нему как к array[2]. Нужно начать с head и дважды перейти по next. Поэтому поиск элемента по позиции занимает O(n) в худшем случае.

Node current = head;

while (current != null) {
    System.out.println(current.value);
    current = current.next;
}

Такой проход посещает каждый узел ровно один раз и работает за O(n). Главная проверка в цикле — сам current: после последнего узла он становится null.

Почему вставка может быть O(1)

Если ссылка на нужный узел уже известна, вставить новый узел сразу после него можно несколькими переназначениями ссылок. Размер списка при этом не влияет на количество операций.

Node added = new Node(15);

added.next = current.next;
current.next = added;

Но если сначала нужно найти current, стоимость поиска никуда не исчезает. Поэтому фраза «вставка в связный список — O(1)» верна только когда позиция уже представлена ссылкой на подходящий узел.