「算法與數據結構」JavaScript中的鏈表

語言: CN / TW / HK

寫在前面

此文會先探討下什麼是鏈表以及在 JavaScript 中的鏈表,接着我們會使用 JavaScript 這門語言動手實現下各類鏈表的設計,最後我們會拋出一些常規疑問,並從各個方面一一解答,總之,目的就是完全搞定鏈表

搞定概念之後我們可以去力扣上選擇鏈表分類,按照難易程度把它們刷完,其實力扣上鏈表的題目相對簡單,只要你完整的看完了此文的鏈表設計,最起碼可以輕鬆淦掉20題,同時鏈表題目數量也比較少,一共也就有50題左右,還有十來題需要會員,也就是説刷個40題,鏈表這種數據結構就可以初步掌握了,如果你不想找題排序,可以按照我的 GitHub 算法倉庫庫中的順序刷題,有不太懂的題目或者概念可以看我寫的題解,同時我也錄製了視頻,文末有鏈接,那麼我們來開始學習鏈表,GO!

什麼是鏈表

通常我們在程序中想要存儲多個元素,數組可能是最常用的數據結構,數組這種數據結構非常方便,它甚至可以通過非常簡單的方式即 [] 這種語法來訪問其元素

而鏈表存儲的也是有序的元素集合,但不同於數組的是,鏈表中的元素在內存中並不是連續的,每個元素由一個存儲元素本身的節點和一個指向下一個元素的引用(也可以稱為指針)組成

我們接着再來看數組這種數據結構,它有一個缺點,在大多數語言中數組的大小是固定的,從數組的起點或中間插入或移除項的成本很高,因為需要移動元素,如下圖

上圖數組刪除索引為 2 值為 3 的元素,那麼我們首先要刪掉 3 這個元素,因為索引為 2 值為 3 的元素刪除了,索引 2 就空了,所以接着,我們要把索引 3 也就是元素 4 向前移動一位,與此同時後面的元素 5 也需要向前移動一位,向數組中插入一個元素也是這個道理,只要數組中少了一位或者多了一位,那麼後面的元素都要依次向前或向後移動一位,那麼可想而之,當數組長度很大的時候,插入及刪除的效率就會逐漸降低

我們再來看看鏈表

同樣是刪除元素 3,鏈表這裏只需要迭代到值為 3 的節點,將節點 2 指向節點 4 就行了,節點 3 沒有了引用關係,就會被垃圾回收機制當作垃圾回收了,即使當節點非常多的情況下,依然只用改變一下引用關係即可刪除元素,而插入元素則是反過來,即先斷開插入位置兩邊的元素,然後讓前一個元素指向插入元素,插入元素指向後一個元素即可,元素越多對比數組的效率就會越高

相對於傳統的數組,鏈表的一個好處就在於,添加或移除元素的時候不需要移動其他元素,但是在數組中,我們可以直接訪問任何位置的任何元素,鏈表中是不行的,因為鏈表中每個節點只有對下一個節點的引用,所以想訪問鏈表中間的一個元素,必須要從起點(鏈表頭部節點)開始迭代鏈表直到找到所需的元素,這點需要注意

JavaScript中的鏈表

上面我們簡單介紹了常規鏈表的概念,但是在 JavaScript 這門語言中,我們怎麼表示鏈表呢?

由於 JS 中沒有內置鏈表這種數據結構,所以我們需要使用對象來模擬實現鏈表,就如同我們上面介紹鏈表,它其實是一個單向鏈表,除此之外還有雙向鏈表、環形鏈表等等,我們接下來會一一介紹並使用 JavaScript 來實現下

單向鏈表

我們先來看基礎的單項鍊表,單向鏈表每個元素由一個存儲元素本身的節點和一個指向下一個元素的指針構成,如下圖

要實現鏈表這種數據結構,關鍵在於保存 head 元素(即鏈表的頭元素)以及每一個元素的 next 指針,有這兩部分我們就可以很方便地遍歷鏈表從而操作所有的元素,你可以把鏈表想象成一條鐵鏈,鐵鏈中的每一個節點都是相互連接的,我們只要找到鐵鏈的頭,整條鐵鏈就都可以找到了,那麼單向鏈表在 JS 中究竟要如何來模擬呢,我們一步一步來

首先,我們要創建一個類,這個類的作用就是描述鏈表的節點,它很簡單,只需要有兩個屬性就可以了,一個用來保存此節點的值,一個用來保存指向下一個節點的指針,如下

