Linked List (Связный список)

Связный список — линейная структура, где каждый элемент (узел) хранит значение и ссылку на следующий узел. В отличие от массива, элементы не лежат в непрерывной памяти.

class ListNode<T> {
    value: T;
    next: ListNode<T> | null = null;
    constructor(value: T) {
        this.value = value;
    }
}

Операция	Связный список	Массив
Доступ по индексу	O(n)	O(1)
Вставка/удаление в начало	O(1)	O(n)
Вставка после известного узла	O(1)	O(n)
Удаление известного узла	O(n)* / O(1)	O(n)
Память	Указатель на каждый узел	Непрерывный блок

* Удаление известного узла в односвязном списке — O(n): нужен предшественник (трюк «скопировать next» не работает для хвоста). В двусвязном — O(1).

Разворот списка

function reverse<T>(head: ListNode<T> | null): ListNode<T> | null {
    let prev: ListNode<T> | null = null;
    let curr = head;
    while (curr) {
        const next = curr.next; // запомнить следующий
        curr.next = prev;       // развернуть указатель
        prev = curr;            // сдвинуть prev
        curr = next;            // сдвинуть curr
    }
    return prev; // новая голова
}

Техника «кролика и черепахи» (Floyd’s Cycle Detection)

Два указателя двигаются с разной скоростью: медленный (slow) на 1 шаг, быстрый (fast) на 2. Если в списке есть цикл — быстрый рано или поздно догонит медленного. Если цикла нет — fast дойдёт до конца (null).

function hasCycle<T>(head: ListNode<T> | null): boolean {
    let slow = head;
    let fast = head;
 
    while (fast && fast.next) {
        slow = slow!.next;        // +1 шаг
        fast = fast.next.next;    // +2 шага
        if (slow === fast) return true; // встретились — есть цикл
    }
 
    return false; // fast дошёл до конца — цикла нет
}

Та же техника (fast/slow) находит середину списка (когда fast дойдёт до конца, slow будет в середине) и начало цикла.

Виды связных списков

• Singly linked — ссылка только на next
• Doubly linked — ссылки на next и prev (двунаправленный обход)
• Circular — последний узел ссылается на первый

См. также

• two-pointers — техника fast/slow
• find-path — обход структур