[[397775]]

前言

前端工程師對(duì)于算法和數(shù)據(jù)結(jié)構(gòu)這塊的知識(shí)的掌握程度，是進(jìn)階高級(jí)工程師的非常重要的標(biāo)志之一，為了總結(jié)一下數(shù)據(jù)結(jié)構(gòu)和算法方面的知識(shí)，筆者今天繼續(xù)把鏈表這一塊的知識(shí)補(bǔ)上，也作為自己知識(shí)體系的一個(gè)梳理，筆者早在去年就寫(xiě)過(guò)一篇關(guān)于使用javascript實(shí)現(xiàn)二叉樹(shù)和二叉搜索樹(shù)的文章，如果感興趣或者想進(jìn)階高級(jí)的朋友們可以參考學(xué)習(xí)一下： JavaScript 中的二叉樹(shù)以及二叉搜索樹(shù)的實(shí)現(xiàn)及應(yīng)用.

你將收獲

• 鏈表的概念和應(yīng)用
• 原生javascript實(shí)現(xiàn)一條單向鏈表
• 原生javascript實(shí)現(xiàn)一條個(gè)雙單向鏈表
• 鏈表和數(shù)組的對(duì)比及優(yōu)缺點(diǎn)

正文

1. 鏈表的概念和應(yīng)用

鏈表是一種線(xiàn)性表數(shù)據(jù)結(jié)構(gòu)，由一系列結(jié)點(diǎn)(鏈表中每一個(gè)元素稱(chēng)為結(jié)點(diǎn))組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。

以上概念用圖表示為以下結(jié)構(gòu)：

鏈表是非連續(xù)的，所以說(shuō)從底層存儲(chǔ)結(jié)構(gòu)上看，它不需要一整塊連續(xù)的存儲(chǔ)空間，而是通過(guò)“指針”將一組零散的數(shù)據(jù)單元串聯(lián)起來(lái)成為一個(gè)整體。鏈表也有幾種不同的類(lèi)型：?jiǎn)蜗蜴湵?，雙向鏈表，循環(huán)鏈表。上圖就是一種單向鏈表。由其定義不難發(fā)現(xiàn)雙向鏈表無(wú)非就是每個(gè)節(jié)點(diǎn)加上了前后節(jié)點(diǎn)的指針引用，如下圖所示：

那什么是循環(huán)鏈表呢?循環(huán)鏈表本質(zhì)上是一種特殊的單向鏈表，唯一的區(qū)別就在于它的尾結(jié)點(diǎn)指向了鏈表的頭結(jié)點(diǎn)，這樣首尾相連，形成了一個(gè)環(huán)，所以叫做循環(huán)鏈表。如下圖所示：

當(dāng)然我們還可以擴(kuò)展出雙向循環(huán)鏈表，這里就不一一舉例了?？傊湵斫Y(jié)構(gòu)在計(jì)算機(jī)底層語(yǔ)言中應(yīng)用的比較多，當(dāng)我們?cè)谟酶呒?jí)語(yǔ)言做編程時(shí)可能不會(huì)察覺(jué)，比如我們用javascript敲js的時(shí)候，其實(shí)我們?cè)谏钊肓私怄湵碇笪覀兙蜁?huì)發(fā)現(xiàn)鏈表有很多應(yīng)用場(chǎng)景，比如LRU 緩存淘汰，最近消息推送等。

舉個(gè)更接地氣的，當(dāng)我們?cè)谟肞S畫(huà)圖時(shí)軟件提供了一個(gè)動(dòng)作面板，可以記錄用戶(hù)之前的操作記錄，并批量執(zhí)行動(dòng)作，或者當(dāng)我們?cè)谑褂镁庉嬈鲿r(shí)的回退撤銷(xiāo)功能等，用鏈表結(jié)構(gòu)來(lái)存儲(chǔ)狀態(tài)信息還是比較方便的。