/**
 * @description: 創建鏈表單節點類
 * @param {*} val 節點值
 * @return {*}
 */
function ListNode(val) {
  this.val = val
  this.next = null
}
複製代碼

接着,我們需要先寫一個鏈表類,其中 length屬性 代表鏈表長度,head屬性 代表鏈表頭部節點

/**
 * @description: 創建鏈表類
 * @param {*}
 * @return {*}
 */
function LinkedList() {
  this.length = 0
  this.head = null
}
複製代碼

我們思考下,既然是來模擬一個鏈表類,那麼就應該把它所有可能會用到的特性都塞進這個類裏,就比如數組有 push/splice/indexOf/... 等等這些好用的方法我們鏈表必須也得有啊,我們先仔細構思下要給鏈表添加哪些實用的特性或者説方法,先搭一個基礎骨架,這裏我列出了很多,我們來一一實現下,也歡迎補充

// 向鏈表中追加節點
LinkedList.prototype.append = function (val) { }

// 在鏈表的指定位置插入節點
LinkedList.prototype.insert = function (index, val) { }

// 刪除鏈表中指定位置的元素,並返回這個元素的值
LinkedList.prototype.removeAt = function (index) { }

// 刪除鏈表中對應的元素
LinkedList.prototype.remove = function (val) { }

// 獲取鏈表中給定元素的索引
LinkedList.prototype.indexOf = function (val) { }

// 獲取鏈表中某個節點
LinkedList.prototype.find = function (val) { }

// 獲取鏈表中索引所對應的元素
LinkedList.prototype.getElementAt = function (index) { }

// 判斷鏈表是否為空
LinkedList.prototype.isEmpty = function () { }

// 獲取鏈表的長度
LinkedList.prototype.size = function () { }

// 獲取鏈表的頭元素
LinkedList.prototype.getHead = function () { }

// 清空鏈表
LinkedList.prototype.clear = function () { }

// 序列化鏈表
LinkedList.prototype.jion = function (string) { }
複製代碼

getElementAt(index)

我們先來實現獲取鏈表中索引所對應的元素即 getElementAt 方法以及通過節點值獲取鏈表元素即 find 方法,因為後面要多次用到它們,我們先説 getElementAt 方法,上面我們説想要找一個元素,我們必須從頭迭代,所以我們直接根據傳入的索引進行迭代即可

首先判斷參數 index 的邊界值,如果值超出了索引的範圍(小於 0 或者大於 length - 1),則返回null,我們從鏈表的 head 節點開始,遍歷整個鏈表直到找到對應索引位置的節點,然後返回這個節點,是不是很簡單?和所有有序數據集合一樣,鏈表的索引也是從 0 開始,只要有鏈表的頭節點,就可以遍歷找到索引所在位置的元素,所以我們在構造函數即 LinkedList 類中保存了 head

// 獲取鏈表中索引所對應的元素
LinkedList.prototype.getElementAt = function (index) {
  if (index < 0 || index >= this.length) return null

  let cur = this.head
  while (index--) {
    cur = cur.next
  }
  return cur
}
複製代碼

find(val)

find 方法和 getElementAt 方法類似,一個通過索引找元素,一個通過節點值找元素,所以我們直接迭代查找對比即可

// 獲取鏈表中某個節點
LinkedList.prototype.find = function (val) {
  let cur = this.head
  while (cur) {
    if (cur.val == val) return cur
    cur = cur.next
  }
  return null
}
複製代碼

append(val)

有了 getElementAt 方法後,接下來我們就可以很方便地實現 append 方法,此方法的作用是在鏈表末尾追加元素

此方法傳入的是一個值,我們可以通過上面的構造函數 ListNode 來創建一個新節點

而後,我們需要考慮,如果鏈表的 headnull 時,這種情況表示鏈表為空,所以需要將 head 節點指向新添加的元素,以此來確保存儲頭節點,如果不為空,我們通過 getElementAt 方法找到鏈表的最後一個節點,最後一個節點的索引就是構造函數中的我們存的鏈表長度 length 屬性減去 1,再將最後一個節點的 next 指針指向新添加的元素即可

新添加的元素 next 指針默認為 null,鏈表最後一個元素的 next 值也就為 null,另外,將節點掛到鏈表上之後,還需將鏈表的長度加 1,保證 length 屬性等於鏈表長度,如下

