[[378875]]

 本文轉(zhuǎn)載自微信公眾號「不正經(jīng)的前端」，作者 isboyjc   。轉(zhuǎn)載本文請聯(lián)系不正經(jīng)的前端公眾號。

寫在前面

此文會先探討下什么是鏈表以及在 JavaScript 中的鏈表，接著我們會使用 JavaScript 這門語言動手實現(xiàn)下各類鏈表的設(shè)計，最后我們會拋出一些常規(guī)疑問，并從各個方面一一解答，總之，目的就是完全搞定鏈表

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

什么是鏈表

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

而鏈表存儲的也是有序的元素集合，但不同于數(shù)組的是，鏈表中的元素在內(nèi)存中并不是連續(xù)的，每個元素由一個存儲元素本身的節(jié)點和一個指向下一個元素的引用(也可以稱為指針)組成

 

我們接著再來看數(shù)組這種數(shù)據(jù)結(jié)構(gòu)，它有一個缺點，在大多數(shù)語言中數(shù)組的大小是固定的，從數(shù)組的起點或中間插入或移除項的成本很高，因為需要移動元素，如下圖

 

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

我們再來看看鏈表

 

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

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

JavaScript中的鏈表

上面我們簡單介紹了常規(guī)鏈表的概念，但是在 JavaScript 這門語言中，我們怎么表示鏈表呢?

由于 JS 中沒有內(nèi)置鏈表這種數(shù)據(jù)結(jié)構(gòu)，所以我們需要使用對象來模擬實現(xiàn)鏈表，就如同我們上面介紹鏈表，它其實是一個單向鏈表，除此之外還有雙向鏈表、環(huán)形鏈表等等，我們接下來會一一介紹并使用 JavaScript 來實現(xiàn)下

單向鏈表

我們先來看基礎(chǔ)的單項鏈表，單向鏈表每個元素由一個存儲元素本身的節(jié)點和一個指向下一個元素的指針構(gòu)成，如下圖

 

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

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

/** 
 * @description: 創(chuàng)建鏈表單節(jié)點類 
 * @param {*} val 節(jié)點值 
 * @return {*} 
 */ 
function ListNode(val) { 
  this.val = val 
  this.next = null 
} 

接著，我們需要先寫一個鏈表類，其中 length屬性 代表鏈表長度，head屬性 代表鏈表頭部節(jié)點

/** 
 * @description: 創(chuàng)建鏈表類 
 * @param {*} 
 * @return {*} 
 */ 
function LinkedList() { 
  this.length = 0 
  this.head = null 
} 

我們思考下，既然是來模擬一個鏈表類，那么就應(yīng)該把它所有可能會用到的特性都塞進(jìn)這個類里，就比如數(shù)組有 push/splice/indexOf/... 等等這些好用的方法我們鏈表必須也得有啊，我們先仔細(xì)構(gòu)思下要給鏈表添加哪些實用的特性或者說方法，先搭一個基礎(chǔ)骨架，這里我列出了很多，我們來一一實現(xiàn)下，也歡迎補充

// 向鏈表中追加節(jié)點 
LinkedList.prototype.append = function (val) { } 
 
// 在鏈表的指定位置插入節(jié)點 
LinkedList.prototype.insert = function (index, val) { } 
 
// 刪除鏈表中指定位置的元素，并返回這個元素的值 
LinkedList.prototype.removeAt = function (index) { } 
 
// 刪除鏈表中對應(yīng)的元素 
LinkedList.prototype.remove = function (val) { } 
 
// 獲取鏈表中給定元素的索引 
LinkedList.prototype.indexOf = function (val) { } 
 
// 獲取鏈表中某個節(jié)點 
LinkedList.prototype.find = function (val) { } 
 
// 獲取鏈表中索引所對應(yīng)的元素 
LinkedList.prototype.getElementAt = function (index) { } 
 
// 判斷鏈表是否為空 
LinkedList.prototype.isEmpty = function () { } 
 