最近比較火的react hooks API，其結(jié)構(gòu)也是一個(gè)鏈表型的數(shù)據(jù)結(jié)構(gòu)，所以學(xué)習(xí)鏈表還是非常有幫助的。讀到這里可能還是有點(diǎn)懵，接下來(lái)我們先用js實(shí)現(xiàn)一個(gè)鏈表，這樣有助于理解鏈表的本質(zhì)，后面筆者會(huì)總結(jié)一下鏈表和數(shù)組的對(duì)比以及優(yōu)劣勢(shì)，方便大家對(duì)鏈表有一個(gè)更加直觀的認(rèn)識(shí)。

2.原生javascript實(shí)現(xiàn)一條單向鏈表

在上面一節(jié)介紹的鏈表結(jié)構(gòu)中大家可能對(duì)鏈表有了初步的認(rèn)識(shí)，因?yàn)閖avascript中沒(méi)有鏈表的數(shù)據(jù)結(jié)構(gòu)，為了模擬鏈表結(jié)構(gòu)，我們可以通過(guò)js面向?qū)ο蟮姆绞綄?shí)現(xiàn)一個(gè)鏈表結(jié)構(gòu)及其API，具體設(shè)計(jì)如下：

有了以上需求點(diǎn)之后，這個(gè)鏈表才是基本可用的鏈表，那么我們一步步來(lái)實(shí)現(xiàn)它吧。

2.1 定義鏈表結(jié)構(gòu)

為了實(shí)現(xiàn)鏈表以及鏈表的操作，首先我們需要先定義鏈表的基本結(jié)構(gòu)，第一步就是定義節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)。我們知道一個(gè)節(jié)點(diǎn)會(huì)有自己的值以及指向下一個(gè)節(jié)點(diǎn)的引用，所以可以這樣定義節(jié)點(diǎn)：

let Node = function(el) { 
      this.el = el; 
      this.next = null; 
 } 

接下來(lái)我們定義一下鏈表的基本骨架：

// 單向鏈表, 每一個(gè)元素都有一個(gè)存儲(chǔ)元素自身的節(jié)點(diǎn)和一個(gè)指向下一個(gè)元素引用的節(jié)點(diǎn)組成 
function linkedList() { 
  let Node = function(el) { 
      this.el = el; 
      this.next = null; 
  } 
  let length = 0 
  let head = null  // 用來(lái)存儲(chǔ)第一個(gè)元素的引用 
 
  // 尾部添加元素 
  this.append = (el) => {}; 
  //插入元素 
  this.insert = (pos, el) => {}; 
  // 移除指定位置的元素 
  this.removeAt = (pos) => {}; 
  // 移除指定節(jié)點(diǎn) 
  this.remove = (el) => {}; 
  // 查詢(xún)節(jié)點(diǎn)所在位置 
  this.indexOf = (el) => {}; 
  // 判斷鏈表是否為空 
  this.isEmpty = () => {}; 
  // 返回鏈表長(zhǎng)度 
  this.size = () => {}; 
  // 將鏈表轉(zhuǎn)化為數(shù)組返回 
  this.toArray = () => {}; 
} 

由以上代碼我們可以知道鏈表的初始長(zhǎng)度為0，頭部元素為null，接下來(lái)我們實(shí)現(xiàn)添加節(jié)點(diǎn)的功能。

2.2 實(shí)現(xiàn)添加節(jié)點(diǎn)

追加節(jié)點(diǎn)的時(shí)候首先需要知道頭部節(jié)點(diǎn)是否存在，如果不存在直接賦值，存在的話(huà)則從頭部開(kāi)始遍歷，直到找到下一個(gè)節(jié)點(diǎn)為空的節(jié)點(diǎn)，再賦值，并將鏈表長(zhǎng)度+1，代碼如下：

// 尾部添加元素 
this.append = (el) => { 
    let node = new Node(el), 
        current; 
    if(!head) { 
      head = node 
    }else { 
      current = head; 
      while(current.next) { 
        current = current.next; 
      } 
      current.next = node; 
    } 
    length++ 
}; 

2.3 實(shí)現(xiàn)插入節(jié)點(diǎn)

實(shí)現(xiàn)插入節(jié)點(diǎn)邏輯首先我們要考慮邊界條件，如果插入的位置在頭部或者比尾部位置還大，我們就沒(méi)必要從頭遍歷一遍處理了，這樣可以提高性能，所以我們可以這樣處理：

