鏈表（Linked list）是一種表示元素集合的線性數(shù)據(jù)結(jié)構(gòu)，其中每個元素指向下一個元素。鏈表中的第一個元素是 head，最后一個元素是 tail离福。

JavaScript 鏈表可視化

鏈表數(shù)據(jù)結(jié)構(gòu)的每個元素必須具有以下屬性：

• value：元素的值
• next：指向鏈表中下一個元素的指針（如果沒有，則為 null）

鏈表數(shù)據(jù)結(jié)構(gòu)的主要屬性有：

• size：鏈表中的元素個數(shù)
• head：鏈表中的第一個元素
• tail：鏈表中的最后一個元素

鏈表數(shù)據(jù)結(jié)構(gòu)的主要操作有：

• insertAt：在特定索引處插入元素
• removeAt：刪除特定索引處的元素
• getAt：檢索特定索引處的元素
• clear：清空鏈表
• reverse：反轉(zhuǎn)鏈表中元素的順序

JavsScript 實現(xiàn)

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

• 創(chuàng)建一個具有 constructor 的類（class），為每個實例初始化一個空數(shù)組 nodes幢竹。
• 定義一個 size getter，它使用 Array.prototype.length 返回 nodes 數(shù)組中元素的數(shù)量恩静。
• 定義一個 head getter焕毫，它返回 nodes 數(shù)組的第一個元素，如果為空驶乾，則返回 null邑飒。
• 定義一個 tail getter，它返回 nodes 數(shù)組的最后一個元素级乐，如果為空疙咸，則返回 null。
• 定義一個 insertAt() 方法风科，使用 Array.prototype.splice() 在 nodes 數(shù)組中添加一個新對象撒轮，更新上一個元素的 next 鍵。
• 定義兩個便捷的方法 insertFirst() 和 insertLast()贼穆，它們分別使用 insertAt() 方法在 nodes 數(shù)組的開頭或結(jié)尾插入新元素题山。
• 定義一個 getAt() 方法，用于檢索給定 index 的元素扮惦。
• 定義一個 removeAt() 方法臀蛛，使用 Array.prototype.splice() 刪除 nodes 數(shù)組中的一個對象，更新上一個元素的 next 鍵崖蜜。
• 定義一個 clear() 方法浊仆，清空 nodes 數(shù)組。
• 定義一個 reverse() 方法豫领，使用 Array.prototype.reduce() 和擴展運算符（...）來反轉(zhuǎn) nodes 數(shù)組的順序抡柿，適當?shù)馗旅總€元素的 next 鍵。
• 為 Symbol.iterator 定義一個生成器方法等恐，使用 yield* 語法委托給 nodes 數(shù)組的迭代器洲劣。

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

以上內(nèi)容譯自 30 seconds of code 的 JavaScript Data Structures - Linked List备蚓。

Leetcode 相關(guān)的鏈表題目

• 刪除鏈表的倒數(shù)第 N 個結(jié)點
• 合并兩個有序鏈表
• 合并K個升序鏈表
• 環(huán)形鏈表
• 環(huán)形鏈表 II
• 排序鏈表
• 相交鏈表
• 反轉(zhuǎn)鏈表
• 回文鏈表
• 重排鏈表
• 二叉樹展開為鏈表
• 更多

更多資料

Linked List