我現(xiàn)在有點(diǎn)明白了，在面試過程中面試官有時(shí)會(huì)讓我們手寫代碼，其實(shí)主要是考驗(yàn)大家的基本功，更是通過大眾都熟悉的領(lǐng)域來考核大家的體系化思維與應(yīng)對(duì)思路。

而數(shù)據(jù)結(jié)構(gòu)又是編程領(lǐng)域最基本知識(shí)，因?yàn)榫幊痰氖澜缰斜仨毥鉀Q的問題：存儲(chǔ)。

接下來筆者會(huì)從自己角度，重新開始學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，并將學(xué)習(xí)到的內(nèi)容與大家一起探討，交流，共同進(jìn)步。

溫馨提示：本文主要以單鏈表表為例進(jìn)行展開，因?yàn)閱捂湵淼姆崔D(zhuǎn)、檢測(cè)環(huán)都是常見面試題。

1、鏈表是什么?具備哪些基本特征?

面試官讓我們手寫一個(gè)鏈表，那我們首先快速梳理出鏈表的基本特征。

特意從百度百科上查詢了鏈表的定義：

鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)(鏈表中每一個(gè)元素稱為結(jié)點(diǎn))組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。

基本特征如下：

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



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

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

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

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

鏈表的類圖如下：

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

接下來將從代碼角度來實(shí)現(xiàn)一個(gè)簡(jiǎ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)防該指針會(huì)丟失，圖示如下：

代碼如下所示

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)防該指針會(huì)丟失，圖解如下圖所示：

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

• @1：首先創(chuàng)建一個(gè)臨時(shí)節(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)：其實(shí)我們發(fā)現(xiàn)，前驅(qū)節(jié)點(diǎn)是要暫存，但是否真有必要開辟一個(gè)臨時(shí)節(jié)點(diǎn)，其實(shí)不需要，直接將其賦值給新節(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)，即圖中的第三個(gè)節(jié)點(diǎn)，核心關(guān)鍵點(diǎn)還是需要找到待刪除節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，然后前驅(qū)節(jié)點(diǎn)的next等于待刪除節(jié)點(diǎn)的next即可，故實(shí)現(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)時(shí)，需要能方便的訪問到該節(jié)點(diǎn)的前驅(qū)動(dòng)。

另外一個(gè)核心點(diǎn)就是，在遍歷過程中，對(duì)當(dāng)前節(jié)點(diǎn)的next指針進(jìn)行操作(賦值為前驅(qū)節(jié)點(diǎn))時(shí)必須暫存該節(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ù)遍歷下一個(gè)節(jié)點(diǎn) 
            cur = cur_next; 
        } 
         
        //反轉(zhuǎn) header ,tail 
        DataNode<T> tmp = header; 
        header = tail; 
        tail = tmp; 
    } 

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

3、常見面試題

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

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

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

3.1.1 內(nèi)存布局

數(shù)組必須申請(qǐng)連續(xù)的內(nèi)存，即物理上連續(xù)，例如當(dāng)前jvm虛擬機(jī)當(dāng)前還剩150M內(nèi)存，但此時(shí)嘗試去創(chuàng)建一個(gè)100M內(nèi)存，可能無法分配內(nèi)存而觸發(fā)垃圾回收，而鏈表是邏輯連續(xù)，物理上不連續(xù)，因?yàn)闀r(shí)通過指針進(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ù)制、移動(dòng)，從而帶來較大性能損耗。

3.1.3 查找性能

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

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