Обход связного списка является фундаментальной техникой работы с этой структурой данных. В отличие от массива, здесь нет случайного доступа по индексу, поэтому движение происходит шаг за шагом по ссылкам. У обхода есть разные варианты. Каждый из них решает свои задачи и имеет нюансы: где-то легко забыть обновить указатель, где-то важно учесть границы.

Освоение всех типов обхода даёт уверенность и готовит к более сложным приёмам: реверсу, удалению, работе с двумя указателями.

Виды обхода

1. Классический обход

Идея: Последовательно пройти от head до null, обработать каждый узел.

Где применяют: Печать значений, подсчёт длины, поиск первого совпадения, подготовка к более сложным техникам.

Как работает (pseudocode):

public void traverse(Node head) { // вход: голова списка
    Node current = head;          // начинаем с головы
    while (current != null) {     // пока не дошли до конца
        process(current);         // обработка узла
        current = current.next;   // переход к следующему
    }
}

Подводные камни:

• Обработка пустого списка: цикл не должен начинаться, если head == null.

• При долгих проверках лучше предусматривать ранний выход, чтобы не проходить список до конца без нужды.

Ошибки:

• Забытое обновление current = current.next ведёт к бесконечному циклу.

• Мутирование ссылок current.next внутри цикла без сохранения временной переменной может порвать цепочку.

2. Обход с prev + current

Идея: одновременно хранить ссылки на предыдущий (prev) и текущий (current) узлы. Это нужно, потому что в односвязном списке нет ссылки назад, и без prev невозможно безопасно менять связи.

Где применяют: удаление или вставка в середину списка, задачи, где нужно знать «соседа слева».

Как работает (pseudocode):

public void traverseWithPrev(Node head) {   // вход: голова списка
    Node prev = null;                       // изначально перед головой нет узла
    Node current = head;                    // начинаем с головы
    while (current != null) {               // пока не дошли до конца
        // логика с использованием prev и current
        prev = current;                     // сдвигаем prev вперёд
        current = current.next;             // сдвигаем current вперёд
    }
}

Подводные камни:

• После удаления узла нельзя сразу сдвигать prev, иначе следующий элемент будет пропущен.

• Если список хранит ссылку на tail, её нужно обновлять отдельно при изменении последнего элемента.

Ошибки:

• Попытка применить технику к двусвязному списку как «обратный обход» — это неверно: для двусвязного списка используется prev внутри узлов, а не переменная.

• Забыта обработка случая prev == null при удалении головы.

3. Обход до предпоследнего узла (penultimate node)

Идея: пройти список так, чтобы остановиться на узле, который стоит перед хвостом.

Где применяют: удаление последнего элемента, обновление tail в односвязном списке, вставка в конец без сохранённого tail.

Как работает (pseudocode):

public Node findPenultimate(Node head) {  // вход: голова списка
    if (head == null) return null;        // пустой список
    Node current = head;                  // старт с головы
    while (current.next != null           // есть следующий
           && current.next.next != null) {// и после него ещё есть узел
        current = current.next;           // двигаемся вперёд
    }
    return current;                       // current — предпоследний, current.next — хвост
}

Подводные камни:

• Длины 0 и 1: предпоследнего не существует, логику нужно завершать заранее.

• Длина 2: цикл не выполнится ни разу, и current уже будет указывать на предпоследний.

Ошибки:

• Проверка только current != null вместо current.next и current.next.next, что приводит к обращению к null.

• После удаления хвоста забыто обнулить current.next = null и, при наличии поля tail, не обновлён tail = current.

4. Обход по индексу

Идея: дойти до позиции i последовательным движением от head, так как у LinkedList нету случайного доступа по индексу как в массивах.

Где применяют: вставка или удаление по индексу, доступ к k-му элементу, поиск узла-предшественника для операций в середине.

Как работает (pseudocode):

public Node getNodeAtIndex(Node head, int i) { // вход: голова списка и индекс i
    Node current = head;                       // старт с головы
    int currIdx = 0;                           // текущий индекс
    while (current != null && currIdx < i) {   // двигаемся, пока не дошли до i
        current = current.next;                // шаг вперёд
        currIdx += 1;                          // увеличиваем индекс
    }
    return current; // либо узел с индексом i, либо null если i за границами
}

Подводные камни:

• Индекс 0 тут голова (head). Для i == 0 часто лучше вызывать «вставку в голову» или «удаление головы».

• Если поддерживается tail и известно size, то i == size вставка в хвост, удобно делегировать в addAtTail.

• Размер может быть неизвестен. Тогда выход за границы нужно обрабатывать по факту current == null.

Ошибки:

• Нет проверки на выход за границы: использование current.next, когда current == null.

• Смешивание логики: попытка вручную обрабатывать все случаи в одном цикле вместо делегирования краевых случаев в Head/Tail.

• Неверная остановка цикла (<= вместо <), что приводит к попаданию на узел с индексом i+1.

5. Обратный обход (для двусвязного списка)

Идея: идти от хвоста к голове по ссылкам prev. Работает только в двусвязном списке (у каждого узла есть next и prev).

Где применяют: печать в обратном порядке, симметричные проверки (сравнение крайних элементов), задачи «от конца к началу», некоторые реализации LRU.

Как работает (pseudocode):

public void reverseTraverse(Node tail) { // вход: хвост списка
    Node current = tail; // начинаем с хвоста
    while (current != null) { // пока не дошли до начала
        process(current);  // обработка узла
        current = current.prev; // шаг назад
    }
}

Подводные камни:

• При вставках/удалениях нужно обновлять обе ссылки: и next, и prev; любая несогласованность ломает обход.

• Если структура хранит head и tail, убедиться, что они корректно меняются при операциях на краях.

Ошибки:

• Попытка сделать обратный обход в односвязном списке (нет prev).

• Забыто обновить prev/next у обоих соседей при вставке или удалении, из-за чего цепочка рвётся.

• Неправильная инициализация: начать с head вместо tail (получится прямой обход).

Пример (Java)

На LeetCode и на собеседованиях обычно дают только head, чтобы проверить умение работать с указателями. В реальной разработке чаще используют обёртку LinkedList или готовые коллекции, скрывающие внутреннее устройство.

public void printLinkedList(Node head) {
    Node current = head;

    while (current != null) {
        System.out.println(current.value); // обработка узла
        current = current.next;
    }
}

Recommended LeetCode Practice

Используйте JUMBAQ Framework для систематичного решения leetcode задач

1290. Convert Binary Number in a Linked List to Integer

📌 Главная идея: Traversal это фундаментальная техника для связного списка. Без неё невозможны поиск, удаление, реверс и все более сложные паттерны.