日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
前端進(jìn)階:從零實現(xiàn)單向&雙向鏈表

前言

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

專業(yè)成都網(wǎng)站建設(shè)公司，做排名好的好網(wǎng)站，排在同行前面，為您帶來客戶和效益!創(chuàng)新互聯(lián)為您提供成都網(wǎng)站建設(shè)，五站合一網(wǎng)站設(shè)計制作，服務(wù)好的網(wǎng)站設(shè)計公司，成都做網(wǎng)站、成都網(wǎng)站設(shè)計負(fù)責(zé)任的成都網(wǎng)站制作公司!

你將收獲

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

正文

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

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

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

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

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

當(dāng)然我們還可以擴(kuò)展出雙向循環(huán)鏈表，這里就不一一舉例了?？傊湵斫Y(jié)構(gòu)在計算機(jī)底層語言中應(yīng)用的比較多，當(dāng)我們在用高級語言做編程時可能不會察覺，比如我們用javascript敲js的時候，其實我們在深入了解鏈表之后我們就會發(fā)現(xiàn)鏈表有很多應(yīng)用場景，比如LRU 緩存淘汰，最近消息推送等。

舉個更接地氣的，當(dāng)我們在用PS畫圖時軟件提供了一個動作面板，可以記錄用戶之前的操作記錄，并批量執(zhí)行動作，或者當(dāng)我們在使用編輯器時的回退撤銷功能等，用鏈表結(jié)構(gòu)來存儲狀態(tài)信息還是比較方便的。

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

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

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

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

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

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

 
 
 
 
    
  
  
  
  
  1. let Node = function(el) {
    2. 
  
  
  
  
  2.       this.el = el;
    3. 
  
  
  
  
  3.       this.next = null;
    4. 
  
  
  
  
  4.  }
    5.

