前言

除了一些演算法之外，我們還要掌握一些常見的數據結構，比如數組、鏈表、棧、隊列、樹等結構。 在之前的文章中，已經帶著大家學習了Java里的一維數組和多維數組，所以對此我就不再細述了。接下來我會給大家講解一下線性結構中的鏈表，希望你能喜歡哦。

全文大約【3200】 字，不說廢話，只講可以讓你學到技術、明白原理的純乾貨！本文帶有豐富的案例及配圖視頻，讓你更好地理解和運用文中的技術概念，並可以給你帶來具有足夠啟迪的思考...

一. 鏈表簡介

1. 概念

線性表可以說是一種最基礎最簡單的數據結構，它表示的是一種線性結構，比較常見的線性結構包括數組和鏈表等。

所謂的鏈表，顧名思義，就是鏈式的線性表，即鏈表也是一種線性表。與數組不同的是，鏈表採用的是鏈式存儲，這種鏈式結構是非連續、非順序的記憶體空間。鏈表中的每一個獨立的元素被稱為結點，故鏈表由一系列的結點組成。

其中鏈式存儲的含義如下：

假如我們需要存放一堆物品，但沒有足夠大的空間將所有的物品一次性放下，此時該如何既放下所有的物品，又能簡單的找到所有的物品位置呢？我們可以嘗試採用如下解決方案：存放物品時，每放置一件物品就在該物品上貼一個小紙條，標明下一件物品放在哪裡。這樣，我們只需要記住第一件物品的位置，從第一件物品上的小紙條，就可以找到第二件物品，再根據第二件物品紙條的內容就找到第三件物品。按照這個方法依次類推，我們便可以找到所有的物品，這就是所謂的鏈式存儲。

2. 表示方式

鏈表中的每個結點都由兩部分組成：數據域、指針域。數據域用來存放當前結點需要存儲的數據內容，指針域用於存放當前結點的下一個結點的地址。如下圖所示：

圖1-鏈表的結構示意圖

上圖所示的節點細節如下：

• 首個結點中next1存放的是第二結點的記憶體地址，因此用一個箭頭指向第二個結點，就可以表示兩個結點之間的關係。

• 最後一個結點的後面不再有其他結點，因此最後結點的next5指針域中沒有地址內容，編程中可以用null表示。

3. 特點

通過上文所述，就可以給大家總結出鏈表的主要特點：

(1). 從記憶體結構來看，鏈表的記憶體結構是不連續的記憶體空間，是將一組零散的記憶體塊串聯起來，從而進行數據存儲的數據結構；

(2). 鏈表由一系列結點組成，每個結點包括兩個部分，一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。鏈表中數據元素的邏輯順序就是通過地址指針實現的；

(3). 鏈表和數組相比，記憶體空間消耗更大，因為每個存儲數據的結點都需要額外的空間存儲地址指針。

二. 鏈表分類

在工作實踐中，開發者接觸到的鏈表主要有三種：單向鏈表、雙向鏈表、迴圈鏈表。下麵給大家逐一進行介紹一下。

1. 單向鏈表

單向鏈表的每一個結點包含兩部分，一部分是存放數據的變數data，另一部分是指向下一個結點的指針next。 單鏈表只能單向讀取，其結構如下所示：

圖2-單向鏈表結構示意圖

們以Java為例，給出單向鏈表的結構定義：

class Node{
	Object value;
    Node next;
}

2. 雙向鏈表

雙向鏈表，表示鏈表結點由三部分組成：數據域、下一結點指針域、前一結點指針域。

在雙向鏈表結構中，既可以從首個結點出發，根據下一結點指針域依次找到所有結點；同理，也可以從指定的某個結點，根據結點中的前一結點指針地址，向前依次得到前面的結點。具體地，雙向鏈表的結構示意圖如下所示：

圖3-雙向鏈表結構示意圖

如上圖所示：

• 第1個結點作為整個鏈表的首結點，該結點的prev1指針內容為null，表示沒有前一個結點。

• 第5個結點作為整個鏈表的最後結點，next5指針內容為null，表示後續沒有下一個結點。

• 除此之外，中間三個結點，next指針和prev指針分別指向下一個結點和前一個結點，可以實現雙向查找。

使用Java進行雙向鏈表的結點結構定義如下：

class Node{
    Object value;
    Node next;
    Node prev;
}

3. 迴圈鏈表

如果，我們將鏈表的最後結點的next指針域做下修改，由原來的指向null修改為指向第1個結點，則整個鏈表就變成了一個環路。以單向鏈表進行操作，如下圖所示：

圖4-單向迴圈鏈表示意圖

如上圖，每個結點有數據域和指針域兩個部分，這種迴圈鏈表被稱之為單向迴圈鏈表。在電腦領域中，單向迴圈鏈表又稱約瑟夫環（Josephu Loop），這一點僅做瞭解即可。當然，雙向鏈表也可以調整為迴圈的鏈表，被稱之為雙向迴圈鏈表，如下圖所示：

