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

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

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

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

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

  • value - значение;
  • next - ссылка на следующий узел;
  • previous - ссылка на предыдущий узел.

Сам список, как и раньше, хранит head и tail.

Реализация DoublyLinkedListNode и DoublyLinkedList

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

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

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

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

    if (this.head) {
      this.head.previous = newNode;
    }

    this.head = newNode;

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

    return this;
  }

  append(value) {
    const newNode = new DoublyLinkedListNode(value, null, this.tail);

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

    this.tail = newNode;

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

    return this;
  }

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

    let deletedNode = null;
    let currentNode = this.head;

    while (currentNode) {
      if (currentNode.value === value) {
        deletedNode = currentNode;

        if (deletedNode === this.head) {
          this.head = deletedNode.next;

          if (this.head) {
            this.head.previous = null;
          }
        }

        if (deletedNode === this.tail) {
          this.tail = deletedNode.previous;

          if (this.tail) {
            this.tail.next = null;
          }
        }

        if (deletedNode.previous) {
          deletedNode.previous.next = deletedNode.next;
        }

        if (deletedNode.next) {
          deletedNode.next.previous = deletedNode.previous;
        }
      }

      currentNode = currentNode.next;
    }

    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.head.previous = null;
    } else {
      this.tail = null;
    }

    return deletedHead;
  }

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

    const deletedTail = this.tail;

    this.tail = this.tail.previous;

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

    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;

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

      currentNode.next = currentNode.previous;
      currentNode.previous = nextNode;

      currentNode = nextNode;
    }

    const oldHead = this.head;
    this.head = this.tail;
    this.tail = oldHead;

    return this;
  }
}

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

const list = new DoublyLinkedList();

list.fromArray(["A", "B", "C"]);

console.log(list.toString()); // "A, B, C"
console.log(list.tail.previous.value); // "B"

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

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

Что становится проще по сравнению с singly linked list

Главное преимущество двусвязного списка - симметрия.

В односвязном списке удаление хвоста требует прохода от головы до предпоследнего узла. Здесь достаточно посмотреть на tail.previous.

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

Именно поэтому двусвязные списки часто лежат в основе:

  • LRU-кэшей;
  • двусторонних очередей;
  • структур, где узлы постоянно удаляются и вставляются между соседями.

Итог

Как и с односвязным списком, в обычном JavaScript-коде массив обычно удобнее. Он проще, лучше читается и лучше поддерживается экосистемой.

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

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