//插入元素 
this.insert = (pos, el) => { 
    if(pos >=0 && pos <= length) { 
      let node = new Node(el), 
          previousNode = null, 
          current = head, 
          curIdx = 0; 
      if(pos === 0) { 
        node.next = current; 
        head = node; 
      }else { 
        while(curIdx++ < pos) { 
          previousNode = current; 
          current = current.next; 
        } 
        node.next = current; 
        previousNode.next = node; 
        length++; 
        return true 
      } 
    }else { 
      return false 
    } 
}; 

2.4 根據(jù)節(jié)點(diǎn)的值查詢(xún)節(jié)點(diǎn)位置

根據(jù)節(jié)點(diǎn)的值查詢(xún)節(jié)點(diǎn)位置實(shí)現(xiàn)起來(lái)比較簡(jiǎn)單，我們只要從頭開(kāi)始遍歷，然后找到對(duì)應(yīng)的值之后記錄一下索引即可：

// 查詢(xún)節(jié)點(diǎn)所在位置 
this.indexOf = (el) => { 
    let idx = -1, 
        curIdx = -1, 
        current = head; 
    while(current) { 
      idx++ 
      if(current.el === el) { 
        curIdx = idx 
        break; 
      } 
      current = current.next; 
    } 
    return curIdx 
}; 

這里我們之所以要用idx和curIdx兩個(gè)變量來(lái)處理，是因?yàn)槿绻脩?hù)傳入的值不在鏈表里，那么idx的值就會(huì)有問(wèn)題，所以用curIdx來(lái)保證準(zhǔn)確性。

2.5 移除指定位置的節(jié)點(diǎn)

移除指定位置的節(jié)點(diǎn)也需要判斷一下邊界條件，可插入節(jié)點(diǎn)類(lèi)似，但要注意移除之后一定要將鏈表長(zhǎng)度-1，代碼如下：

// 移除指定位置的元素 
this.removeAt = (pos) => { 
    // 檢測(cè)邊界條件 
    if(pos >=0 && pos < length) { 
      let previousNode = null, 
               current = head, 
               curIdx = 0; 
      if(pos === 0) { 
        // 如果pos為第一個(gè)元素 
        head = current.next 
      }else { 
        while(curIdx++ < pos) { 
          previousNode = current; 
          current = current.next; 
        } 
        previousNode.next = current.next; 
      } 
      length --; 
      return current.el 
    }else { 
      return null 
    } 
}; 

2.6 移除指定節(jié)點(diǎn)

移除指定節(jié)點(diǎn)實(shí)現(xiàn)非常簡(jiǎn)單，我們只需要利用之前實(shí)現(xiàn)好的查找節(jié)點(diǎn)先找到節(jié)點(diǎn)的位置，然后再用實(shí)現(xiàn)過(guò)的removeAt即可，代碼如下：

// 移除指定節(jié)點(diǎn) 
this.remove = (el) => { 
  let idx = this.indexOf(el); 
  this.removeAt(idx); 
}; 

2.7 獲取節(jié)點(diǎn)長(zhǎng)度

這里比較簡(jiǎn)單，直接上代碼：

// 返回鏈表長(zhǎng)度 
this.size = () => { 
  return length 
}; 

2.8 判斷鏈表是否為空

判斷鏈表是否為空我們只需要判斷長(zhǎng)度是否為零即可：

// 返回鏈表長(zhǎng)度 
this.size = () => { 
  return length 
}; 

2.9 打印節(jié)點(diǎn)

打印節(jié)點(diǎn)實(shí)現(xiàn)方式有很多，大家可以按照自己喜歡的格式打印，這里筆者直接將其打印為數(shù)組格式輸出，代碼如下：

// 將鏈表轉(zhuǎn)化為數(shù)組返回 
this.toArray = () => { 
    let current = head, 
        results = []; 
    while(current) { 
      results.push(current.el); 
      current = current.next; 
    } 
    return results 
};  

這樣，我們的單向鏈表就實(shí)現(xiàn)了，那么我們可以這么使用：