接下來我們定義一下鏈表的基本骨架：

 
 
 
 
    
  
  
  
  
  1. // 單向鏈表, 每一個元素都有一個存儲元素自身的節(jié)點(diǎn)和一個指向下一個元素引用的節(jié)點(diǎn)組成
    2. 
  
  
  
  
  2. function linkedList() {
    3. 
  
  
  
  
  3.   let Node = function(el) {
    4. 
  
  
  
  
  4.       this.el = el;
    5. 
  
  
  
  
  5.       this.next = null;
    6. 
  
  
  
  
  6.   }
    7. 
  
  
  
  
  7.   let length = 0
    8. 
  
  
  
  
  8.   let head = null  // 用來存儲第一個元素的引用
    9. 
  
  
  
  
  9. 
  
  
  
  
  10.   // 尾部添加元素
    11. 
  
  
  
  
  11.   this.append = (el) => {};
    12. 
  
  
  
  
  12.   //插入元素
    13. 
  
  
  
  
  13.   this.insert = (pos, el) => {};
    14. 
  
  
  
  
  14.   // 移除指定位置的元素
    15. 
  
  
  
  
  15.   this.removeAt = (pos) => {};
    16. 
  
  
  
  
  16.   // 移除指定節(jié)點(diǎn)
    17. 
  
  
  
  
  17.   this.remove = (el) => {};
    18. 
  
  
  
  
  18.   // 查詢節(jié)點(diǎn)所在位置
    19. 
  
  
  
  
  19.   this.indexOf = (el) => {};
    20. 
  
  
  
  
  20.   // 判斷鏈表是否為空
    21. 
  
  
  
  
  21.   this.isEmpty = () => {};
    22. 
  
  
  
  
  22.   // 返回鏈表長度
    23. 
  
  
  
  
  23.   this.size = () => {};
    24. 
  
  
  
  
  24.   // 將鏈表轉(zhuǎn)化為數(shù)組返回
    25. 
  
  
  
  
  25.   this.toArray = () => {};
    26. 
  
  
  
  
  26. }
    27.

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

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

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

 
 
 
 
    
  
  
  
  
  1. // 尾部添加元素
    2. 
  
  
  
  
  2. this.append = (el) => {
    3. 
  
  
  
  
  3.     let node = new Node(el),
    4. 
  
  
  
  
  4.         current;
    5. 
  
  
  
  
  5.     if(!head) {
    6. 
  
  
  
  
  6.       head = node
    7. 
  
  
  
  
  7.     }else {
    8. 
  
  
  
  
  8.       current = head;
    9. 
  
  
  
  
  9.       while(current.next) {
    10. 
  
  
  
  
  10.         current = current.next;
    11. 
  
  
  
  
  11.       }
    12. 
  
  
  
  
  12.       current.next = node;
    13. 
  
  
  
  
  13.     }
    14. 
  
  
  
  
  14.     length++
    15. 
  
  
  
  
  15. };
    16.

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

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

 
 
 
 
    
  
  
  
  
  1. //插入元素
    2. 
  
  
  
  
  2. this.insert = (pos, el) => {
    3. 
  
  
  
  
  3.     if(pos >=0 && pos <= length) {
    4. 
  
  
  
  
  4.       let node = new Node(el),
    5. 
  
  
  
  
  5.           previousNode = null,
    6. 
  
  
  
  
  6.           current = head,
    7. 
  
  
  
  
  7.           curIdx = 0;
    8. 
  
  
  
  
  8.       if(pos === 0) {
    9. 
  
  
  
  
  9.         node.next = current;
    10. 
  
  
  
  
  10.         head = node;
    11. 
  
  
  
  
  11.       }else {
    12. 
  
  
  
  
  12.         while(curIdx++ < pos) {
    13. 
  
  
  
  
  13.           previousNode = current;
    14. 
  
  
  
  
  14.           current = current.next;
    15. 
  
  
  
  
  15.         }
    16. 
  
  
  
  
  16.         node.next = current;
    17. 
  
  
  
  
  17.         previousNode.next = node;
    18. 
  
  
  
  
  18.         length++;
    19. 
  
  
  
  
  19.         return true
    20. 
  
  
  
  
  20.       }
    21. 
  
  
  
  
  21.     }else {
    22. 
  
  
  
  
  22.       return false
    23. 
  
  
  
  
  23.     }
    24. 
  
  
  
  
  24. };
    25.

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

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

 
 
 
 
    
  
  
  
  
  1. // 查詢節(jié)點(diǎn)所在位置
    2. 
  
  
  
  
  2. this.indexOf = (el) => {
    3. 
  
  
  
  
  3.     let idx = -1,
    4. 
  
  
  
  
  4.         curIdx = -1,
    5. 
  
  
  
  
  5.         current = head;
    6. 
  
  
  
  
  6.     while(current) {
    7. 
  
  
  
  
  7.       idx++
    8. 
  
  
  
  
  8.       if(current.el === el) {
    9. 
  
  
  
  
  9.         curIdx = idx
    10. 
  
  
  
  
  10.         break;
    11. 
  
  
  
  
  11.       }
    12. 
  
  
  
  
  12.       current = current.next;
    13. 
  
  
  
  
  13.     }
    14. 
  
  
  
  
  14.     return curIdx
    15. 
  
  
  
  
  15. };
    16.

這里我們之所以要用idx和curIdx兩個變量來處理，是因為如果用戶傳入的值不在鏈表里，那么idx的值就會有問題，所以用curIdx來保證準(zhǔn)確性。

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

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

 
 
 
 
    
  
  
  
  
  1. // 移除指定位置的元素
    2. 
  
  
  
  
  2. this.removeAt = (pos) => {
    3. 
  
  
  
  
  3.     // 檢測邊界條件
    4. 
  
  
  
  
  4.     if(pos >=0 && pos < length) {
    5. 
  
  
  
  
  5.       let previousNode = null,
    6. 
  
  
  
  
  6.                current = head,
    7. 
  
  
  
  
  7.                curIdx = 0;
    8. 
  
  
  
  
  8.       if(pos === 0) {
    9. 
  
  
  
  
  9.         // 如果pos為第一個元素
    10. 
  
  
  
  
  10.         head = current.next
    11. 
  
  
  
  
  11.       }else {
    12. 
  
  
  
  
  12.         while(curIdx++ < pos) {
    13. 
  
  
  
  
  13.           previousNode = current;
    14. 
  
  
  
  
  14.           current = current.next;
    15. 
  
  
  
  
  15.         }
    16. 
  
  
  
  
  16.         previousNode.next = current.next;
    17. 
  
  
  
  
  17.       }
    18. 
  
  
  
  
  18.       length --;
    19. 
  
  
  
  
  19.       return current.el
    20. 
  
  
  
  
  20.     }else {
    21. 
  
  
  
  
  21.       return null
    22. 
  
  
  
  
  22.     }
    23. 
  
  
  
  
  23. };
    24.

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

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

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

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

