数据结构 — 双向链表

双向链表，又称为双链表，是一种表示元素集合的线性数据结构，其中每个元素都指向下一个和上一个元素。双向链表中的第一个元素是 head，最后一个元素是 tail。

JavaScript 双向链表可视化

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

value：元素的值
next：指向双向链表中下一个元素的指针(如果没有，则为 null)
previous：指向双向链表中上一个元素的指针(如果没有，则为 null)

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

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

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

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

JavaScript 实现


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]
  }
 
  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
  }
}

创建一个具有 constructor 的类(class)，为每个实例初始化一个空数组 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() 方法，用于检索给定 index 的元素。
定义一个 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

以上内容译自 30 seconds of code 的 JavaScript Data Structures - Doubly Linked List。

数据结构 — 双向链表

JavaScript 实现

Leetcode 相关的双向链表题目

更多资料