動畫：面試如何輕鬆手寫鏈表？

• 2019 年 10 月 7 日
• 筆記

寫在前邊

在上一節的動畫學編程中，主要分享了數組和鏈表的基本知識點，如果還沒掌握，回頭要多學習下，因為後邊的知識會在基礎上進行擴展。

對於數組的學習呢，在前端中，最重要的就是數組的一些方法的使用，數組的截取、查找、反轉等常用的方法；除此之外，數組另一個稍微難點就是演算法題。上一周我又拿起《劍指offer》把關於數組的演算法題刷了一遍，又總結了很多的做題技巧和有關數組的解題思路，後期會分享。

那對於鏈表呢，我們在項目中用到的不如數組頻繁，但是面試是個重點，為什麼面試官喜歡考我們鏈表呢？想必大家對這個問題很感興趣，因為鏈表靈活、涉及到的邊界條件多，又加上很多細節點，對應聘者是一個考驗。

不料，暑假參加的第一個公司的就讓我手寫一個雙向鏈表，並完成插入數據和刪除數據的操作。當時我很蒙蔽，懵逼的不是思路，而是手寫，雖然寫出來了，但是很多邊界條件和程式碼規範自我感覺不好，所以有了這些細心的總結。那麼今天的主題就是徒手寫鏈表，應聘者該如何下手？

我們通常寫鏈表準備應聘的時候，通常背加上理解，但是過了幾天又讓你寫。就會陌生了，雖然有點思路。還是模模糊糊，小鹿也有這個記性的「毛病」，「有毛病」就要治，怎麼治？我們必須在腦海里形成一套可行的步驟和方法，在遇到手寫就不用手忙腳亂，而是穩穩噹噹，從頭到尾寫出一個漂亮的鏈表結構及操作。

思維導圖

1

熟悉結構

首先我們要知道鏈表的結構以及每個節點的結構，這是我們手寫鏈表的第一步，也是學習鏈表的第一步。我們知道，每個鏈表時這樣表示的：

那每個節點結構是由數據域和指針域組成，數據域是存放數據的，而指針域存放下一結點的地址。

我們可以通過數據域訪問到我們要的數據，而通過指針域訪問到當前結點以後的結點，那麼將這些結點串起來，就是一個鏈表。

那麼用程式碼怎麼來表示呢？

我們通常會用到函數，我們如果將一個函數抽象成一個結點，那麼我們給函數添加兩個屬性，一個屬性是存放數據的屬性data，另一個屬性是存放指向下一個結點的指針屬性next。

你可能會問，如果我們有成千上萬個結點，要定義成千上萬個函數？有一個函數叫做構造函數，想必大家都聽說過，聲明一個構造函數就可以創造出成千上萬個結點實例。

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

還有一個方法就是使用類的概念，在JavaScript中，類的概念在ES6才出現，使用 Class 來聲明一個類，我們可以為類添加兩個屬性，同上，一樣可以創造出多個結點實例。

class Node{      constructor(data){          this.data = data;          this.next = null;      }  }

2

理清思路

如果你把鏈表的結構搞得明明白白了，恭喜你，成功的進入第二關，但是你只超越了百分之20的人，繼續加油。

既然鏈表的結構弄明白了，那麼我們開始理思路，我們就先拿最簡單的單鏈表開刀，我們要完成兩個操作，插入數據和刪除數據。

如果我想插入數據，你可能會問，往哪裡插呢？有幾種插入的方法？

開始想，插入到單鏈表的頭部算一種。

然後插入到單鏈表的中間算一種。

插入到單鏈表尾部又算一種。

所有可能的情況就三種。那麼刪除呢？想必你也想到了，也一共三種，刪除頭部、刪除中間部分、刪除尾部。

如果你覺的現在可以寫程式碼了，那你就錯了，雖然我們的思路非常清晰，但是面試官僅僅考我們思路嗎？其實這一關你只打敗了百分之50%的人，最重點、最主要的是在下一個部分，邊界條件。

3

邊界條件

邊界條件是這五個步驟最容易犯錯的一部分，因為通常考慮的不全面，導致了最後的面試未通過。如果想做好這一部分，也不難，跟著小鹿的方法走。

3.1 輸入邊界

首先我們先考慮用戶輸入的參數，比如傳入一個鏈表，我們首先要判斷鏈表是否為空，如果為空我們就不能讓它執行下邊的程式。再比如插入一個結點到指定結點的後邊，那麼你也要判斷輸入的結點是否為空，而且還要判斷該結點是否存在該鏈表中。對於這些輸入值的判斷，小鹿給他同一起個名字叫做輸入邊界。

3.2 特殊邊界

特殊邊界考慮到一些特殊情況，比如插入數據，我們插入數據一般考慮到插入尾部，但是突然面試官插入到頭部，插入尾部的程式碼並不適用於插入到頭部，所以呢需要考慮這種情況，刪除節點也是同樣思考。其實特殊邊界最主要考慮到一些邏輯上的特殊情況，考察應聘者的考慮的是否全面。小鹿給他起個名字叫做特殊邊界。

4

手寫程式碼

4.1 定義結點

class Node{      constructor(data){          this.data = data;          this.next = null;      }  }

4.2 增加結點

咱們就以單鏈表中部添加數據為例子，分解成每個步驟，每個步驟對應程式碼如下：