這里比較簡單，直接上代碼：

 
 
 
 
    
  
  
  
  
  1. // 返回鏈表長度
    2. 
  
  
  
  
  2. this.size = () => {
    3. 
  
  
  
  
  3.   return length
    4. 
  
  
  
  
  4. };
    5.

2.8 判斷鏈表是否為空

判斷鏈表是否為空我們只需要判斷長度是否為零即可：

 
 
 
 
    
  
  
  
  
  1. // 返回鏈表長度
    2. 
  
  
  
  
  2. this.size = () => {
    3. 
  
  
  
  
  3.   return length
    4. 
  
  
  
  
  4. };
    5.

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

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

 
 
 
 
    
  
  
  
  
  1. // 將鏈表轉(zhuǎn)化為數(shù)組返回
    2. 
  
  
  
  
  2. this.toArray = () => {
    3. 
  
  
  
  
  3.     let current = head,
    4. 
  
  
  
  
  4.         results = [];
    5. 
  
  
  
  
  5.     while(current) {
    6. 
  
  
  
  
  6.       results.push(current.el);
    7. 
  
  
  
  
  7.       current = current.next;
    8. 
  
  
  
  
  8.     }
    9. 
  
  
  
  
  9.     return results
    10. 
  
  
  
  
  10. }; 
    11.

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

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

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

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

 
 
 
 
    
  
  
  
  
  1. let Node = function(el) {
    2. 
  
  
  
  
  2.       this.el = el;
    3. 
  
  
  
  
  3.       this.previous = null;
    4. 
  
  
  
  
  4.       this.next = null;
    5. 
  
  
  
  
  5.  }
    6. 
  
  
  
  
  6. let length = 0
    7. 
  
  
  
  
  7. let head = null  // 用來存儲頭部元素的引用
    8. 
  
  
  
  
  8. let tail = null  // 用來存儲尾部元素的引用
    9.

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

 
 
 
 
    
  
  
  
  
  1. // 雙向鏈表, 每一個元素都有一個存儲元素自身的節(jié)點(diǎn)和指向上一個元素引用以及下一個元素引用的節(jié)點(diǎn)組成
    2. 
  
  
  
  
  2. function doubleLinkedList() {
    3. 
  
  
  
  
  3.   let Node = function(el) {
    4. 
  
  
  
  
  4.       this.el = el;
    5. 
  
  
  
  
  5.       this.previous = null;
    6. 
  
  
  
  
  6.       this.next = null;
    7. 
  
  
  
  
  7.   }
    8. 
  
  
  
  
  8.   let length = 0
    9. 
  
  
  
  
  9.   let head = null  // 用來存儲頭部元素的引用
    10. 
  
  
  
  
  10.   let tail = null  // 用來存儲尾部元素的引用
    11. 
  
  
  
  
  11. 
  
  
  
  
  12.   // 尾部添加元素
    13. 
  
  
  
  
  13.   this.append = (el) => {
    14. 
  
  
  
  
  14.     let node = new Node(el)
    15. 
  
  
  
  
  15.     if(!head) {
    16. 
  
  
  
  
  16.       head = node
    17. 
  
  
  
  
  17.     }else {
    18. 
  
  
  
  
  18.       tail.next = node;
    19. 
  
  
  
  
  19.       node.previous = tail;
    20. 
  
  
  
  
  20.     }
    21. 
  
  
  
  
  21.     tail = node;
    22. 
  
  
  
  
  22.     length++
    23. 
  
  
  
  
  23.   };
    24. 
  
  
  
  
  24.   // 插入元素
    25. 
  
  
  
  
  25.   this.insert = (pos, el) => {
    26. 
  
  
  
  
  26.     if(pos >=0 && pos < length) {
    27. 
  
  
  
  
  27.       let node = new Node(el);
    28. 
  
  
  
  
  28.       if(pos === length - 1) {
    29. 
  
  
  
  
  29.         // 在尾部插入
    30. 
  
  
  
  
  30.         node.previous = tail.previous;
    31. 
  
  
  
  
  31.         node.next = tail;
    32. 
  
  
  
  
  32.         tail.previous = node;
    33. 
  
  
  
  
  33.         length++;
    34. 
  
  
  
  
  34.         return true
    35. 
  
  
  
  
  35.       }
    36. 
  
  
  
  
  36.       let current = head,
    37. 
  
  
  
  
  37.           i = 0;
    38. 
  
  
  
  
  38.       while(i < pos) {
    39. 
  
  
  
  
  39.         current = current.next;
    40. 
  
  
  
  
  40.         i++
    41. 
  
  
  
  
  41.       }
    42. 
  
  
  
  
  42.       node.next = current;
    43. 
  
  
  
  
  43.       node.previous = current.previous;
    44. 
  
  
  
  
  44.       current.previous.next = node;
    45. 
  
  
  
  
  45.       current.previous = node;
    46. 
  
  
  
  
  46.       length ++;
    47. 
  
  
  
  
  47.       return true    
    48. 
  
  
  
  
  48.     }else {
    49. 
  
  
  
  
  49.       throw new RangeError(`插入范圍有誤`)
    50. 
  
  
  
  
  50.     }
    51. 
  
  
  
  
  51.   };
    52. 
  
  
  
  
  52.   // 移除指定位置的元素
    53. 
  
  
  
  
  53.   this.removeAt = (pos) => {
    54. 
  
  
  
  
  54.     // 檢測邊界條件
    55. 
  
  
  
  
  55.     if(pos < 0 || pos >= length) {
    56. 
  
  
  
  
  56.       throw new RangeError(`刪除范圍有誤`)
    57. 
  
  
  
  
  57.     }else {
    58. 
  
  
  
  
  58.       if(length) {
    59. 
  
  
  
  
  59.         if(pos === length - 1) {
    60. 
  
  
  
  
  60.           // 如果刪除節(jié)點(diǎn)位置為尾節(jié)點(diǎn),直接刪除,節(jié)省查找時間
    61. 
  
  
  
  
  61.           let previous = tail.previous;
    62. 
  
  
  
  
  62.           previous.next = null;
    63. 
  
  
  
  
  63.           length --;
    64. 
  
  
  
  
  64.           return tail.el
    65. 
  
  
  
  
  65.         }else {
    66. 
  
  
  
  
  66.           let current = head,
    67. 
  
  
  
  
  67.               previous = null,
    68. 
  
  
  
  
  68.               next = null,
    69. 
  
  
  
  
  69.               i = 0;
    70. 
  
  
  
  
  70.           while(i < pos) {
    71. 
  
  
  
  
  71.             current = current.next
    72. 
  
  
  
  
  72.             i++
    73. 
  
  
  
  
  73.           }
    74. 
  
  
  
  
  74.           previous = current.previous;
    75. 
  
  
  
  
  75.           next = current.next;
    76. 
  
  
  
  
  76.           previous.next = next;
    77. 
  
  
  
  
  77.           length --;
    78. 
  
  
  
  
  78.           return current.el
    79. 
  
  
  
  
  79.         }
    80. 
  
  
  
  
  80.       }else {
    81. 
  
  
  
  
  81.         return null
    82. 
  
  
  
  
  82.       }
    83. 
  
  
  
  
  83.     }
    84. 
  
  
  
  
  84.   };
    85. 
  
  
  
  
  85.   // 移除指定節(jié)點(diǎn)
    86. 
  
  
  
  
  86.   this.remove = (el) => {
    87. 
  
  
  
  
  87.     let idx = this.indexOf(el);
    88. 
  
  
  
  
  88.     this.removeAt(idx);
    89. 
  
  
  
  
  89.   };
    90. 
  
  
  
  
  90.   // 查詢指定位置的鏈表元素
    91. 
  
  
  
  
  91.   this.get = (index) => {
    92. 
  
  
  
  
  92.     if(index < 0 || index >= length) {
    93. 
  
  
  
  
  93.       return undefined
    94. 
  
  
  
  
  94.     }else {
    95. 
  
  
  
  
  95.       if(length) {
    96. 
  
  
  
  
  96.         if(index === length - 1) {
    97. 
  
  
  
  
  97.           return tail.el
    98. 
  
  
  
  
  98.         }
    99. 
  
  
  
  
  99.         let current = head,
    100. 
  
  
  
  
  100.             i = 0;
    101. 
  
  
  
  
  101.         while(i < index) {
    102. 
  
  
  
  
  102.           current = current.next
    103. 
  
  
  
  
  103.           i++
    104. 
  
  
  
  
  104.         }
    105. 
  
  
  
  
  105.         return current.el
    106. 
  
  
  
  
  106.       }else {
    107. 
  
  
  
  
  107.         return undefined
    108. 
  
  
  
  
  108.       }
    109. 
  
  
  
  
  109.     }
    110. 
  
  
  
  
  110.   }
    111. 
  
  
  
  
  111.   // 查詢節(jié)點(diǎn)所在位置
    112. 
  
  
  
  
  112.   this.indexOf = (el) => {
    113. 
  
  
  
  
  113.     let idx = -1,
    114. 
  
  
  
  
  114.         current = head,
    115. 
  
  
  
  
  115.         curIdx = -1;
    116. 
  
  
  
  
  116.     while(current) {
    117. 
  
  
  
  
  117.       idx++
    118. 
  
  
  
  
  118.       if(current.el === el) {
    119. 
  
  
  
  
  119.         curIdx = idx;
    120. 
  
  
  
  
  120.         break;
    121. 
  
  
  
  
  121.       }
    122. 
  
  
  
  
  122.       current = current.next;
    123. 
  
  
  
  
  123.     }
    124. 
  
  
  
  
  124.     return curIdx
    125. 
  
  
  
  
  125.   };
    126. 
  
  
  
  
  126.   // 判斷鏈表是否為空
    127. 
  
  
  
  
  127.   this.isEmpty = () => {
    128. 
  
  
  
  
  128.     return length === 0
    129. 
  
  
  
  
  129.   };
    130. 
  
  
  
  
  130.   // 返回鏈表長度
    131. 
  
  
  
  
  131.   this.size = () => {
    132. 
  
  
  
  
  132.     return length
    133. 
  
  
  
  
  133.   };
    134. 
  
  
  
  
  134.   // 將鏈表轉(zhuǎn)化為數(shù)組返回
    135. 
  
  
  
  
  135.   this.toArray = () => {
    136. 
  
  
  
  
  136.     let current = head,
    137. 
  
  
  
  
  137.         results = [];
    138. 
  
  
  
  
  138.     while(current) {
    139. 
  
  
  
  
  139.       results.push(current.el);
    140. 
  
  
  
  
  140.       current = current.next;
    141. 
  
  
  
  
  141.     }
    142. 
  
  
  
  
  142.     return results
    143. 
  
  
  
  
  143.   };
    144. 
  
  
  
  
  144. }
    145.

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

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

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

我們先看看插入和刪除的過程：

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

再來看看查詢過程：

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

我們再看看內(nèi)存占用。鏈表的內(nèi)存消耗比較大，因為每個結(jié)點(diǎn)除了要存儲數(shù)據(jù)本身，還要儲存前后結(jié)點(diǎn)的地址。但是好處是可以動態(tài)分配內(nèi)存。

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

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


標(biāo)題名稱：前端進(jìn)階:從零實現(xiàn)單向&雙向鏈表
文章位置：http://www.5511xx.com/article/djhpdsp.html