// 獲取鏈表的長度 
LinkedList.prototype.size = function () { } 
 
// 獲取鏈表的頭元素 
LinkedList.prototype.getHead = function () { } 
 
// 清空鏈表 
LinkedList.prototype.clear = function () { } 
 
// 序列化鏈表 
LinkedList.prototype.join = function (string) { } 

getElementAt(index)

我們先來實現(xiàn)獲取鏈表中索引所對應(yīng)的元素即 getElementAt 方法以及通過節(jié)點值獲取鏈表元素即 find 方法，因為后面要多次用到它們，我們先說 getElementAt 方法，上面我們說想要找一個元素，我們必須從頭迭代，所以我們直接根據(jù)傳入的索引進(jìn)行迭代即可

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

// 獲取鏈表中索引所對應(yīng)的元素 
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 方法類似，一個通過索引找元素，一個通過節(jié)點值找元素，所以我們直接迭代查找對比即可

// 獲取鏈表中某個節(jié)點 
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 方法后，接下來我們就可以很方便地實現(xiàn) append 方法，此方法的作用是在鏈表末尾追加元素

此方法傳入的是一個值，我們可以通過上面的構(gòu)造函數(shù) ListNode 來創(chuàng)建一個新節(jié)點

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

新添加的元素 next 指針默認(rèn)為 null，鏈表最后一個元素的 next 值也就為 null，另外，將節(jié)點掛到鏈表上之后，還需將鏈表的長度加 1，保證 length 屬性等于鏈表長度，如下

// 向鏈表中追加節(jié)點 
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)

接下來我們要實現(xiàn) insert 方法，即在鏈表的任意位置添加節(jié)點

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

接著我們分兩種情況考慮

當(dāng) index 的值為 0 時，表示要在鏈表的頭部插入新節(jié)點，將新插入節(jié)點的 next 指針指向現(xiàn)在的 head，然后更新 head 的值為新插入的節(jié)點即可，如下圖

當(dāng) index 的值不為 0 時，即插入的節(jié)點在鏈表的中間或者尾部，我們首先找到待插入位置的前一個節(jié)點 prevNode，然后將新節(jié)點 newNode 的 next 指針指向 prevNode 的 next 所對應(yīng)的節(jié)點，再將 prevNode 的 next 指針指向 newNode，這樣就把新節(jié)點插入鏈表中了，當(dāng)插入的節(jié)點在鏈表的尾部，這種方法也同樣適用，如下圖 

最后，我們插入了節(jié)點，還需要將鏈表的長度即 length 長度加 1，代碼如下

// 在鏈表的指定位置插入節(jié)點 
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 方法，用來刪除鏈表中指定位置的節(jié)點

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

還是分兩種情況

如果要刪除的節(jié)點是鏈表的頭部，將 head 移到下一個節(jié)點即可，如果當(dāng)前鏈表只有一個節(jié)點，那么下一個節(jié)點為 null，此時將 head 指向下一個節(jié)點等同于將 head 設(shè)置成 null，刪除之后鏈表為空

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

image-20201227180444604

 被刪除的節(jié)點沒有了引用關(guān)系，JavaScript 垃圾回收機制會處理它，關(guān)于垃圾回收機制，同樣不在此文討論范圍內(nèi)，知道即可，刪除節(jié)點元素，我們還需將鏈表的長度減 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)

獲取鏈表中給定元素的索引，這個比較簡單，直接迭代即可，匹配到了返回對應(yīng)索引，匹配不到返回 -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)

刪除鏈表中對應(yīng)的元素，有了之前的鋪墊，這里就比較簡單了，我們可以直接用 indexOf 方法拿到對應(yīng)索引，再使用 removeAt 方法刪除節(jié)點即可

// 刪除鏈表中對應(yīng)的元素 
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 
} 

join(string)

序列化鏈表即使用指定格式輸出鏈表，類似于數(shù)組中 join 方法，此舉旨在便于我們測試

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

