我現(xià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é)點(鏈表中每一個元素稱為結(jié)點)組成，結(jié)點可以在運行時動態(tài)生成。每個結(jié)點包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點地址的指針域。

基本特征如下：

• 物理存儲非連續(xù)、邏輯通過指針實現(xiàn)順序性,其示例圖如下所示：



• 數(shù)據(jù)結(jié)構(gòu)分為指針域和數(shù)據(jù)域

面向?qū)ο缶幊?，類不僅要定義屬性，還需要抽象出行為(方法)，思考如下：

通知在面試過程中，只需要基本實現(xiàn)增、刪、改、查即可。

2、圖解與代碼實現(xiàn)

鏈表的類圖如下：

鏈表的存儲結(jié)構(gòu)如下圖所示：

接下來將從代碼角度來實現(xiàn)一個簡易的鏈表。

2.1 基礎(chǔ)代碼

鏈表的基礎(chǔ)數(shù)據(jù)如下所示：

public class LinkedList<T> { 
 
    /** 指針域*/ 
    // 頭節(jié)點 
    private DataNode<T> header; 
    // 從節(jié)點 
    private DataNode<T> tail; 
 
    private int size; 
 
 
    /** 
     * 數(shù)據(jù)節(jié)點 
     * @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é)點

上面主要是定義基本的數(shù)據(jù)結(jié)構(gòu)，接下來我們看一下在鏈表的中間插入新的數(shù)據(jù)。

在指定下標(biāo)處插入節(jié)點，該節(jié)點作為新節(jié)點的前驅(qū)節(jié)點，暫存它的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é)點，暫存它的next指針，謹(jǐn)防該指針會丟失，圖解如下圖所示：

上述三行代碼的說明如下：

• @1：首先創(chuàng)建一個臨時節(jié)點，用于暫存前驅(qū)節(jié)點的next
• @2：前驅(qū)節(jié)點的next指針重新指向待插入的節(jié)點
• @3：新節(jié)點的next指針指向原前驅(qū)節(jié)點的next指針

優(yōu)化點：其實我們發(fā)現(xiàn)，前驅(qū)節(jié)點是要暫存，但是否真有必要開辟一個臨時節(jié)點，其實不需要，直接將其賦值給新節(jié)點的next即可。優(yōu)化代碼如下：

node.next = prev.next; 
prev.next = node; 

2.3 移除指定下標(biāo)處節(jié)點

移除指定下標(biāo)處節(jié)點的示例圖：

正如上圖所示，要移除下標(biāo)為2的節(jié)點，即圖中的第三個節(jié)點，核心關(guān)鍵點還是需要找到待刪除節(jié)點的前驅(qū)節(jié)點，然后前驅(qū)節(jié)點的next等于待刪除節(jié)點的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é)點的next指針指向前驅(qū)節(jié)點。

但由于單鏈表只有next指針，故從頭節(jié)點開始遍歷的過程中，遍歷指針前進(jìn)到的當(dāng)前節(jié)點時，需要能方便的訪問到該節(jié)點的前驅(qū)動。

另外一個核心點就是，在遍歷過程中，對當(dāng)前節(jié)點的next指針進(jìn)行操作(賦值為前驅(qū)節(jié)點)時必須暫存該節(jié)點的next指針，否則next指針丟失，無法遍歷到鏈表的結(jié)尾。

基于上述思路，鏈表反轉(zhuǎn)的具體操作流程如下圖所示：

基于上述思路，代碼編寫如下所示：

public void reverse() { 
        // 從頭節(jié)點開始遍歷 
        DataNode<T> cur = header; 
        // 記錄當(dāng)前節(jié)點到 prev 前驅(qū)節(jié)點 
        DataNode<T> cur_prev = null; 
        // 暫存當(dāng)前節(jié)點到next指針 
        DataNode<T> cur_next = null; 
 
        // 從當(dāng)前節(jié)點開始遍歷，直接到尾部 
        while(cur != null) { 
            //反轉(zhuǎn)之前，先暫存相關(guān)節(jié)點 
            cur_next = cur.next; 
            cur.next = cur_prev; 
            cur_prev = cur; 
            // 繼續(xù)遍歷下一個節(jié)點 
            cur = cur_next; 
        } 
         
        //反轉(zhuǎn) header ,tail 
        DataNode<T> tmp = header; 
        header = tail; 
        tail = tmp; 
    } 

鏈表的其他方法實現(xiàn)，基本差不多，從編寫代碼的過程中，不難看出鏈表的操作，主要是操作各個節(jié)點的指針。

3、常見面試題

3.1 鏈表與數(shù)組的區(qū)別

鏈表與數(shù)組的區(qū)別可以從如下幾個方面展開：

• 內(nèi)存布局
• 插入性能
• 查找性能

3.1.1 內(nèi)存布局

數(shù)組必須申請連續(xù)的內(nèi)存，即物理上連續(xù)，例如當(dāng)前jvm虛擬機當(dāng)前還剩150M內(nèi)存，但此時嘗試去創(chuàng)建一個100M內(nèi)存，可能無法分配內(nèi)存而觸發(fā)垃圾回收，而鏈表是邏輯連續(xù)，物理上不連續(xù)，因為時通過指針進(jìn)行定位。

3.1.2 插入性能

鏈表在頭、尾節(jié)點插入性能極佳，如果需要在鏈表的隨機位置插入數(shù)據(jù)，需要先從頭節(jié)點開始遍歷，先找到相關(guān)待插入節(jié)點的前驅(qū)節(jié)點，后續(xù)的插入操作只需要涉及指針賦值，性能表現(xiàn)佳，而數(shù)組的插入由于需要涉及數(shù)據(jù)的復(fù)制、移動，從而帶來較大性能損耗。

3.1.3 查找性能

數(shù)組最大的優(yōu)勢是隨機查找能力，其時間復(fù)雜度為O(1)，即數(shù)組可以根據(jù)下表快速定位到需要查詢到數(shù)據(jù)。而鏈表只能是從頭節(jié)點或尾節(jié)點開始遍歷。

本文轉(zhuǎn)載自微信公眾號「中間件興趣圈」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系中間件興趣圈公眾號。