「算法與數據結構」JavaScript中的鏈表
本文轉載自微信公眾號「不正經的前端」，作者 isboyjc 。轉載本文請聯系不正經的前端公眾號。
寫在前面
此文會先探討下什么是鏈表以及在 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.join = 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 來創建一個新節點
而后，我們需要考慮，如果鏈表的 head 為 null 時，這種情況表示鏈表為空，所以需要將 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，然后將新節點 newNode 的 next 指針指向 prevNode 的 next 所對應的節點，再將 prevNode 的 next 指針指向 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
- }
join(string)
序列化鏈表即使用指定格式輸出鏈表，類似于數組中 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
- }
那么到此，我們的單向鏈表類就設計完成了，快來測試一下吧，我們輸入下面代碼進行測試
- 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
上面代碼中少了一些參數校驗，不過夠我們學習用了，完成代碼文末附鏈接
雙向鏈表
上面我們說了單向鏈表，接下來我們來說雙向鏈表，那么什么是雙向鏈表呢?其實聽名字就可以聽出來，單向鏈表中每一個元素只有一個 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 再變成雙向鏈表后也可優化，我們想，既然雙向都可以進行迭代，那么我們兩邊同時迭代豈不是更快，雙向迭代的情況下，只有找不到時才會迭代整個鏈表，效率更高
- // 獲取雙向鏈表中某個節點
- 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)
又來到了我們的追加節點元素，雙向鏈表追加與單向鏈表還是有些區別的
當鏈表為空時，除了要將 head 指向當前添加的節點外，還要將 tail 也指向當前要添加的節點
當鏈表不為空時，直接將 tail 的 next 指向當前要添加的節點 node，然后修改node 的 prev 指向舊的 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)
接著是插入節點元素方法，同樣思路一致，并不困難，我們注意 tail 及 prev 指針分情況討論，插入后長度加 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)
刪除雙向鏈表中指定位置的元素，同樣是注意 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
環形鏈表
我們再來看另一種鏈表，環形鏈表，顧名思義，環形鏈表的尾部節點指向它自己的頭節點
環形鏈表有單向環形鏈表，也可以有雙向環形鏈表，如下圖
單雙環形鏈表這里我們就不再一一的寫了，你可以嘗試自己寫一下，對比上面我們環形鏈表只需要注意下尾部節點要指向頭節點即可
為什么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[1]
此文介紹數據結構之一的鏈表，作為鏈表刷題前的小知識
上班摸魚水群不如摸魚刷道算法，百利無一害，堅持每天刷題吧，加油
GitHub建了個算法倉庫，從零更算法題/文字/視頻 題解ing，一塊來刷吧 👉 GitHub傳送門[2]
此文視頻版本詳見 👉 B站傳送門[3]
看到這里了，來個三連吧，如有錯誤請指正，也歡迎大家關注公眾號「不正經的前端」，和算法群的朋友們組團刷算法，效率更高
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
