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