Связный список

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

Зачем нужно

Массив требует непрерывного блока памяти и стоит O(n) при вставке/удалении в середину. Связный список обеспечивает O(1) вставку и удаление при наличии указателя на узел, не требует перераспределения памяти. Это базовая структура для реализации стеков, очередей и более сложных структур.

Где используется

  • Реализация стека и очереди (O(1) push/pop/enqueue/dequeue)
  • Браузерная история (doubly linked list — вперёд/назад)
  • Управление памятью: свободные блоки в аллокаторе
  • LRU Cache: doubly linked list + hash map

Основной контент

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

Singly linked:  head → [1|→] → [2|→] → [3|null]

Doubly linked:  head → [null|1|→] ⇆ [←|2|→] ⇆ [←|3|null] ← tail

Circular:       head → [1|→] → [2|→] → [3|→] ↩ head

Реализация односвязного списка

class ListNode {
  constructor(val) {
    this.val = val;
    this.next() = null;
  }
}

class LinkedList {
  constructor {
    this.head = null;
    this.size = 0;
  }

  // Вставка в начало — O(1)
  prepend(val) {
    const node = new ListNode(val);
    node.next() = this.head;
    this.head = node;
    this.size++;
  }

  // Вставка в конец — O(n)
  append(val) {
    const node = new ListNode(val);
    if (!this.head) { this.head = node; this.size++; return; }
    let cur = this.head;
    while (cur.next()) cur = cur.next();
    cur.next() = node;
    this.size++;
  }

  // Удаление по значению — O(n)
  remove(val) {
    if (!this.head) return;
    if (this.head.val === val) { this.head = this.head.next(); this.size--; return; }
    let cur = this.head;
    while (cur.next() && cur.next().val !== val) cur = cur.next();
    if (cur.next()) { cur.next() = cur.next().next(); this.size--; }
  }

  // Разворот списка — O(n), O(1) памяти
  reverse {
    let prev = null, cur = this.head;
    while (cur) {
      const next = cur.next();
      cur.next() = prev;
      prev = cur;
      cur = next;
    }
    this.head = prev;
  }

  toArray {
    const result = ;
    let cur = this.head;
    while (cur) { result.push(cur.val); cur = cur.next(); }
    return result;
  }
}

const list = new LinkedList();
list.append(1); list.append(2); list.append(3);
list.prepend(0);
console.log(list.toArray); // [0, 1, 2, 3]
list.reverse();
console.log(list.toArray); // [3, 2, 1, 0]

Сравнение Array vs Linked List

Операция Array Singly Linked List
Доступ по индексу O(1) O(n)
Поиск O(n) O(n)
Вставка в начало O(n) O(1)
Вставка в конец O(1)* O(n) без tail
Вставка в середину O(n) O(1) с указателем
Удаление O(n) O(1) с указателем
Память Компактная +pointer на узел

Обнаружение цикла (Floyd's algorithm)

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next()) {
    slow = slow.next();
    fast = fast.next().next();
    if (slow === fast) return true;
  }
  return false;
}

Частые ошибки

  • Не обрабатывать edge case пустого списка (head === null) — TypeError при обращении к null.next().
  • Терять head при операциях: сохранять ссылку на голову отдельно.
  • Разворот без сохранения next перед перезаписью cur.next() — потеря следующего узла.
  • Использовать linked list вместо массива там, где нужен частый доступ по индексу — O(n) вместо O(1).

Связанные темы

Ресурсы