1、保存臨時地址（4結點的地址）,需要進行遍歷查找到3結點，也就是下列程式碼的currentNode 結點。

//先查找該元素  let currentNode = this.findByValue(element);  // 保存 3 結點的下一結點地址（4 結點的地址）  let pre = currentNode.next  

2、創建新結點，將新結點（5結點）的指針指向下一結點指針（4結點地址，已經在上一步驟保存下來了）

let newNode = new Node(value);  newNode.next = pre;  

3、將3 的結點地址指向新結點（5結點）

 currentNode.next = newNode;  

以上步驟分析完畢，剩下的兩個在頭部插入和在尾部插入同樣的分析方式，將這兩個作為練習題，課下自己試一試這個步驟。

4.3 刪除節點

刪除節點也分為三種，頭部、中部、尾部，咱們就刪除中間結點為例進行刪除，我們詳細看步驟操作。

我們先看刪除的全部動畫，然後再分步拆分。

斷開3結點的指針（斷開3結點相當於讓2結點直接指向4結點）

 let currentNode = this.head;   // 用來記錄 3 結點的前一結點   let preNode = null;   // 遍歷查找 3 結點   while(currentNode !== null && currentNode.data !== value){          // 3 結點的前一結點          preNode = currentNode;          // 3 結點          currentNode = currentNode.next;  }

讓結點2的指針指向4結點，完成刪除。

preNode.next = currentNode.next;  

剩下的刪除頭結點和刪除尾結點同樣的步驟，自己動手嘗試下。

所有程式碼實現：

/**   * 2019/3/23   * 公眾號:「一個不甘平凡的碼農」   * @author 小鹿   * 功能：單鏈表的插入、刪除、查找   * 【插入】：插入到指定元素後方   * 1、查找該元素是否存在？   * 2、沒有找到返回 -1   * 3、找到進行創建結點並插入鏈表。   *   * 【查找】：按值查找/按索引查找   * 1、判斷當前結點是否等於null，且是否等於給定值？   * 2、判斷是否可以找到該值？   * 3、沒有找到返回 -1；   * 4、找到該值返回結點；   *   * 【刪除】：按值刪除   * 1、判斷是否找到該值？   * 2、找到記錄前結點，進行刪除；   * 3、找不到直接返回-1；   */  //定義結點  class Node{      constructor(data){          this.data = data;          this.next = null;      }  }    //定義鏈表  class LinkList{      constructor(){          //初始化頭結點          this.head = new Node('head');      }        //根據 value 查找結點      findByValue = (value) =>{          let currentNode = this.head;          while(currentNode !== null && currentNode.data !== value){              currentNode = currentNode.next;          }          //判斷該結點是否找到          console.log(currentNode)          return currentNode === null ? -1 : currentNode;      }        //根據 index 查找結點      findByIndex = (index) =>{          let pos = 0;          let currentNode = this.head;          while(currentNode !== null && pos !== index){              currentNode = currentNode.next;              pos++;          }          //判斷是否找到該索引          console.log(currentNode)          return currentNode === null ? -1 : currentNode;      }        //插入元素(指定元素向後插入)      insert = (value,element) =>{          //先查找該元素          let currentNode = this.findByValue(element);          //如果沒有找到          if(currentNode == -1){              console.log("未找到插入位置!")              return;          }          let newNode = new Node(value);          newNode.next = currentNode.next;          currentNode.next = newNode;      }        //根據值刪除結點      delete = (value) =>{          let currentNode = this.head;          let preNode = null;          while(currentNode !== null && currentNode.data !== value){              preNode = currentNode;              currentNode = currentNode.next;          }          if(currentNode == null) return -1;          preNode.next = currentNode.next;      }         //遍歷所有結點      print = () =>{          let currentNode = this.head          //如果結點不為空          while(currentNode !== null){              console.log(currentNode.data)              currentNode = currentNode.next;          }      }  }    //測試  const list = new LinkList()  list.insert('xiao','head');  list.insert('lu','xiao');  list.insert('ni','head');  list.insert('hellow','head');  list.print()  console.log('-------------刪除元素------------')  list.delete('ni')  list.delete('xiao')  list.print()  console.log('-------------按值查找------------')  list.findByValue('lu')  console.log('-------------按索引查找------------')  list.print()  

5

測試用例

其實這裡的測試用例主要用於判斷我們寫的程式到底對不對，我們一般都會輸入一個自己認為的情況進行測試，這是錯誤的做法。程式最容易出錯的還是邊界情況考慮不全面導致的，所以，我們為了能夠測試程式的全面性，所以我們要按照以下步驟進行全面性的測試。

5.1 普通測試

普通測試就是輸入一個正常的值，比如單鏈表中插入數據

5.2 特殊測試

特殊輸入可以參照上邊邊界條件中的特殊邊界進行測試，比如在頭部插入數據，在尾部插入數據等特殊情況的測試。

5.3 輸入測試

對於輸入測試的內容參考上邊邊界條件中的輸入邊界，比如：輸入一個空鏈表測試一下程式能否正常的運行。

6

小結

做一個小結。今天的手寫鏈表主要從五部分下手，從前到後依次為熟悉結構、理清思路、手寫程式碼、測試用例。以後無論手寫什麼程式碼，有五步走，對於面試完全沒有問題啦。