那么到此，我們的單向鏈表類就設(shè)計完成了，快來測試一下吧，我們輸入下面代碼進(jìn)行測試

let linkedList = new LinkedList() 
linkedList.append(10) 
linkedList.append(20) 
linkedList.append(30) 
 
console.log(linkedList.join("--")) 
 
linkedList.insert(0, 5) 
linkedList.insert(2, 15) 
linkedList.insert(4, 25) 
console.log(linkedList.join("--")) 
 
console.log(linkedList.removeAt(0)) 
console.log(linkedList.removeAt(1)) 
console.log(linkedList.removeAt(2)) 
console.log(linkedList.join("--")) 
 
console.log(linkedList.indexOf(20)) 
 
linkedList.remove(20) 
 
console.log(linkedList.join("--")) 
 
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 

上面代碼中少了一些參數(shù)校驗，不過夠我們學(xué)習(xí)用了，完成代碼文末附鏈接

雙向鏈表

上面我們說了單向鏈表，接下來我們來說雙向鏈表，那么什么是雙向鏈表呢?其實聽名字就可以聽出來，單向鏈表中每一個元素只有一個 next 指針，用來指向下一個節(jié)點，我們只能從鏈表的頭部開始遍歷整個鏈表，任何一個節(jié)點只能找到它的下一個節(jié)點，而不能找到它的上一個節(jié)點，雙向鏈表中的每一個元素?fù)碛袃蓚€指針，一個用來指向下一個節(jié)點，一個用來指向上一個節(jié)點，雙向鏈表中，除了可以像單向鏈表一樣從頭部開始遍歷之外，還可以從尾部進(jìn)行遍歷，如下圖

同單向鏈表，我們首先創(chuàng)建鏈表節(jié)點類，不同的是，它需要多一個 prev 屬性用來指向前一個節(jié)點

/** 
 * @description: 創(chuàng)建雙向鏈表單節(jié)點類 
 * @param {*} val 節(jié)點值 
 * @return {*} 
 */ 
function ListNode(val) { 
  this.val = val 
  this.next = null 
  this.prev = null 
} 

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

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

接下來我們來實現(xiàn)雙向鏈表的原型方法

getElementAt(index)

首先就是，獲取雙向鏈表中索引所對應(yīng)的元素，雙向鏈表由于可以雙向進(jìn)行迭代查找，所以這里 getElementAt 方法我們可以進(jìn)行優(yōu)化，當(dāng)索引大于鏈表長度 length/2 時，我們可以從后往前找，反之則從前向后找，這樣可以更快找到該節(jié)點元素

// 獲取雙向鏈表中索引所對應(yīng)的元素 
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 方法可以優(yōu)化，那么find 再變成雙向鏈表后也可優(yōu)化，我們想，既然雙向都可以進(jìn)行迭代，那么我們兩邊同時迭代豈不是更快，雙向迭代的情況下，只有找不到時才會迭代整個鏈表，效率更高

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

append(val)

又來到了我們的追加節(jié)點元素，雙向鏈表追加與單向鏈表還是有些區(qū)別的

當(dāng)鏈表為空時，除了要將 head 指向當(dāng)前添加的節(jié)點外，還要將 tail 也指向當(dāng)前要添加的節(jié)點

當(dāng)鏈表不為空時，直接將 tail 的 next 指向當(dāng)前要添加的節(jié)點 node，然后修改node 的 prev 指向舊的 tail，最后修改 tail 為新添加的節(jié)點

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

// 向雙向鏈表中追加節(jié)點 
DoubleLinkedList.prototype.append = function (val) { 
  let node = new ListNode(val) 
 
  if (this.head === null) { 
    // 鏈表為空，head 和 tail 都指向當(dāng)前添加的節(jié)點 
    this.head = node 
    this.tail = node 
  } 
  else { 
    // 鏈表不為空，將當(dāng)前節(jié)點添加到鏈表的尾部 
    this.tail.next = node 
    node.prev = this.tail 
    this.tail = node 
  } 
 
  this.length++ 
} 

