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

永興網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)！從網(wǎng)頁設(shè)計、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、成都響應(yīng)式網(wǎng)站建設(shè)公司等網(wǎng)站項目制作，到程序開發(fā)，運營維護。創(chuàng)新互聯(lián)于2013年創(chuàng)立到現(xiàn)在10年的時間，我們擁有了豐富的建站經(jīng)驗和運維經(jīng)驗，來保證我們的工作的順利進行。專注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)。

寫在前面

什么是鏈表以及在 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ù)組中少了一位或者多了一位，那么后面的元素都要依次向前或向后移動一位，那么可想而之，當數(shù)組長度很大的時候，插入及刪除的效率就會逐漸降低

我們再來看看鏈表

同樣是刪除元素 3，鏈表這里只需要迭代到值為 3 的節(jié)點，將節(jié)點 2 指向節(jié)點 4 就行了，節(jié)點 3  沒有了引用關(guān)系，就會被垃圾回收機制當作垃圾回收了，即使當節(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)該把它所有可能會用到的特性都塞進這個類里，就比如數(shù)組有 push/splice/indexOf/...  等等這些好用的方法我們鏈表必須也得有啊，我們先仔細構(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ù)傳入的索引進行迭代即可

首先判斷參數(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 指針默認為 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 索引是否超出邊界

接著我們分兩種情況考慮

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

當 index 的值不為 0 時，即插入的節(jié)點在鏈表的中間或者尾部，我們首先找到待插入位置的前一個節(jié)點 prevNode，然后將新節(jié)點 newNode 的  next 指針指向 prevNode 的 next 所對應(yīng)的節(jié)點，再將 prevNode 的 next 指針指向  newNode，這樣就把新節(jié)點插入鏈表中了，當插入的節(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é)點即可，如果當前鏈表只有一個節(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è)計完成了，快來測試一下吧，我們輸入下面代碼進行測試

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é)點，雙向鏈表中的每一個元素擁有兩個指針，一個用來指向下一個節(jié)點，一個用來指向上一個節(jié)點，雙向鏈表中，除了可以像單向鏈表一樣從頭部開始遍歷之外，還可以從尾部進行遍歷，如下圖

同單向鏈表，我們首先創(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)的元素，雙向鏈表由于可以雙向進行迭代查找，所以這里 getElementAt 方法我們可以進行優(yōu)化，當索引大于鏈表長度  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)化，我們想，既然雙向都可以進行迭代，那么我們兩邊同時迭代豈不是更快，雙向迭代的情況下，只有找不到時才會迭代整個鏈表，效率更高

// 獲取雙向鏈表中某個節(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ū)別的

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

當鏈表不為空時，直接將 tail 的 next 指向當前要添加的節(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 都指向當前添加的節(jié)點     this.head = node     this.tail = node   }   else {     // 鏈表不為空，將當前節(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ù)組達到了鏈表的效率要求

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

當然，這只局限于 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 中的鏈表當真就毫無作用了嗎?

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

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

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

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

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

但是 虛擬DOM 是樹結(jié)構(gòu)，當任務(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)手了

以上就是JavaScript中的鏈表是怎樣的，小編相信有部分知識點可能是我們?nèi)粘９ぷ鲿姷交蛴玫降?。希望你能通過這篇文章學(xué)到更多知識。更多詳情敬請關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

當前文章：JavaScript中的鏈表是怎樣的
URL鏈接：http://aaarwkj.com/article26/pchjcg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信小程序、面包屑導(dǎo)航、服務(wù)器托管、外貿(mào)網(wǎng)站建設(shè)、軟件開發(fā)、營銷型網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)