// 向鏈表中追加節點
LinkedList.prototype.append = function (val) {
  let node = new ListNode(val)

  if (!this.head) {
    this.head = node
  } else {
    let cur = this.getElementAt(this.length - 1)
    cur.next = node
  }
  this.length++
}
複製代碼

insert(index, val)

接下來我們要實現 insert 方法,即在鏈表的任意位置添加節點

在指定位置插入元素,首先我們還是需要先判斷下傳入 index 索引是否超出邊界

接着我們分兩種情況考慮

index 的值為 0 時,表示要在鏈表的頭部插入新節點,將新插入節點的 next 指針指向現在的 head,然後更新 head 的值為新插入的節點即可,如下圖

index 的值不為 0 時,即插入的節點在鏈表的中間或者尾部,我們首先找到待插入位置的前一個節點 prevNode,然後將新節點 newNodenext 指針指向 prevNodenext 所對應的節點,再將 prevNodenext 指針指向 newNode,這樣就把新節點插入鏈表中了,當插入的節點在鏈表的尾部,這種方法也同樣適用,如下圖

最後,我們插入了節點,還需要將鏈表的長度即 length 長度加 1,代碼如下

// 在鏈表的指定位置插入節點
LinkedList.prototype.insert = function (index, val) {
  if (index < 0 || index > this.length) return false

  let node = new ListNode(val)

  if (index === 0) {
    node.next = this.head
    this.head = node
  } else {
    let prev = this.getElementAt(index - 1)
    node.next = prev.next
    prev.next = node
  }

  this.length++
  return true
}
複製代碼

removeAt(index)

相同的方式,我們可以很容易地寫出 removeAt 方法,用來刪除鏈表中指定位置的節點

依然還是先判斷下傳入 index 索引是否超出邊界

還是分兩種情況

如果要刪除的節點是鏈表的頭部,將 head 移到下一個節點即可,如果當前鏈表只有一個節點,那麼下一個節點為 null,此時將 head 指向下一個節點等同於將 head 設置成 null,刪除之後鏈表為空

如果要刪除的節點在鏈表的中間部分,我們需要找出 index 所在位置的前一個節點,將它的 next 指針指向 index 所在位置的下一個節點,總之,刪除節點只需要修改相應節點的指針,斷開刪除位置左右相鄰的節點再重新連接上即可

image-20201227180444604

被刪除的節點沒有了引用關係,JavaScript 垃圾回收機制會處理它,關於垃圾回收機制,同樣不在此文討論範圍內,知道即可,刪除節點元素,我們還需將鏈表的長度減 1,最終代碼如下

// 刪除鏈表中指定位置的元素,並返回這個元素的值
LinkedList.prototype.removeAt = function (index) {
  if (index < 0 || index >= this.length) return null

  let cur = this.head

  if (index === 0) {
    this.head = cur.next
  } else {
    let prev = this.getElementAt(index - 1)
    cur = prev.next
    prev.next = cur.next
  }

  this.length--
  return cur.val
}
複製代碼

indexOf(val)

獲取鏈表中給定元素的索引,這個比較簡單,直接迭代即可,匹配到了返回對應索引,匹配不到返回 -1

// 獲取鏈表中給定元素的索引
LinkedList.prototype.indexOf = function (val) {
  let cur = this.head

  for (let i = 0; i < this.length; i++) {
    if (cur.val === val) return i
    cur = cur.next
  }

  return -1
}
複製代碼

remove(val)

刪除鏈表中對應的元素,有了之前的鋪墊,這裏就比較簡單了,我們可以直接用 indexOf 方法拿到對應索引,再使用 removeAt 方法刪除節點即可

// 刪除鏈表中對應的元素
LinkedList.prototype.remove = function (val) {
  let index = this.indexOf(val)
  return this.removeAt(index)
}
複製代碼

isEmpty()

判斷鏈表是否為空,只需要我們判斷一下鏈表長度 length 等不等於 0 即可

// 判斷鏈表是否為空
LinkedList.prototype.isEmpty = function () {
  return !this.length
}
複製代碼

size()

獲取鏈表長度就是取其 length

// 獲取鏈表的長度
LinkedList.prototype.size = function () {
  return this.length
}
複製代碼

getHead()

獲取鏈表的頭元素即返回 head 屬性即可

// 獲取鏈表的頭元素
LinkedList.prototype.getHead = function () {
  return this.head
}
複製代碼

clear()

