前端進階:從零實現單向 & 雙向鏈表
前言
前端工程師對于算法和數據結構這塊的知識的掌握程度，是進階高級工程師的非常重要的標志之一，為了總結一下數據結構和算法方面的知識，筆者今天繼續把鏈表這一塊的知識補上，也作為自己知識體系的一個梳理，筆者早在去年就寫過一篇關于使用javascript實現二叉樹和二叉搜索樹的文章，如果感興趣或者想進階高級的朋友們可以參考學習一下： JavaScript 中的二叉樹以及二叉搜索樹的實現及應用.
你將收獲
- 鏈表的概念和應用
- 原生javascript實現一條單向鏈表
- 原生javascript實現一條個雙單向鏈表
- 鏈表和數組的對比及優缺點
正文
1. 鏈表的概念和應用
鏈表是一種線性表數據結構，由一系列結點(鏈表中每一個元素稱為結點)組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。
以上概念用圖表示為以下結構：
鏈表是非連續的，所以說從底層存儲結構上看，它不需要一整塊連續的存儲空間，而是通過“指針”將一組零散的數據單元串聯起來成為一個整體。鏈表也有幾種不同的類型：單向鏈表，雙向鏈表，循環鏈表。上圖就是一種單向鏈表。由其定義不難發現雙向鏈表無非就是每個節點加上了前后節點的指針引用，如下圖所示：
那什么是循環鏈表呢?循環鏈表本質上是一種特殊的單向鏈表，唯一的區別就在于它的尾結點指向了鏈表的頭結點，這樣首尾相連，形成了一個環，所以叫做循環鏈表。如下圖所示：
當然我們還可以擴展出雙向循環鏈表，這里就不一一舉例了。總之鏈表結構在計算機底層語言中應用的比較多，當我們在用高級語言做編程時可能不會察覺，比如我們用javascript敲js的時候，其實我們在深入了解鏈表之后我們就會發現鏈表有很多應用場景，比如LRU 緩存淘汰，最近消息推送等。
舉個更接地氣的，當我們在用PS畫圖時軟件提供了一個動作面板，可以記錄用戶之前的操作記錄，并批量執行動作，或者當我們在使用編輯器時的回退撤銷功能等，用鏈表結構來存儲狀態信息還是比較方便的。
最近比較火的react hooks API，其結構也是一個鏈表型的數據結構，所以學習鏈表還是非常有幫助的。讀到這里可能還是有點懵，接下來我們先用js實現一個鏈表，這樣有助于理解鏈表的本質，后面筆者會總結一下鏈表和數組的對比以及優劣勢，方便大家對鏈表有一個更加直觀的認識。
2.原生javascript實現一條單向鏈表
在上面一節介紹的鏈表結構中大家可能對鏈表有了初步的認識，因為javascript中沒有鏈表的數據結構，為了模擬鏈表結構，我們可以通過js面向對象的方式實現一個鏈表結構及其API，具體設計如下：
有了以上需求點之后，這個鏈表才是基本可用的鏈表，那么我們一步步來實現它吧。
2.1 定義鏈表結構
為了實現鏈表以及鏈表的操作，首先我們需要先定義鏈表的基本結構，第一步就是定義節點的數據結構。我們知道一個節點會有自己的值以及指向下一個節點的引用，所以可以這樣定義節點：
- let Node = function(el) {
- this.el = el;
- this.next = null;
- }
接下來我們定義一下鏈表的基本骨架：
- // 單向鏈表, 每一個元素都有一個存儲元素自身的節點和一個指向下一個元素引用的節點組成
- function linkedList() {
- let Node = function(el) {
- this.el = el;
- this.next = null;
- }
- let length = 0
- let head = null // 用來存儲第一個元素的引用
- // 尾部添加元素
- this.append = (el) => {};
- //插入元素
- this.insert = (pos, el) => {};
- // 移除指定位置的元素
- this.removeAt = (pos) => {};
- // 移除指定節點
- this.remove = (el) => {};
- // 查詢節點所在位置
- this.indexOf = (el) => {};
- // 判斷鏈表是否為空
- this.isEmpty = () => {};
- // 返回鏈表長度
- this.size = () => {};
- // 將鏈表轉化為數組返回
- this.toArray = () => {};
- }
由以上代碼我們可以知道鏈表的初始長度為0，頭部元素為null，接下來我們實現添加節點的功能。
2.2 實現添加節點
追加節點的時候首先需要知道頭部節點是否存在，如果不存在直接賦值，存在的話則從頭部開始遍歷，直到找到下一個節點為空的節點，再賦值，并將鏈表長度+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 實現插入節點
實現插入節點邏輯首先我們要考慮邊界條件，如果插入的位置在頭部或者比尾部位置還大，我們就沒必要從頭遍歷一遍處理了，這樣可以提高性能，所以我們可以這樣處理：
- //插入元素
- 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 根據節點的值查詢節點位置
根據節點的值查詢節點位置實現起來比較簡單，我們只要從頭開始遍歷，然后找到對應的值之后記錄一下索引即可：
- // 查詢節點所在位置
- 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兩個變量來處理，是因為如果用戶傳入的值不在鏈表里，那么idx的值就會有問題，所以用curIdx來保證準確性。
2.5 移除指定位置的節點
移除指定位置的節點也需要判斷一下邊界條件，可插入節點類似，但要注意移除之后一定要將鏈表長度-1，代碼如下：
- // 移除指定位置的元素
- this.removeAt = (pos) => {
- // 檢測邊界條件
- if(pos >=0 && pos < length) {
- let previousNode = null,
- current = head,
- curIdx = 0;
- if(pos === 0) {
- // 如果pos為第一個元素
- 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 移除指定節點
移除指定節點實現非常簡單，我們只需要利用之前實現好的查找節點先找到節點的位置，然后再用實現過的removeAt即可，代碼如下：
- // 移除指定節點
- this.remove = (el) => {
- let idx = this.indexOf(el);
- this.removeAt(idx);
- };
2.7 獲取節點長度
這里比較簡單，直接上代碼：
- // 返回鏈表長度
- this.size = () => {
- return length
- };
2.8 判斷鏈表是否為空
判斷鏈表是否為空我們只需要判斷長度是否為零即可：
- // 返回鏈表長度
- this.size = () => {
- return length
- };
2.9 打印節點
打印節點實現方式有很多，大家可以按照自己喜歡的格式打印，這里筆者直接將其打印為數組格式輸出，代碼如下：
- // 將鏈表轉化為數組返回
- this.toArray = () => {
- let current = head,
- results = [];
- while(current) {
- results.push(current.el);
- current = current.next;
- }
- return results
- };
這樣，我們的單向鏈表就實現了，那么我們可以這么使用：
- let link = new linkedList()
- // 添加節點
- link.append(1)
- link.append(2)
- // 查找節點
- link.indexOf(2)
- // ...
3.原生javascript實現一條個雙單向鏈表
有了單向鏈表的實現基礎，實現雙向鏈表也很簡單了，我們無非要關注的是雙向鏈表的節點創建，這里筆者實現一個例子供大家參考：
- let Node = function(el) {
- this.el = el;
- this.previous = null;
- this.next = null;
- }
- let length = 0
- let head = null // 用來存儲頭部元素的引用
- let tail = null // 用來存儲尾部元素的引用
由代碼可知我們在節點中會有上一個節點的引用以及下一個節點的引用，同時這里筆者添加了頭部節點和尾部節點方便大家操作。大家可以根據自己的需求實現雙向鏈表的功能，這里筆者提供一份自己實現的代碼，可以參考交流一下：
- // 雙向鏈表, 每一個元素都有一個存儲元素自身的節點和指向上一個元素引用以及下一個元素引用的節點組成
- function doubleLinkedList() {
- let Node = function(el) {
- this.el = el;
- this.previous = null;
- this.next = null;
- }
- let length = 0
- let head = null // 用來存儲頭部元素的引用
- let tail = null // 用來存儲尾部元素的引用
- // 尾部添加元素
- 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) => {
- // 檢測邊界條件
- if(pos < 0 || pos >= length) {
- throw new RangeError(`刪除范圍有誤`)
- }else {
- if(length) {
- if(pos === length - 1) {
- // 如果刪除節點位置為尾節點,直接刪除,節省查找時間
- 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
- }
- }
- };
- // 移除指定節點
- this.remove = (el) => {
- let idx = this.indexOf(el);
- this.removeAt(idx);
- };
- // 查詢指定位置的鏈表元素
- 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
- }
- }
- }
- // 查詢節點所在位置
- 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
- };
- // 返回鏈表長度
- this.size = () => {
- return length
- };
- // 將鏈表轉化為數組返回
- this.toArray = () => {
- let current = head,
- results = [];
- while(current) {
- results.push(current.el);
- current = current.next;
- }
- return results
- };
- }
4.鏈表和數組的對比及優缺點
實現完鏈表之后我們會對鏈表有更深入的認知，接下來我們進一步分析鏈表的優缺點。筆者將從3個維度來帶大家分析鏈表的性能情況：
- 插入刪除性能
- 查詢性能
- 內存占用
我們先看看插入和刪除的過程：
由上圖可以發現，鏈表的插入、刪除數據效率非常高，只需要考慮相鄰結點的指針變化，因為不需要移動其他節點，時間復雜度是 O(1)。
再來看看查詢過程：
我們對鏈表進行每一次查詢時，都需要從鏈表的頭部開始找起，一步步遍歷到目標節點，這個過程效率是非常低的，時間復雜度是 O(n)。這方面我們使用數組的話效率會更高一點。
我們再看看內存占用。鏈表的內存消耗比較大，因為每個結點除了要存儲數據本身，還要儲存前后結點的地址。但是好處是可以動態分配內存。
另一方面，對于數組來說，也存在一些缺點，比如數組必須占用整塊、連續的內存空間，如果聲明的數組數據量過大，可能會導致“內存不足”。其次就是數組一旦需要擴容，會重新申請連續的內存空間，并且需要把上一次的數組數據全部copy到新的內存空間中。
綜上所述，當我們的數據存在頻繁的插入刪除操作時，我們可以采用鏈表結構來存儲我們的數據，如果涉及到頻繁查找的操作，我們可以采用數組來處理。實際工作中很多底層框架的封裝都是采用組合模式進行設計，一般純粹采用某種數據結構的比較少，所以具體還是要根據所處環境進行適當的方案設計。