let link = new linkedList() 
// 添加節(jié)點(diǎn) 
link.append(1) 
link.append(2) 
// 查找節(jié)點(diǎn) 
link.indexOf(2) 
// ... 

3.原生javascript實(shí)現(xiàn)一條個(gè)雙單向鏈表

有了單向鏈表的實(shí)現(xiàn)基礎(chǔ)，實(shí)現(xiàn)雙向鏈表也很簡(jiǎn)單了，我們無(wú)非要關(guān)注的是雙向鏈表的節(jié)點(diǎn)創(chuàng)建，這里筆者實(shí)現(xiàn)一個(gè)例子供大家參考：

let Node = function(el) { 
      this.el = el; 
      this.previous = null; 
      this.next = null; 
 } 
let length = 0 
let head = null  // 用來(lái)存儲(chǔ)頭部元素的引用 
let tail = null  // 用來(lái)存儲(chǔ)尾部元素的引用 

由代碼可知我們?cè)诠?jié)點(diǎn)中會(huì)有上一個(gè)節(jié)點(diǎn)的引用以及下一個(gè)節(jié)點(diǎn)的引用，同時(shí)這里筆者添加了頭部節(jié)點(diǎn)和尾部節(jié)點(diǎn)方便大家操作。大家可以根據(jù)自己的需求實(shí)現(xiàn)雙向鏈表的功能，這里筆者提供一份自己實(shí)現(xiàn)的代碼，可以參考交流一下：

// 雙向鏈表, 每一個(gè)元素都有一個(gè)存儲(chǔ)元素自身的節(jié)點(diǎn)和指向上一個(gè)元素引用以及下一個(gè)元素引用的節(jié)點(diǎn)組成 
function doubleLinkedList() { 
  let Node = function(el) { 
      this.el = el; 
      this.previous = null; 
      this.next = null; 
  } 
  let length = 0 
  let head = null  // 用來(lái)存儲(chǔ)頭部元素的引用 
  let tail = null  // 用來(lái)存儲(chǔ)尾部元素的引用 
 
  // 尾部添加元素 
  this.append = (el) => { 
    let node = new Node(el) 
    if(!head) { 
      head = node 
    }else { 
      tail.next = node; 
      node.previous = tail; 
    } 
    tail = node; 
    length++ 
  }; 
  // 插入元素 
  this.insert = (pos, el) => { 
    if(pos >=0 && pos < length) { 
      let node = new Node(el); 
      if(pos === length - 1) { 
        // 在尾部插入 
        node.previous = tail.previous; 
        node.next = tail; 
        tail.previous = node; 
        length++; 
        return true 
      } 
      let current = head, 
          i = 0; 
      while(i < pos) { 
        current = current.next; 
        i++ 
      } 
      node.next = current; 
      node.previous = current.previous; 
      current.previous.next = node; 
      current.previous = node; 
      length ++; 
      return true     
    }else { 
      throw new RangeError(`插入范圍有誤`) 
    } 
  }; 
  // 移除指定位置的元素 
  this.removeAt = (pos) => { 
    // 檢測(cè)邊界條件 
    if(pos < 0 || pos >= length) { 
      throw new RangeError(`刪除范圍有誤`) 
    }else { 
      if(length) { 
        if(pos === length - 1) { 
          // 如果刪除節(jié)點(diǎn)位置為尾節(jié)點(diǎn),直接刪除,節(jié)省查找時(shí)間 
          let previous = tail.previous; 
          previous.next = null; 
          length --; 
          return tail.el 
        }else { 
          let current = head, 
              previous = null, 
              next = null, 
              i = 0; 
          while(i < pos) { 
            current = current.next 
            i++ 
          } 
          previous = current.previous; 
          next = current.next; 
          previous.next = next; 
          length --; 
          return current.el 
        } 
      }else { 
        return null 
      } 
    } 
  }; 
  // 移除指定節(jié)點(diǎn) 
  this.remove = (el) => { 
    let idx = this.indexOf(el); 
    this.removeAt(idx); 
  }; 
  // 查詢(xún)指定位置的鏈表元素 
  this.get = (index) => { 
    if(index < 0 || index >= length) { 
      return undefined 
    }else { 
      if(length) { 
        if(index === length - 1) { 
          return tail.el 
        } 
        let current = head, 
            i = 0; 
        while(i < index) { 
          current = current.next 
          i++ 
        } 
        return current.el 
      }else { 
        return undefined 
      } 
    } 
  } 
  // 查詢(xún)節(jié)點(diǎn)所在位置 
  this.indexOf = (el) => { 
    let idx = -1, 
        current = head, 
        curIdx = -1; 
    while(current) { 
      idx++ 
      if(current.el === el) { 
        curIdx = idx; 
        break; 
      } 
      current = current.next; 
    } 
    return curIdx 
  }; 
  // 判斷鏈表是否為空 
  this.isEmpty = () => { 
    return length === 0 
  }; 
  // 返回鏈表長(zhǎng)度 
  this.size = () => { 
    return length 
  }; 
  // 將鏈表轉(zhuǎn)化為數(shù)組返回 
  this.toArray = () => { 
    let current = head, 
        results = []; 
    while(current) { 
      results.push(current.el); 
      current = current.next; 
    } 
    return results 
  }; 
} 