清空鏈表,我們只需要將 head 置空,然後讓 length 等於 0,等待垃圾回收機制回收無引用的廢棄鏈表即可

// 清空鏈表
LinkedList.prototype.clear = function () {
  this.head = null
  this.length = 0
}
複製代碼

jion(string)

序列化鏈表即使用指定格式輸出鏈表,類似於數組中 jion 方法,此舉旨在便於我們測試

// 序列化鏈表
LinkedList.prototype.jion = function (string) {
  let cur = this.head
  let str = ''
  while (cur) {
    str += cur.val

    if (cur.next) str += string

    cur = cur.next
  }
  return str
}
複製代碼

那麼到此,我們的單向鏈表類就設計完成了,快來測試一下吧,我們輸入下面代碼進行測試

let linkedList = new LinkedList()
linkedList.append(10)
linkedList.append(20)
linkedList.append(30)

console.log(linkedList.jion("--"))

linkedList.insert(0, 5)
linkedList.insert(2, 15)
linkedList.insert(4, 25)
console.log(linkedList.jion("--"))

console.log(linkedList.removeAt(0))
console.log(linkedList.removeAt(1))
console.log(linkedList.removeAt(2))
console.log(linkedList.jion("--"))

console.log(linkedList.indexOf(20))

linkedList.remove(20)

console.log(linkedList.jion("--"))

console.log(linkedList.find(10))

linkedList.clear()
console.log(linkedList.size())
複製代碼

最終輸出如下

// 10--20--30
// 5--10--15--20--25--30
// 5
// 15
// 25
// 10--20--30
// 1
// 10--30
// ListNode { val: 10, next: ListNode { val: 30, next: null } }
// 0
複製代碼

上面代碼中少了一些參數校驗,不過夠我們學習用了,完成代碼文末附鏈接

雙向鏈表

上面我們説了單向鏈表,接下來我們來説雙向鏈表,那麼什麼是雙向鏈表呢?其實聽名字就可以聽出來,單向鏈表中每一個元素只有一個 next 指針,用來指向下一個節點,我們只能從鏈表的頭部開始遍歷整個鏈表,任何一個節點只能找到它的下一個節點,而不能找到它的上一個節點,雙向鏈表中的每一個元素擁有兩個指針,一個用來指向下一個節點,一個用來指向上一個節點,雙向鏈表中,除了可以像單向鏈表一樣從頭部開始遍歷之外,還可以從尾部進行遍歷,如下圖

同單向鏈表,我們首先創建鏈表節點類,不同的是,它需要多一個 prev 屬性用來指向前一個節點

/**
 * @description: 創建雙向鏈表單節點類
 * @param {*} val 節點值
 * @return {*}
 */
function ListNode(val) {
  this.val = val
  this.next = null
  this.prev = null
}
複製代碼

雙向鏈表類同單向鏈表多增加了一個尾部節點 tail

/**
 * @description: 創建雙向鏈表類
 * @param {*}
 * @return {*}
 */
function DoubleLinkedList() {
  this.length = 0
  this.head = null
  this.tail = null
}
複製代碼

接下來我們來實現雙向鏈表的原型方法

getElementAt(index)

首先就是,獲取雙向鏈表中索引所對應的元素,雙向鏈表由於可以雙向進行迭代查找,所以這裏 getElementAt 方法我們可以進行優化,當索引大於鏈表長度 length/2 時,我們可以從後往前找,反之則從前向後找,這樣可以更快找到該節點元素

// 獲取雙向鏈表中索引所對應的元素
DoubleLinkedList.prototype.getElementAt = function (index) {
  if (index < 0 || index >= this.length) return null
	
  let cur = null
  if(index > Math.floor(this.length / 2)){
    // 從後往前
    cur = this.tail
    let i = this.length - 1
    while (i > index) {
      cur = cur.prev
      i--
    }
  }else{
    // 從前往後
    cur = this.head
    while (index--) {
      cur = cur.next
    }
  }
  return cur
}
複製代碼

find(val)

find 方法和 getElementAt 方法是類似的,getElementAt 方法可以優化,那麼 find 再變成雙向鏈表後也可優化,我們想,既然雙向都可以進行迭代,那麼我們兩遍同時迭代豈不是更快,同時迭代的情況下,當前後相等時,代表遍歷到了中間,即全鏈表都已經迭代過,結束迭代返回 null

