JavaScript数据结构 - 双向链表

定义

双向链表是一种线性数据结构，表示一组元素，每个元素都指向前一个和后一个元素。双向链表的第一个元素是头部，最后一个元素是尾部。

JavaScript双向链表可视化

双向链表数据结构的每个元素必须具有以下属性：

value：元素的值
next：指向链表中下一个元素的指针（如果没有则为null）
previous：指向链表中前一个元素的指针（如果没有则为null）

双向链表数据结构的主要属性包括：

size：双向链表中的元素数量
head：双向链表中的第一个元素
tail：双向链表中的最后一个元素

双向链表数据结构的主要操作包括：

insertAt：在特定索引处插入一个元素
removeAt：删除特定索引处的元素
getAt：检索特定索引处的元素
clear：清空双向链表
reverse：反转双向链表中的元素的顺序

实现

class DoublyLinkedList {
  constructor() {
    this.nodes = [];
  }

  get size() {
    return this.nodes.length;
  }

  get head() {
    return this.size ? this.nodes[0] : null;
  }

  get tail() {
    return this.size ? this.nodes[this.size - 1] : null;
  }

  insertAt(index, value) {
    const previousNode = this.nodes[index - 1] || null;
    const nextNode = this.nodes[index] || null;
    const node = { value, next: nextNode, previous: previousNode };

    if (previousNode) previousNode.next = node;
    if (nextNode) nextNode.previous = node;
    this.nodes.splice(index, 0, node);
  }

  insertFirst(value) {
    this.insertAt(0, value);
  }

  insertLast(value) {
    this.insertAt(this.size, value);
  }

  getAt(index) {
    return this.nodes[index];
  }

```js
removeAt(index) {
  const previousNode = this.nodes[index - 1] || null;
  const nextNode = this.nodes[index + 1] || null;

  if (previousNode) previousNode.next = nextNode;
  if (nextNode) nextNode.previous = previousNode;

  return this.nodes.splice(index, 1);
}

clear() {
  this.nodes = [];
}

reverse() {
  this.nodes = this.nodes.reduce((acc, { value }) => {
    const nextNode = acc[0] || null;
    const node = { value, next: nextNode, previous: null };
    if (nextNode) nextNode.previous = node;
    return [node, ...acc];
  }, []);
}

*[Symbol.iterator]() {
  yield* this.nodes;
}
}

创建一个class，其中的constructor初始化一个空数组nodes。
定义一个size getter，使用Array.prototype.length返回nodes数组中的元素数量。
定义一个head getter，返回nodes数组的第一个元素，如果为空则返回null。
定义一个tail getter，返回nodes数组的最后一个元素，如果为空则返回null。
定义一个insertAt()方法，使用Array.prototype.splice()在nodes数组中添加一个新对象，并更新前一个和后一个元素的next和previous键。
定义两个方便的方法，insertFirst()和insertLast()，它们使用insertAt()方法在nodes数组的开头或结尾插入一个新元素。
定义一个getAt()方法，检索给定索引处的元素。
定义一个removeAt()方法，使用Array.prototype.splice()从nodes数组中删除一个对象，并更新前一个和后一个元素的next和previous键。
定义一个clear()方法，清空nodes数组。
定义一个reverse()方法，使用Array.prototype.reduce()和展开运算符(...)来反转nodes数组的顺序，并适当更新每个元素的next和previous键。
为Symbol.iterator定义一个生成器方法，使用yield*语法委托给nodes数组的迭代器。

const list = new DoublyLinkedList();

list.insertFirst(1);
list.insertFirst(2);
list.insertFirst(3);
list.insertLast(4);
list.insertAt(3, 5);

list.size;                      // 5
list.head.value;                // 3
list.head.next.value;           // 2
list.tail.value;                // 4
list.tail.previous.value;       // 5
[...list.map(e => e.value)];    // [3, 2, 1, 5, 4]

list.removeAt(1); // 2 list.getAt(1).value; // 1 list.head.next.value; // 1 [...list.map(e => e.value)]; // [3, 1, 5, 4]

list.reverse(); [...list.map(e => e.value)]; // [4, 5, 1, 3]

list.clear(); list.size; // 0 ```