面試官：請手寫一個簡易的單鏈表
我現在有點明白了，在面試過程中面試官有時會讓我們手寫代碼，其實主要是考驗大家的基本功，更是通過大眾都熟悉的領域來考核大家的體系化思維與應對思路。
而數據結構又是編程領域最基本知識，因為編程的世界中必須解決的問題：存儲。
接下來筆者會從自己角度，重新開始學習數據結構，并將學習到的內容與大家一起探討，交流，共同進步。
溫馨提示：本文主要以單鏈表表為例進行展開，因為單鏈表的反轉、檢測環都是常見面試題。
1、鏈表是什么?具備哪些基本特征?
面試官讓我們手寫一個鏈表，那我們首先快速梳理出鏈表的基本特征。
特意從百度百科上查詢了鏈表的定義：
鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點(鏈表中每一個元素稱為結點)組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。
基本特征如下：
- 物理存儲非連續、邏輯通過指針實現順序性,其示例圖如下所示：
- 數據結構分為指針域和數據域
面向對象編程，類不僅要定義屬性，還需要抽象出行為(方法)，思考如下：
通知在面試過程中，只需要基本實現增、刪、改、查即可。
2、圖解與代碼實現
鏈表的類圖如下：
鏈表的存儲結構如下圖所示：
接下來將從代碼角度來實現一個簡易的鏈表。
2.1 基礎代碼
鏈表的基礎數據如下所示：
- public class LinkedList<T> {
- /** 指針域*/
- // 頭節點
- private DataNode<T> header;
- // 從節點
- private DataNode<T> tail;
- private int size;
- /**
- * 數據節點
- * @param <T>
- */
- private class DataNode<T> {
- public T value;
- public DataNode<T> next;
- public DataNode(T value) {
- this.value = value;
- }
- }
- }
2.2 指定下標插入節點
上面主要是定義基本的數據結構，接下來我們看一下在鏈表的中間插入新的數據。
在指定下標處插入節點，該節點作為新節點的前驅節點，暫存它的next指針，謹防該指針會丟失，圖示如下：
代碼如下所示
- public void add(int index, T value) {
- if(index >= size) {
- throw new ArrayIndexOutOfBoundsException();
- }
- DataNode<T> node = new DataNode<>(value);
- DataNode<T> prev = get(index);
- DataNode<T> tmp = prev.next; // @1
- prev.next = node; // @2
- node.next = tmp; // @3
- }
鏈表的插入首先找到前驅節點，暫存它的next指針，謹防該指針會丟失，圖解如下圖所示：
上述三行代碼的說明如下：
- @1：首先創建一個臨時節點，用于暫存前驅節點的next
- @2：前驅節點的next指針重新指向待插入的節點
- @3：新節點的next指針指向原前驅節點的next指針
優化點：其實我們發現，前驅節點是要暫存，但是否真有必要開辟一個臨時節點，其實不需要，直接將其賦值給新節點的next即可。優化代碼如下：
- node.next = prev.next;
- prev.next = node;
2.3 移除指定下標處節點
移除指定下標處節點的示例圖：
正如上圖所示，要移除下標為2的節點，即圖中的第三個節點，核心關鍵點還是需要找到待刪除節點的前驅節點，然后前驅節點的next等于待刪除節點的next即可，故實現代碼如下：
- public T remove(int index) {
- if(index >= size) {
- throw new ArrayIndexOutOfBoundsException();
- }
- DataNode<T> pre = get(index - 1 );
- DataNode<T> cur = pre.next;
- pre.next = cur.next;
- // help GC
- cur.next = null;
- size --;
- return cur.value;
- }
2.4 單鏈表反轉
所謂的單鏈表反轉，就是將原鏈表逆序輸出結果，其示例圖如下：
單鏈表的反轉，需要做的事情是將當前節點的next指針指向前驅節點。
但由于單鏈表只有next指針，故從頭節點開始遍歷的過程中，遍歷指針前進到的當前節點時，需要能方便的訪問到該節點的前驅動。
另外一個核心點就是，在遍歷過程中，對當前節點的next指針進行操作(賦值為前驅節點)時必須暫存該節點的next指針，否則next指針丟失，無法遍歷到鏈表的結尾。
基于上述思路，鏈表反轉的具體操作流程如下圖所示：
基于上述思路，代碼編寫如下所示：
- public void reverse() {
- // 從頭節點開始遍歷
- DataNode<T> cur = header;
- // 記錄當前節點到 prev 前驅節點
- DataNode<T> cur_prev = null;
- // 暫存當前節點到next指針
- DataNode<T> cur_next = null;
- // 從當前節點開始遍歷，直接到尾部
- while(cur != null) {
- //反轉之前，先暫存相關節點
- cur_next = cur.next;
- cur.next = cur_prev;
- cur_prev = cur;
- // 繼續遍歷下一個節點
- cur = cur_next;
- }
- //反轉 header ,tail
- DataNode<T> tmp = header;
- header = tail;
- tail = tmp;
- }
鏈表的其他方法實現，基本差不多，從編寫代碼的過程中，不難看出鏈表的操作，主要是操作各個節點的指針。
3、常見面試題
3.1 鏈表與數組的區別
鏈表與數組的區別可以從如下幾個方面展開：
- 內存布局
- 插入性能
- 查找性能
3.1.1 內存布局
數組必須申請連續的內存，即物理上連續，例如當前jvm虛擬機當前還剩150M內存，但此時嘗試去創建一個100M內存，可能無法分配內存而觸發垃圾回收，而鏈表是邏輯連續，物理上不連續，因為時通過指針進行定位。
3.1.2 插入性能
鏈表在頭、尾節點插入性能極佳，如果需要在鏈表的隨機位置插入數據，需要先從頭節點開始遍歷，先找到相關待插入節點的前驅節點，后續的插入操作只需要涉及指針賦值，性能表現佳，而數組的插入由于需要涉及數據的復制、移動，從而帶來較大性能損耗。
3.1.3 查找性能
數組最大的優勢是隨機查找能力，其時間復雜度為O(1)，即數組可以根據下表快速定位到需要查詢到數據。而鏈表只能是從頭節點或尾節點開始遍歷。
本文轉載自微信公眾號「中間件興趣圈」，可以通過以下二維碼關注。轉載本文請聯系中間件興趣圈公眾號。