// 獲取雙向鏈表中某個節點
DoubleLinkedList.prototype.find = function (val) {
	let curHead = this.head
  let curTail = this.tail
  while (curHead !== curTail) {
    if (curHead.val == val) return curHead
    curHead = curHead.next

    if (curTail.val == val) return curTail
    curTail = curTail.prev
  }
  return null
}
複製代碼

append(val)

又來到了我們的追加節點元素,雙向鏈表追加與單向鏈表還是有些區別的

當鏈表為空時,除了要將 head 指向當前添加的節點外,還要將 tail 也指向當前要添加的節點

當鏈表不為空時,直接將 tailnext 指向當前要添加的節點 node,然後修改 nodeprev 指向舊的 tail,最後修改 tail 為新添加的節點

雙向鏈表的追加操作我們不需要從頭開始遍歷整個鏈表,通過 tail 可以直接找到鏈表的尾部,這一點比單向鏈表的操作更方便,最後將 length 值加 1,修改鏈表的長度即可

// 向雙向鏈表中追加節點
DoubleLinkedList.prototype.append = function (val) {
  let node = new ListNode(val)

  if (this.head === null) {
    // 鏈表為空,head 和 tail 都指向當前添加的節點
    this.head = node
    this.tail = node
  }
  else {
    // 鏈表不為空,將當前節點添加到鏈表的尾部
    this.tail.next = node
    node.prev = this.tail
    this.tail = node
  }

  this.length++
}
複製代碼

insert(index, val)

接着是插入節點元素方法,同樣思路一致,並不困難,我們注意 tailprev 指針分情況討論,插入後長度加 1 即可

// 在雙向鏈表的指定位置插入節點
DoubleLinkedList.prototype.insert = function (index, val) {
  if (index < 0 || index > this.length) return false

  // 插入到尾部
  if (index === this.length) {
    this.append(val)
  } else {
    let node = new ListNode(val)

    if (index === 0) { // 插入到頭部
      if (this.head === null) {
        this.head = node
        this.tail = node
      } else {
        node.next = this.head
        this.head.prev = node
        this.head = node
      }
    } else { // 插入到中間位置
      let curNode = this.getElementAt(index)
      let prevNode = curNode.prev
      node.next = curNode
      node.prev = prevNode
      prevNode.next = node
      curNode.prev = node
    }
    this.length++
  }
  return true
}
複製代碼

removeAt(index)

刪除雙向鏈表中指定位置的元素,同樣是注意 tailprev 指針分情況討論,最後刪除後長度減 1 即可

// 刪除雙向鏈表中指定位置的元素,並返回這個元素的值
DoubleLinkedList.prototype.removeAt = function (index) {
  if (index < 0 || index >= this.length) return null

  let current = this.head
  let prevNode

  if (index === 0) { // 移除頭部元素
    this.head = current.next
    this.head.prev = null
    if (this.length === 1) this.tail = null
  } else if (index === this.length - 1) { // 移除尾部元素
    current = this.tail
    this.tail = current.prev
    this.tail.next = null
  } else { // 移除中間元素
    current = this.getElementAt(index)
    prevNode = current.prev
    prevNode.next = current.next
    current.next.prev = prevNode
  }

  this.length--
  return current.val
}
複製代碼

indexOf(val)

在雙向鏈表中查找元素索引,有了上面的 find 方法做鋪墊,這裏就簡單了,思路一致,

// 獲取雙向鏈表中給定元素的索引
DoubleLinkedList.prototype.indexOf = function (val) {
  let curHead = this.head
  let curTail = this.tail
  let idx = 0
  while (curHead !== curTail) {
    if (curHead.val == val) return idx
    curHead = curHead.next

    if (curTail.val == val) return this.length - 1 - idx
    curTail = curTail.prev

    idx++
  }
  return -1
}
複製代碼

jion(string)

序列化鏈表我們還是和上面單向鏈表一致即可

// 序列化雙向鏈表
DoubleLinkedList.prototype.jion = function (string) {
  let cur = this.head
  let str = ''
  while (cur) {
    str += cur.val

    if (cur.next) str += string

    cur = cur.next
  }
  return str
}
複製代碼

雙向鏈表我們就介紹這麼多,剩下的方法比較簡單,就不贅述了,文末雙向鏈表案例中有完整代碼

同樣,我們來簡單測試一下對與否

let doubleLinkedList = new DoubleLinkedList()
doubleLinkedList.append(10)
doubleLinkedList.append(15)
doubleLinkedList.append(20)
doubleLinkedList.append(25)
console.log(doubleLinkedList.jion("<->"))