insert(index, val)

接著是插入節(jié)點元素方法，同樣思路一致，并不困難，我們注意 tail 及 prev 指針分情況討論，插入后長度加 1 即可

// 在雙向鏈表的指定位置插入節(jié)點 
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)

刪除雙向鏈表中指定位置的元素，同樣是注意 tail 及 prev 指針分情況討論，最后刪除后長度減 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 
} 

joinstring)

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

// 序列化雙向鏈表 
DoubleLinkedList.prototype.join = 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.join("<->")) 
 
console.log(doubleLinkedList.getElementAt(0).val) 
console.log(doubleLinkedList.getElementAt(1).val) 
console.log(doubleLinkedList.getElementAt(5)) 
 
console.log(doubleLinkedList.join("<->")) 
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.join("<->")) 
 
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.join("<->")) 

上面代碼輸出如下

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

環(huán)形鏈表

我們再來看另一種鏈表，環(huán)形鏈表，顧名思義，環(huán)形鏈表的尾部節(jié)點指向它自己的頭節(jié)點

環(huán)形鏈表有單向環(huán)形鏈表，也可以有雙向環(huán)形鏈表，如下圖

 

單雙環(huán)形鏈表這里我們就不再一一的寫了，你可以嘗試自己寫一下，對比上面我們環(huán)形鏈表只需要注意下尾部節(jié)點要指向頭節(jié)點即可

為什么JavaScript中不內(nèi)置鏈表?

根據(jù)我們上面所說，鏈表有這么多優(yōu)點，那么為什么 JavaScript 這門語言不內(nèi)置鏈表這種數(shù)據(jù)結(jié)構(gòu)呢?

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

我們來用事實說話，現(xiàn)在我們用上面完成的單向鏈表類 LinkedList，同原生數(shù)組做一個簡單的的時間測試

let linkedList = new LinkedList() 
let arr = [] 
 
// 測試 分別嘗試 「總數(shù)100 插入節(jié)點50」/「總數(shù)100000 插入節(jié)點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('數(shù)組push操作') 
for (let i = 0; i < count; i++) { 
  arr.push(i) 
} 
console.timeEnd('數(shù)組push操作') 
 
 
console.time('鏈表insert操作') 
linkedList.insert('test節(jié)點', insertIndex) 
console.timeEnd('鏈表insert操作') 
 
console.time('數(shù)組insert操作') 
arr.splice(insertIndex, 0, 'test節(jié)點') 
console.timeEnd('數(shù)組insert操作') 
 
 
console.time('鏈表remove操作') 
linkedList.removeAt(insertIndex) 
console.timeEnd('鏈表remove操作') 
 
console.time('數(shù)組remove操作') 
arr.splice(insertIndex, 1) 
console.timeEnd('數(shù)組remove操作') 

我們來看下結(jié)果

追加 100 個數(shù)據(jù)，在索引 50 插入元素，再刪除插入的元素

追加 100000 個數(shù)據(jù)，在索引 50000 插入元素，再刪除插入的元素

What??????

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

也就是說鏈表效率高于數(shù)組效率這種話，事實上在 JS 中是不存在的，即使你創(chuàng)建一個長度為 1 億的數(shù)組，再創(chuàng)建一個長度為 10 的數(shù)組，并且向這兩個數(shù)組的中間添加元素，console.time 時間出來看看，你會發(fā)現(xiàn)所用時間與數(shù)組長度長度無關(guān)，這說明 JS 數(shù)組達(dá)到了鏈表的效率要求

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

