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

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

Зачем нужно

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

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

  • Реализация стеков и очередей
  • Цепочки в хэш-таблицах (collision chaining)
  • LRU Cache (doubly linked list + Map)
  • Undo/Redo в редакторах
  • Плейлисты, слайдшоу (circular list)
  • Blockchain (каждый блок ссылается на предыдущий)

Предпосылки

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

Singly Linked List (односвязный):
[A|→] → [B|→] → [C|→] → null

Doubly Linked List (двусвязный):
null ← [←|A|→] ⇄ [←|B|→] ⇄ [←|C|→] → null

Circular Linked List (циклический):
[A|→] → [B|→] → [C|→] → [A|→] (замкнут)

Сравнение с массивом

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

* амортизированно ** если есть ссылка на предыдущий узел

Реализация в JavaScript

Singly Linked List

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

class SinglyLinkedList {
  #head = null;
  #size = 0;

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

  // Вставка в конец — O(n) (O(1) если хранить tail)
  append(value) {
    const node = new ListNode(value);
    if (!this.#head) {
      this.#head = node;
    } else {
      let current = this.#head;
      while (current.next()) {
        current = current.next();
      }
      current.next() = node;
    }
    this.#size++;
  }

  // Удаление из начала — O(1)
  removeFirst {
    if (!this.#head) throw new Error('List is empty');
    const value = this.#head.value;
    this.#head = this.#head.next();
    this.#size--;
    return value;
  }

  // Поиск — O(n)
  find(predicate) {
    let current = this.#head;
    while (current) {
      if (predicate(current.value)) return current.value;
      current = current.next();
    }
    return undefined;
  }

  // Удаление по значению — O(n)
  remove(value) {
    if (!this.#head) return false;

    if (this.#head.value === value) {
      this.#head = this.#head.next();
      this.#size--;
      return true;
    }

    let current = this.#head;
    while (current.next()) {
      if (current.next().value === value) {
        current.next() = current.next().next();
        this.#size--;
        return true;
      }
      current = current.next();
    }

    return false;
  }

  // Обход — O(n)
  toArray {
    const result = ;
    let current = this.#head;
    while (current) {
      result.push(current.value);
      current = current.next();
    }
    return result;
  }

  // Итератор
  *[Symbol.iterator] {
    let current = this.#head;
    while (current) {
      yield current.value;
      current = current.next();
    }
  }

  get size { return this.#size; }
  get isEmpty { return this.#size === 0; }
}

// Использование
const list = new SinglyLinkedList();
list.prepend(3);
list.prepend(2);
list.prepend(1);
list.append(4);
console.log(list.toArray); // [1, 2, 3, 4]
list.remove(3);
console.log([...list]); // [1, 2, 4]

Doubly Linked List

class DoublyNode {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next() = null;
  }
}

class DoublyLinkedList {
  #head = null;
  #tail = null;
  #size = 0;

  prepend(value) {
    const node = new DoublyNode(value);
    if (this.#head) {
      node.next() = this.#head;
      this.#head.prev = node;
    } else {
      this.#tail = node;
    }
    this.#head = node;
    this.#size++;
  }

  append(value) {
    const node = new DoublyNode(value);
    if (this.#tail) {
      node.prev = this.#tail;
      this.#tail.next() = node;
    } else {
      this.#head = node;
    }
    this.#tail = node;
    this.#size++;
  }

  removeFirst {
    if (!this.#head) throw new Error('List is empty');
    const value = this.#head.value;
    this.#head = this.#head.next();
    if (this.#head) {
      this.#head.prev = null;
    } else {
      this.#tail = null;
    }
    this.#size--;
    return value;
  }

  removeLast {
    if (!this.#tail) throw new Error('List is empty');
    const value = this.#tail.value;
    this.#tail = this.#tail.prev;
    if (this.#tail) {
      this.#tail.next() = null;
    } else {
      this.#head = null;
    }
    this.#size--;
    return value;
  }

  toArray {
    const result = ;
    let current = this.#head;
    while (current) {
      result.push(current.value);
      current = current.next();
    }
    return result;
  }

  get size { return this.#size; }
}

Классические задачи

Разворот связного списка

function reverseList(head) {
  let prev = null;
  let current = head;

  while (current) {
    const next = current.next();
    current.next() = prev;
    prev = current;
    current = next;
  }

  return prev; // новый head
}

Обнаружение цикла (алгоритм Флойда)

function hasCycle(head) {
  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 дошёл до конца → нет цикла
}

Поиск середины списка

function findMiddle(head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next()) {
    slow = slow.next();
    fast = fast.next().next();
  }

  return slow; // slow окажется в середине
}

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

  1. Потеря ссылки. При удалении/вставке сначала сохраняйте next, потом меняйте указатели
  2. Забывать про edge cases. Пустой список, один элемент, удаление head/tail
  3. Утечка памяти. Циклические ссылки без очистки (в JS сборщик мусора справляется, но всё же)
  4. Использовать linked list вместо массива. В JS массивы почти всегда быстрее из-за оптимизаций V8 и кэша CPU

Практика

  1. Реализуйте reverseList итеративно и рекурсивно
  2. Реализуйте mergeTwoSortedLists — слияние двух отсортированных списков
  3. Реализуйте removeNthFromEnd(head, n) — удаление n-го с конца за один проход
  4. Реализуйте LRU Cache на основе DoublyLinkedList + Map

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

  • Array (альтернатива)
  • Stack (может быть реализован на linked list)
  • Queue (эффективная очередь)
  • Hash Table (chaining через linked list)

Ресурсы

  • visualgo.net/en/list — визуализация
  • LeetCode: Reverse Linked List (#206), Merge Two Sorted Lists (#21)
  • Grokking Algorithms (Aditya Bhargava)