Связный список полезен не потому, что ты будешь постоянно писать его в продакшене на JavaScript. Скорее наоборот: в реальных приложениях почти всегда выигрывает обычный массив. Но связный список хорошо показывает, как устроены базовые структуры данных без магии стандартной библиотеки.

Если объяснять коротко, односвязный список - это цепочка узлов, где каждый узел хранит значение и ссылку на следующий узел. Из этой простой идеи вырастают все основные операции: добавление, удаление, поиск и разворот списка.

Ниже соберем рабочую реализацию на JavaScript, а затем разберем, где такая структура действительно уместна и почему в UI-коде она нужна редко.

Как устроен односвязный список

У каждого узла есть два поля:

  • value - значение;
  • next - ссылка на следующий узел или null, если это конец списка.

Сам список обычно хранит две ссылки:

  • head - первый узел;
  • tail - последний узел.

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

Реализация LinkedListNode и LinkedList

Ниже полный рабочий пример односвязного списка:

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

  toString(callback) {
    return callback ? callback(this.value) : String(this.value);
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  prepend(value) {
    const newNode = new LinkedListNode(value, this.head);

    this.head = newNode;

    if (!this.tail) {
      this.tail = newNode;
    }

    return this;
  }

  append(value) {
    const newNode = new LinkedListNode(value);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      return this;
    }

    this.tail.next = newNode;
    this.tail = newNode;

    return this;
  }

  delete(value) {
    if (!this.head) {
      return null;
    }

    let deletedNode = null;

    while (this.head && this.head.value === value) {
      deletedNode = this.head;
      this.head = this.head.next;
    }

    let currentNode = this.head;

    while (currentNode && currentNode.next) {
      if (currentNode.next.value === value) {
        deletedNode = currentNode.next;
        currentNode.next = currentNode.next.next;
      } else {
        currentNode = currentNode.next;
      }
    }

    if (!this.head) {
      this.tail = null;
      return deletedNode;
    }

    this.tail = currentNode || this.head;

    return deletedNode;
  }

  find({ value, callback } = {}) {
    if (!this.head) {
      return null;
    }

    let currentNode = this.head;

    while (currentNode) {
      if (callback && callback(currentNode.value)) {
        return currentNode;
      }

      if (value !== undefined && currentNode.value === value) {
        return currentNode;
      }

      currentNode = currentNode.next;
    }

    return null;
  }

  deleteHead() {
    if (!this.head) {
      return null;
    }

    const deletedHead = this.head;

    this.head = this.head.next;

    if (!this.head) {
      this.tail = null;
    }

    return deletedHead;
  }

  deleteTail() {
    if (!this.tail) {
      return null;
    }

    const deletedTail = this.tail;

    if (this.head === this.tail) {
      this.head = null;
      this.tail = null;
      return deletedTail;
    }

    let currentNode = this.head;

    while (currentNode.next !== this.tail) {
      currentNode = currentNode.next;
    }

    currentNode.next = null;
    this.tail = currentNode;

    return deletedTail;
  }

  fromArray(values) {
    values.forEach((value) => this.append(value));
    return this;
  }

  toArray() {
    const nodes = [];
    let currentNode = this.head;

    while (currentNode) {
      nodes.push(currentNode);
      currentNode = currentNode.next;
    }

    return nodes;
  }

  toString(callback) {
    return this.toArray()
      .map((node) => node.toString(callback))
      .join(", ");
  }

  reverse() {
    let currentNode = this.head;
    let previousNode = null;

    this.tail = this.head;

    while (currentNode) {
      const nextNode = currentNode.next;
      currentNode.next = previousNode;
      previousNode = currentNode;
      currentNode = nextNode;
    }

    this.head = previousNode;

    return this;
  }
}

Пример использования:

const list = new LinkedList();

list.append("B");
list.append("C");
list.prepend("A");

console.log(list.toString()); // "A, B, C"
console.log(list.find({ value: "B" }).value); // "B"

list.delete("B");
console.log(list.toString()); // "A, C"

list.reverse();
console.log(list.toString()); // "C, A"

Как работают основные операции

Что важно понимать по поведению:

  • prepend работает быстро, потому что меняет только ссылку на голову списка;
  • append тоже быстрый, если ты поддерживаешь tail;
  • find и delete требуют прохода по списку слева направо;
  • deleteTail в односвязном списке дороже, потому что до предпоследнего узла нужно дойти вручную;
  • reverse просто разворачивает ссылки между узлами, не создавая новый список.

Именно поэтому связный список хорошо показывает компромиссы структуры данных: одни операции дешевые, другие дорогие.

Итог

В JavaScript массив почти всегда практичнее:

  • у массива удобный доступ по индексу;
  • у него богатый стандартный API;
  • движки JavaScript отлично оптимизируют обычные массивы.

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

Если ты пишешь прикладной фронтенд-код, связный список обычно нужен скорее для понимания алгоритмов, чем для интерфейсов или бизнес-логики.