圖5-雙向迴圈鏈表示意圖

三. 存儲原理

數組在記憶體中的存儲方式是順序存儲（連續存儲），鏈表在記憶體中的存儲方式則是隨機存儲，如下圖所示：

圖6-鏈表的記憶體存儲示意圖

鏈表的每一個結點分佈在記憶體的不同位置，依靠next指針關聯起來。這樣可以靈活有效地利用零散的碎片空間。鏈表的第一個結點被稱為頭結點，沒有任何結點的next指針指向它，它的前置結點為空null。頭結點用來記錄鏈表的基地址。有了它，就可以遍歷得到整條鏈表的數據。鏈表的最後一個結點被稱為尾結點，它的next指向為空null。

四. 鏈表常見操作

本篇文章內容，我們以單向鏈表為例，介紹鏈表的常見操作，主要包括：查找結點、更新結點、插入結點和刪除結點等操作。

1. 查找結點

在查找元素時，鏈表只能從頭結點開始向後，一個結點一個結點逐一查找，如下圖所示：

圖7-單向鏈表查找結點示意圖

時間複雜度分析，分兩種情況：

• 查找頭結點：頭結點是鏈表的第一個結點，直接就能得到結果，因此查找頭結點時間複雜度是O(1)。

• 查找非頭結點：如果查找非頭結點，則需要從頭結點向後依次查找，知道整個鏈表的末尾，因此查找非頭結點的其他結點時，時間複雜度是O(n)，最壞情況下時間複雜度也是O(n)。

2. 更新結點

更新結點操作需要兩個步驟：

• 找到要更新的結點；

• 將舊數據替換成新數據。

如下圖所示：

圖8-單向鏈表更新結點數據操作示意圖

與查找結點操作時間複雜度情況類似，更新時間複雜度分兩種情況：

• 更新頭結點：單向鏈表更新頭結點的時間複雜度是O(1)；

• 更新非頭結點：更新其他結點的最壞情況時間複雜度是O(n)。

3. 插入結點

3.1 尾部插入

尾部插入即把最後一個結點的next指針指向新插入的結點即可，如下圖所示：

圖9-單向鏈表尾部插入結點示意圖

時間複雜度分析：如上圖所示，若尾部插入結點，則需要從頭開始遍歷，因此單向鏈表添加尾結點的時間複雜度是O(n)。

3.2 頭部插入

頭部插入新結點需要兩個步驟：

(1). 把新結點的next指針指向原先的頭結點；

(2). 把新結點變為鏈表的頭結點。

如下圖所示：

圖10-單鏈表頭部插入結點示意圖

時間複雜度分析：因為直接將新節點的指針域指向頭結點即可完成操作，因此添加頭結點的時間複雜度是O(1)。

3.3 中間插入

在鏈表的中間位置插入結點同樣需要三步：

(1). 從頭結點開始向後查找，找到要插入的結點的位置；

(2). 新結點的next指針指向插入位置的結點；

(3). 插入位置前置結點的next指針指向新結點；

示意圖如下：

圖11-單向鏈表中間位置插入結點

時間複雜度分析： 若執行插入結點操作，首先需要從頭結點向後查找，找到要插入的位置。很明顯，與鏈表的規模有關，因此中間插入結點操作的時間複雜度是O(n)。

4. 刪除結點

4.1 尾部刪除

若希望刪除鏈表的最後一個結點，只需要將倒數第二個結點的指針域指向null即可，如下圖所示：

圖12-單向鏈表尾部刪除結點示意圖

時間複雜度分析： 因為要從頭開始遍歷，所以單向鏈表刪除尾結點的時間複雜度是O(n)。

4.2 頭部刪除

頭部刪除與頭部插入操作類似，只需要把鏈表的頭結點設為原先頭結點的next指針即可如圖：

圖13-單向鏈表頭部刪除結點示意圖

時間複雜度分析： 刪除頭結點的時間複雜度也是O(1)。

4.3 中間刪除

中間位置刪除結點操作類似於中間插入操作，需要三步：

(1). 從頭結點開始向後，找到要刪除結點的位置；

(2). 找到刪除結點的前一個結點和後一個結點；

(3). 將要刪除結點的前置結點的next指針，指向要刪除元素的下一個結點；

如下所示：

圖14-單向鏈表中間刪除結點示意圖

時間複雜度分析： 因為需要從頭結點開始進行查找，因此時間複雜度與鏈表的規模有關，故單向鏈表刪除中間位置結點的時間複雜度是O(n)。

五. 結語

本篇文章，我們一起學習了鏈表的概念，認識了單向鏈表、雙向鏈表、迴圈鏈表等不同的鏈表類型。並以單向鏈表為例，分析了鏈表中的結點炒作及對應的時間複雜度分析，不知道你現在對鏈表瞭解了嗎？