當(dāng)然，這只局限于 JavaScript 這門語言中，這和 JS 內(nèi)部的數(shù)組實現(xiàn)機制有關(guān)，其實 JS 中的數(shù)組只是叫數(shù)組而已，它和常規(guī)語言中的數(shù)組概念就不同，那么關(guān)于數(shù)組概念以及內(nèi)部實現(xiàn)，不在我們此章節(jié)討論范圍之內(nèi)，先留一個疑問，過幾天有空了再另起一篇 JS 數(shù)組相關(guān)的文章吧，其實自己找去答案最好了，我們說 JS 是一門解釋型高級語言，它的底層實現(xiàn)并不像我們看起來那么簡單循規(guī)，有點打破常規(guī)的意思

講的這里，你可能會吐槽這一篇文章好不容易看完了，現(xiàn)在你給我說沒用。。。不要著急，收好臭雞蛋

JavaScript中鏈表無用?

如我們上面所說，難道 JavaScript 中的鏈表當(dāng)真就毫無作用了嗎?

其實也不是，就比如三大法寶之一 React 中的 Fiber 架構(gòu)，就用到了鏈表這種數(shù)據(jù)結(jié)構(gòu)

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

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

Fiber 架構(gòu)其實就解決兩個問題，一是保證任務(wù)在瀏覽器空閑的時候執(zhí)行，二是將任務(wù)進(jìn)行碎片化，接下來我們簡單說下 Fiber

JS 中有一個實驗性質(zhì)的方法 requestIdleCallback(callback) ，它可以傳入一個回調(diào)函數(shù)，回調(diào)函數(shù)能夠收到一個 deadline 對象，通過該對象的timeRemaining() 方法可以獲取到當(dāng)前瀏覽器的空閑時間，如果有空閑時間，那么就可以執(zhí)行一小段任務(wù)，如果時間不足了，則繼續(xù) requestIdleCallback，等到瀏覽器又有空閑時間的時候再接著執(zhí)行，這樣就實現(xiàn)了瀏覽器空閑的時候執(zhí)行

但是 虛擬DOM 是樹結(jié)構(gòu)，當(dāng)任務(wù)被打斷后，樹結(jié)構(gòu)無法恢復(fù)之前的任務(wù)繼續(xù)執(zhí)行，所以需要一種新的數(shù)據(jù)結(jié)構(gòu)，也就是我們的鏈表，鏈表可以包含多個指針，F(xiàn)iber 采用的鏈表中就包含三個指針，parent 指向其父 Fiber 節(jié)點，child 指向其子 Fiber 節(jié)點，sibling 指向其兄弟 Fiber 節(jié)點，一個 Fiber 節(jié)點對應(yīng)一個任務(wù)節(jié)點，這樣就可以輕易找到下一個節(jié)點，繼而也就可以恢復(fù)任務(wù)的執(zhí)行

這簡簡單單的一段，就是大名鼎鼎的 Fiber 架構(gòu)，那么你說鏈表有用嗎?

說了這么多，其實對于普通需求，我們 JS 確實不需要用到鏈表，數(shù)組能完爆它，但是特殊需求里，鏈表獨具它一定的優(yōu)勢，總之三個字，看需求，再者，我們現(xiàn)在是在用 JS 來闡述鏈表，但是其它常規(guī)語言可沒有 JS 中的數(shù)組這么強悍，而且學(xué)會了鏈表，我們下一個學(xué)習(xí)樹結(jié)構(gòu)時就更加得心應(yīng)手了

最后

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

單雙鏈表DEMO[1]

此文介紹數(shù)據(jù)結(jié)構(gòu)之一的鏈表，作為鏈表刷題前的小知識

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

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

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

看到這里了，來個三連吧，如有錯誤請指正，也歡迎大家關(guān)注公眾號「不正經(jīng)的前端」，和算法群的朋友們組團刷算法，效率更高

Reference

[1]單雙鏈表DEMO:

https://github.com/isboyjc/DailyAlgorithms/tree/master/demo/algorithm[2]GitHub傳送門:

https://github.com/isboyjc/DailyAlgorithms[3]B站傳送門:

https://www.bilibili.com/video/BV1aV411q7WF