console.log(doubleLinkedList.getElementAt(0).val)
console.log(doubleLinkedList.getElementAt(1).val)
console.log(doubleLinkedList.getElementAt(5))

console.log(doubleLinkedList.jion("<->"))
console.log(doubleLinkedList.indexOf(10))
console.log(doubleLinkedList.indexOf(25))
console.log(doubleLinkedList.indexOf(50))

doubleLinkedList.insert(0, 5)
doubleLinkedList.insert(3, 18)
doubleLinkedList.insert(6, 30)
console.log(doubleLinkedList.jion("<->"))

console.log(doubleLinkedList.find(10).val)
console.log(doubleLinkedList.removeAt(0))
console.log(doubleLinkedList.removeAt(1))
console.log(doubleLinkedList.removeAt(5))
console.log(doubleLinkedList.remove(10))
console.log(doubleLinkedList.remove(100))

console.log(doubleLinkedList.jion("<->"))
複製代碼

上面代碼輸出如下

// 10<->15<->20<->25
// 10
// 15
// null
// 10<->15<->20<->25
// 0
// 3
// -1
// 5<->10<->15<->18<->20<->25<->30
// 10
// 5
// 15
// null
// 10
// null
// 18<->20<->25<->30
複製代碼

嗯,沒有報錯,簡單對比一下,是正確的,No Problem

環形鏈表

我們再來看另一種鏈表,環形鏈表,顧名思義,環形鏈表的尾部節點指向它自己的頭節點

環形鏈表有單向環形鏈表,也可以有雙向環形鏈表,如下圖

單雙環形鏈表這裏我們就不再一一的寫了,你可以嘗試自己寫一下,對比上面我們環形鏈表只需要注意下尾部節點要指向頭節點即可

為什麼JavaScript中不內置鏈表?

根據我們上面所説,鏈表有這麼多優點,那麼為什麼 JavaScript 這門語言不內置鏈表這種數據結構呢?

其實 JS 中,數組幾乎實現了鏈表的所有功能,所以沒那個必要去再麻煩一次了,聽到這裏你可能會疑惑,上面不是説,數組在某些情況(例如頭部插入等等)下性能不如鏈表嗎?

我們來用事實説話,現在我們用上面完成的單向鏈表類 LinkedList,同原生數組做一個簡單的的時間測試

let linkedList = new LinkedList()
let arr = []

// 測試 分別嘗試 「總數100 插入節點50」/「總數100000 插入節點50000」
let count = 100
let insertIndex = 50
// let count = 100000
// let insertIndex = 50000

console.time('鏈表push操作')
for (let i = 0; i < count; i++) {
  linkedList.append(i)
}
console.timeEnd('鏈表push操作')

console.time('數組push操作')
for (let i = 0; i < count; i++) {
  arr.push(i)
}
console.timeEnd('數組push操作')


console.time('鏈表insert操作')
linkedList.insert('test節點', insertIndex)
console.timeEnd('鏈表insert操作')

console.time('數組insert操作')
arr.splice(insertIndex, 0, 'test節點')
console.timeEnd('數組insert操作')


console.time('鏈表remove操作')
linkedList.removeAt(insertIndex)
console.timeEnd('鏈表remove操作')

console.time('數組remove操作')
arr.splice(insertIndex, 1)
console.timeEnd('數組remove操作')
複製代碼

我們來看下結果

追加 100 個數據,在索引 50 插入元素,再刪除插入的元素

追加 100000 個數據,在索引 50000 插入元素,再刪除插入的元素

What??????

我們從測試結果可以看到不論基數為 100 這樣的小量級或者基數為 100000 這樣一個很大的量級時,原生 Array 的性能都依然碾壓鏈表

也就是説鏈表效率高於數組效率這種話,事實上在 JS 中是不存在的,即使你創建一個長度為 1 億的數組,再創建一個長度為 10 的數組,並且向這兩個數組的中間添加元素,console.time 時間出來看看,你會發現所用時間與數組長度長度無關,這説明 JS 數組達到了鏈表的效率要求

而且數組中我們也可以用 splice() 方法向數組的指定位置去添加和刪除元素,經測試,所需時間同樣與數組長度無關,也能達到鏈表的要求,而數組的下標完全可以取代鏈表的 head,tail,next,prev 等方法,並且大多數情況下會更方便些,再加上工作中鏈表這種數據結構的使用場景不是太多,所以可以説 JS 中的數組是完爆鏈表的

