JavaScript中的鏈表是怎樣的

本篇文章給大家分享的是有關(guān)JavaScript中的鏈表是怎樣的，小編覺(jué)得挺實(shí)用的，因此分享給大家學(xué)習(xí)，希望大家閱讀完這篇文章后可以有所收獲，話不多說(shuō)，跟著小編一起來(lái)看看吧。

寫在前面

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

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

什么是鏈表

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

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

我們接著再來(lái)看數(shù)組這種數(shù)據(jù)結(jié)構(gòu)，它有一個(gè)缺點(diǎn)，在大多數(shù)語(yǔ)言中數(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è)賮?lái)看看鏈表

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

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

JavaScript中的鏈表

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

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

單向鏈表

我們先來(lái)看基礎(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 中究竟要如何來(lái)模擬呢，我們一步一步來(lái)

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

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

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

首先判斷參數(shù) index 的邊界值，如果值超出了索引的范圍(小于 0 或者大于 length - 1)，則返回null，我們從鏈表的 head  節(jié)點(diǎn)開(kāi)始，遍歷整個(gè)鏈表直到找到對(duì)應(yīng)索引位置的節(jié)點(diǎn)，然后返回這個(gè)節(jié)點(diǎn)，是不是很簡(jiǎn)單?和所有有序數(shù)據(jù)集合一樣，鏈表的索引也是從 0  開(kāi)始，只要有鏈表的頭節(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è)通過(guò)索引找元素，一個(gè)通過(guò)節(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 方法后，接下來(lái)我們就可以很方便地實(shí)現(xiàn) append 方法，此方法的作用是在鏈表末尾追加元素

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

而后，我們需要考慮，如果鏈表的 head 為 null 時(shí)，這種情況表示鏈表為空，所以需要將 head  節(jié)點(diǎn)指向新添加的元素，以此來(lái)確保存儲(chǔ)頭節(jié)點(diǎn)，如果不為空，我們通過(guò)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)

接下來(lái)我們要實(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 方法，用來(lái)刪除鏈表中指定位置的節(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)的指針，斷開(kāi)刪除位置左右相鄰的節(jié)點(diǎn)再重新連接上即可

image-20201227180444604

被刪除的節(jié)點(diǎn)沒(méi)有了引用關(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ī)制回收無(wú)引用的廢棄鏈表即可

// 清空鏈表 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ì)完成了，快來(lái)測(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)，不過(guò)夠我們學(xué)習(xí)用了，完成代碼文末附鏈接

雙向鏈表

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

同單向鏈表，我們首先創(chuàng)建鏈表節(jié)點(diǎn)類，不同的是，它需要多一個(gè) prev 屬性用來(lái)指向前一個(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 }

接下來(lái)我們來(lái)實(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)

又來(lái)到了我們的追加節(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)

雙向鏈表的追加操作我們不需要從頭開(kāi)始遍歷整個(gè)鏈表，通過(guò) 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 指針?lè)智闆r討論，插入后長(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 指針?lè)智闆r討論，最后刪除后長(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)單，就不贅述了，文末雙向鏈表案例中有完整代碼

同樣，我們來(lái)簡(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

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

環(huán)形鏈表

我們?cè)賮?lái)看另一種鏈表，環(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ù)我們上面所說(shuō)，鏈表有這么多優(yōu)點(diǎn)，那么為什么 JavaScript 這門語(yǔ)言不內(nèi)置鏈表這種數(shù)據(jù)結(jié)構(gòu)呢?

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

我們來(lái)用事實(shí)說(shuō)話，現(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操作')

我們來(lái)看下結(jié)果

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

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

What??????

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

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

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

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

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

JavaScript中鏈表無(wú)用?

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

其實(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 的更新過(guò)程碎片化

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

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

JS 中有一個(gè)實(shí)驗(yàn)性質(zhì)的方法 requestIdleCallback(callback) ，它可以傳入一個(gè)回調(diào)函數(shù)，回調(diào)函數(shù)能夠收到一個(gè) deadline  對(duì)象，通過(guò)該對(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)無(wú)法恢復(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)，那么你說(shuō)鏈表有用嗎?

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

以上就是JavaScript中的鏈表是怎樣的，小編相信有部分知識(shí)點(diǎn)可能是我們?nèi)粘９ぷ鲿?huì)見(jiàn)到或用到的。希望你能通過(guò)這篇文章學(xué)到更多知識(shí)。更多詳情敬請(qǐng)關(guān)注億速云行業(yè)資訊頻道。