4.鏈表和數(shù)組的對(duì)比及優(yōu)缺點(diǎn)

實(shí)現(xiàn)完鏈表之后我們會(huì)對(duì)鏈表有更深入的認(rèn)知，接下來(lái)我們進(jìn)一步分析鏈表的優(yōu)缺點(diǎn)。筆者將從3個(gè)維度來(lái)帶大家分析鏈表的性能情況：

• 插入刪除性能
• 查詢(xún)性能
• 內(nèi)存占用

我們先看看插入和刪除的過(guò)程：

由上圖可以發(fā)現(xiàn)，鏈表的插入、刪除數(shù)據(jù)效率非常高，只需要考慮相鄰結(jié)點(diǎn)的指針變化，因?yàn)椴恍枰苿?dòng)其他節(jié)點(diǎn)，時(shí)間復(fù)雜度是 O(1)。

再來(lái)看看查詢(xún)過(guò)程：

我們對(duì)鏈表進(jìn)行每一次查詢(xún)時(shí)，都需要從鏈表的頭部開(kāi)始找起，一步步遍歷到目標(biāo)節(jié)點(diǎn)，這個(gè)過(guò)程效率是非常低的，時(shí)間復(fù)雜度是 O(n)。這方面我們使用數(shù)組的話(huà)效率會(huì)更高一點(diǎn)。

我們?cè)倏纯磧?nèi)存占用。鏈表的內(nèi)存消耗比較大，因?yàn)槊總€(gè)結(jié)點(diǎn)除了要存儲(chǔ)數(shù)據(jù)本身，還要儲(chǔ)存前后結(jié)點(diǎn)的地址。但是好處是可以動(dòng)態(tài)分配內(nèi)存。

另一方面，對(duì)于數(shù)組來(lái)說(shuō)，也存在一些缺點(diǎn)，比如數(shù)組必須占用整塊、連續(xù)的內(nèi)存空間，如果聲明的數(shù)組數(shù)據(jù)量過(guò)大，可能會(huì)導(dǎo)致“內(nèi)存不足”。其次就是數(shù)組一旦需要擴(kuò)容，會(huì)重新申請(qǐng)連續(xù)的內(nèi)存空間，并且需要把上一次的數(shù)組數(shù)據(jù)全部copy到新的內(nèi)存空間中。

綜上所述，當(dāng)我們的數(shù)據(jù)存在頻繁的插入刪除操作時(shí)，我們可以采用鏈表結(jié)構(gòu)來(lái)存儲(chǔ)我們的數(shù)據(jù)，如果涉及到頻繁查找的操作，我們可以采用數(shù)組來(lái)處理。實(shí)際工作中很多底層框架的封裝都是采用組合模式進(jìn)行設(shè)計(jì)，一般純粹采用某種數(shù)據(jù)結(jié)構(gòu)的比較少，所以具體還是要根據(jù)所處環(huán)境進(jìn)行適當(dāng)?shù)姆桨冈O(shè)計(jì)。