数据结构 — 双向链表

双向链表，又称为双链表，是一种表示元素集合的线性数据结构，其中每个元素都指向下一个和上一个元素。双向链表中的第一个元素是 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。

Leetcode 相关的双向链表题目

• 剑指 Offer 36. 二叉搜索树与双向链表
• 扁平化多级双向链表

更多资料

Doubly Linked List