数据结构 — 链表

2022-05-28 本文已影响0人 lio_zero

链表（Linked list）是一种表示元素集合的线性数据结构，其中每个元素指向下一个元素。链表中的第一个元素是 head，最后一个元素是 tail。

JavaScript 链表可视化

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

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

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

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

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

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

JavsScript 实现

class LinkedList {
  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 }

    if (previousNode) previousNode.next = 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]
    const nextNode = this.nodes[index + 1] || null

    if (previousNode) previousNode.next = nextNode

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

  clear() {
    this.nodes = []
  }

  reverse() {
    this.nodes = this.nodes.reduce(
      (acc, { value }) => [{ value, next: acc[0] || null }, ...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 键。
定义两个便捷的方法 insertFirst() 和 insertLast()，它们分别使用 insertAt() 方法在 nodes 数组的开头或结尾插入新元素。
定义一个 getAt() 方法，用于检索给定 index 的元素。
定义一个 removeAt() 方法，使用 Array.prototype.splice() 删除 nodes 数组中的一个对象，更新上一个元素的 next 键。
定义一个 clear() 方法，清空 nodes 数组。
定义一个 reverse() 方法，使用 Array.prototype.reduce() 和扩展运算符（...）来反转 nodes 数组的顺序，适当地更新每个元素的 next 键。
为 Symbol.iterator 定义一个生成器方法，使用 yield* 语法委托给 nodes 数组的迭代器。

const list = new LinkedList()

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.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 - Linked List。

数据结构 — 链表

JavsScript 实现

Leetcode 相关的链表题目

更多资料

猜你喜欢

热点阅读