當然,這隻侷限於 JavaScript 這門語言中,這和 JS 內部的數組實現機制有關,其實 JS 中的數組只是叫數組而已,它和常規語言中的數組概念就不同,那麼關於數組概念以及內部實現,不在我們此章節討論範圍之內,先留一個疑問,過幾天有空了再另起一篇 JS 數組相關的文章吧,其實自己找去答案最好了,我們説 JS 是一門解釋型高級語言,它的底層實現並不像我們看起來那麼簡單循規,有點打破常規的意思

講的這裏,你可能會吐槽這一篇文章好不容易看完了,現在你給我説沒用。。。不要着急,收好臭雞蛋

JavaScript中鏈表無用?

如我們上面所説,難道 JavaScript 中的鏈表當真就毫無作用了嗎?

其實也不是,就比如三大法寶之一 React 中的 Fiber 架構,就用到了鏈表這種數據結構

Fiber 在英文中的意思為 纖維化,即細化,將任務進行細化,它把一個耗時長的任務分成很多小片,每一個小片的運行時間很短,雖然總時間依然很長,但是在每個小片執行完之後,都給其他任務一個執行的機會,這樣唯一的線程就不會被獨佔,其他任務依然有運行的機會,React 中的 Fiber 就把整個 VDOM 的更新過程碎片化

在之前 React 中的 render() 方法會接收一個 虛擬DOM 對象和一個真實的 容器DOM 作為 虛擬DOM 渲染完成後的掛載節點,其主要作用就是將 虛擬DOM 渲染為 真實DOM 並掛載到容器下,這個方法在更新的時候是進行遞歸操作的,如果在更新的過程中有大量的節點需要更新,就會出現長時間佔用 JS 主線程的情況,並且整個遞歸過程是無法被打斷的,由於 JS 線程和 GUI 線程是互斥的(詳看👉「硬核JS」一次搞懂JS運行機制),所以大量更新的情況下你可能會看到界面有些卡頓

Fiber 架構其實就解決兩個問題,一是保證任務在瀏覽器空閒的時候執行,二是將任務進行碎片化,接下來我們簡單説下 Fiber

JS 中有一個實驗性質的方法 requestIdleCallback(callback) ,它可以傳入一個回調函數,回調函數能夠收到一個 deadline 對象,通過該對象的 timeRemaining() 方法可以獲取到當前瀏覽器的空閒時間,如果有空閒時間,那麼就可以執行一小段任務,如果時間不足了,則繼續 requestIdleCallback,等到瀏覽器又有空閒時間的時候再接着執行,這樣就實現了瀏覽器空閒的時候執行

但是 虛擬DOM 是樹結構,當任務被打斷後,樹結構無法恢復之前的任務繼續執行,所以需要一種新的數據結構,也就是我們的鏈表,鏈表可以包含多個指針,Fiber 採用的鏈表中就包含三個指針,parent 指向其父 Fiber 節點,child 指向其子 Fiber 節點,sibling 指向其兄弟 Fiber 節點,一個 Fiber 節點對應一個任務節點,這樣就可以輕易找到下一個節點,繼而也就可以恢復任務的執行

這簡簡單單的一段,就是大名鼎鼎的 Fiber 架構,那麼你説鏈表有用嗎?

説了這麼多,其實對於普通需求,我們 JS 確實不需要用到鏈表,數組能完爆它,但是特殊需求裏,鏈表獨具它一定的優勢,總之三個字,看需求,再者,我們現在是在用 JS 來闡述鏈表,但是其它常規語言可沒有 JS 中的數組這麼強悍,而且學會了鏈表,我們下一個學習樹結構時就更加得心應手了

最後

文中的案例完整代碼地址如下 👇

單雙鏈表DEMO

此文介紹數據結構之一的鏈表,作為鏈表刷題前的小知識

上班摸魚水羣不如摸魚刷道算法,百利無一害,堅持每天刷題吧,加油

GitHub建了個算法倉庫,從零更算法題/文字/視頻 題解ing,一塊來刷吧 👉 GitHub傳送門

此文視頻版本詳見 👉 B站傳送門

看到這裏了,來個三連吧,如有錯誤請指正,也歡迎大家關注公眾號「不正經的前端」,和算法羣的朋友們組團刷算法,效率更高