[[378875]]

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

寫在前面

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

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

什么是鏈表

通常我們?cè)诔绦蛑邢胍鎯?chǔ)多個(gè)元素，數(shù)組可能是最常用的數(shù)據(jù)結(jié)構(gòu)，數(shù)組這種數(shù)據(jù)結(jié)構(gòu)非常方便，它甚至可以通過非常簡(jiǎn)單的方式即 [] 這種語法來訪問其元素

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

我們接著再來看數(shù)組這種數(shù)據(jù)結(jié)構(gòu)，它有一個(gè)缺點(diǎn)，在大多數(shù)語言中數(shù)組的大小是固定的，從數(shù)組的起點(diǎn)或中間插入或移除項(xiàng)的成本很高，因?yàn)樾枰苿?dòng)元素，如下圖

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

我們?cè)賮砜纯存湵?/p>

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

相對(duì)于傳統(tǒng)的數(shù)組，鏈表的一個(gè)好處就在于，添加或移除元素的時(shí)候不需要移動(dòng)其他元素，但是在數(shù)組中，我們可以直接訪問任何位置的任何元素，鏈表中是不行的，因?yàn)殒湵碇忻總€(gè)節(jié)點(diǎn)只有對(duì)下一個(gè)節(jié)點(diǎn)的引用，所以想訪問鏈表中間的一個(gè)元素，必須要從起點(diǎn)(鏈表頭部節(jié)點(diǎn))開始迭代鏈表直到找到所需的元素，這點(diǎn)需要注意

JavaScript中的鏈表

上面我們簡(jiǎn)單介紹了常規(guī)鏈表的概念，但是在 JavaScript 這門語言中，我們?cè)趺幢硎炬湵砟?

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

單向鏈表

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

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

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

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

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

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

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

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

getElementAt(index)

我們先來實(shí)現(xiàn)獲取鏈表中索引所對(duì)應(yīng)的元素即 getElementAt 方法以及通過節(jié)點(diǎn)值獲取鏈表元素即 find 方法，因?yàn)楹竺嬉啻斡玫剿鼈?，我們先說 getElementAt 方法，上面我們說想要找一個(gè)元素，我們必須從頭迭代，所以我們直接根據(jù)傳入的索引進(jìn)行迭代即可

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

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

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

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

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

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

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

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

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

接著我們分兩種情況考慮

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

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

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

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

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

還是分兩種情況

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

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

image-20201227180444604

 被刪除的節(jié)點(diǎn)沒有了引用關(guān)系，JavaScript 垃圾回收機(jī)制會(huì)處理它，關(guān)于垃圾回收機(jī)制，同樣不在此文討論范圍內(nèi)，知道即可，刪除節(jié)點(diǎn)元素，我們還需將鏈表的長(zhǎng)度減 1，最終代碼如下

// 刪除鏈表中指定位置的元素，并返回這個(gè)元素的值 
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)

獲取鏈表中給定元素的索引，這個(gè)比較簡(jiǎn)單，直接迭代即可，匹配到了返回對(duì)應(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)

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

// 刪除鏈表中對(duì)應(yīng)的元素 
LinkedList.prototype.remove = function (val) { 
  let index = this.indexOf(val) 
  return this.removeAt(index) 
} 

isEmpty()

判斷鏈表是否為空，只需要我們判斷一下鏈表長(zhǎng)度 length 等不等于 0 即可

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

size()

獲取鏈表長(zhǎng)度就是取其 length

// 獲取鏈表的長(zhǎng)度 
LinkedList.prototype.size = function () { 
  return this.length 
} 

getHead()

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

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

clear()

清空鏈表，我們只需要將 head 置空，然后讓 length 等于 0，等待垃圾回收機(jī)制回收無引用的廢棄鏈表即可

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

join(string)

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

// 序列化鏈表 
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ì)完成了，快來測(cè)試一下吧，我們輸入下面代碼進(jìn)行測(cè)試

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ù)校驗(yàn)，不過夠我們學(xué)習(xí)用了，完成代碼文末附鏈接

雙向鏈表

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

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

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

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

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

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

getElementAt(index)

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

// 獲取雙向鏈表中索引所對(duì)應(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)行迭代，那么我們兩邊同時(shí)迭代豈不是更快，雙向迭代的情況下，只有找不到時(shí)才會(huì)迭代整個(gè)鏈表，效率更高

// 獲取雙向鏈表中某個(gè)節(jié)點(diǎn) 
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é)點(diǎn)元素，雙向鏈表追加與單向鏈表還是有些區(qū)別的

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

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

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

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

insert(index, val)

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

// 在雙向鏈表的指定位置插入節(jié)點(diǎn) 
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 指針分情況討論，最后刪除后長(zhǎng)度減 1 即可

// 刪除雙向鏈表中指定位置的元素，并返回這個(gè)元素的值 
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 方法做鋪墊，這里就簡(jiǎn)單了，思路一致，

// 獲取雙向鏈表中給定元素的索引 
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 
} 

雙向鏈表我們就介紹這么多，剩下的方法比較簡(jiǎn)單，就不贅述了，文末雙向鏈表案例中有完整代碼

同樣，我們來簡(jiǎn)單測(cè)試一下對(duì)與否

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 

嗯，沒有報(bào)錯(cuò)，簡(jiǎn)單對(duì)比一下，是正確的，No Problem

環(huán)形鏈表

我們?cè)賮砜戳硪环N鏈表，環(huán)形鏈表，顧名思義，環(huán)形鏈表的尾部節(jié)點(diǎn)指向它自己的頭節(jié)點(diǎn)

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

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

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

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

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

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

let linkedList = new LinkedList() 
let arr = [] 
 
// 測(cè)試 分別嘗試 「總數(shù)100 插入節(jié)點(diǎn)50」/「總數(shù)100000 插入節(jié)點(diǎn)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é)點(diǎn)', insertIndex) 
console.timeEnd('鏈表insert操作') 
 
console.time('數(shù)組insert操作') 
arr.splice(insertIndex, 0, 'test節(jié)點(diǎn)') 
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 個(gè)數(shù)據(jù)，在索引 50 插入元素，再刪除插入的元素

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

What??????

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

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

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

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

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

JavaScript中鏈表無用?

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

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

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

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

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

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

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

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

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

最后

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

單雙鏈表DEMO[1]

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

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

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

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

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

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