一. 鏈表簡介

1. 概念

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

所謂的鏈表，顧名思義，就是鏈式的線性表，即鏈表也是一種線性表。與數(shù)組不同的是，鏈表采用的是鏈式存儲，這種鏈式結構是非連續(xù)、非順序的內(nèi)存空間。鏈表中的每一個獨立的元素被稱為結點，故鏈表由一系列的結點組成。

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

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

2. 表示方式

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

圖1-鏈表的結構示意圖

上圖所示的節(jié)點細節(jié)如下：

• 首個結點中next1存放的是第二結點的內(nèi)存地址，因此用一個箭頭指向第二個結點，就可以表示兩個結點之間的關系。
• 最后一個結點的后面不再有其他結點，因此最后結點的next5指針域中沒有地址內(nèi)容，編程中可以用null表示。

3. 特點

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

(1). 從內(nèi)存結構來看，鏈表的內(nèi)存結構是不連續(xù)的內(nèi)存空間，是將一組零散的內(nèi)存塊串聯(lián)起來，從而進行數(shù)據(jù)存儲的數(shù)據(jù)結構；

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

(3). 鏈表和數(shù)組相比，內(nèi)存空間消耗更大，因為每個存儲數(shù)據(jù)的結點都需要額外的空間存儲地址指針。

二. 鏈表分類

在工作實踐中，開發(fā)者接觸到的鏈表主要有三種：單向鏈表、雙向鏈表、循環(huán)鏈表。下面壹哥給大家逐一進行介紹一下。

1. 單向鏈表

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

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

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

class Node{
    Object value;
    Node next;
}

2. 雙向鏈表

雙向鏈表，表示鏈表結點由三部分組成：數(shù)據(jù)域、下一結點指針域、前一結點指針域。 在雙向鏈表結構中，既可以從首個結點出發(fā)，根據(jù)下一結點指針域依次找到所有結點；同理，也可以從指定的某個結點，根據(jù)結點中的前一結點指針地址，向前依次得到前面的結點。具體地，雙向鏈表的結構示意圖如下所示：

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

如上圖所示：

• 第1個結點作為整個鏈表的首結點，該結點的prev1指針內(nèi)容為null，表示沒有前一個結點。
• 第5個結點作為整個鏈表的最后結點，next5指針內(nèi)容為null，表示后續(xù)沒有下一個結點。
• 除此之外，中間三個結點，next指針和prev指針分別指向下一個結點和前一個結點，可以實現(xiàn)雙向查找。

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

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

3. 循環(huán)鏈表

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

圖4-單向循環(huán)鏈表示意圖

如上圖，每個結點有數(shù)據(jù)域和指針域兩個部分，這種循環(huán)鏈表被稱之為單向循環(huán)鏈表。在計算機領域中，單向循環(huán)鏈表又稱約瑟夫環(huán)（Josephu Loop），這一點僅做了解即可。當然，雙向鏈表也可以調(diào)整為循環(huán)的鏈表，被稱之為雙向循環(huán)鏈表，如下圖所示：

圖5-雙向循環(huán)鏈表示意圖

三. 存儲原理

數(shù)組在內(nèi)存中的存儲方式是順序存儲（連續(xù)存儲），鏈表在內(nèi)存中的存儲方式則是隨機存儲，如下圖所示：

圖6-鏈表的內(nèi)存存儲示意圖

鏈表的每一個結點分布在內(nèi)存的不同位置，依靠next指針關聯(lián)起來。這樣可以靈活有效地利用零散的碎片空間。鏈表的第一個結點被稱為頭結點，沒有任何結點的next指針指向它，它的前置結點為空null。頭結點用來記錄鏈表的基地址。有了它，就可以遍歷得到整條鏈表的數(shù)據(jù)。鏈表的最后一個結點被稱為尾結點，它的next指向為空null。

四. 鏈表常見操作

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

1. 查找結點

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

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

• 查找頭結點：頭結點是鏈表的第一個結點，直接就能得到結果，因此查找頭結點時間復雜度是O(1)。
• 查找非頭結點：如果查找非頭結點，則需要從頭結點向后依次查找，知道整個鏈表的末尾，因此查找非頭結點的其他結點時，時間復雜度是O(n)，最壞情況下時間復雜度也是O(n)。

2. 更新結點

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

• 找到要更新的結點；
• 將舊數(shù)據(jù)替換成新數(shù)據(jù)。

如下圖所示：

圖8-單向鏈表更新結點數(shù)據(jù)操作示意圖

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

• 更新頭結點：單向鏈表更新頭結點的時間復雜度是O(1)；
• 更新非頭結點：更新其他結點的最壞情況時間復雜度是O(n)。

3. 插入結點

3.1 尾部插入

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

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

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

3.2 頭部插入

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

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

(2). 把新結點變?yōu)殒湵淼念^結點。

如下圖所示：

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

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

3.3 中間插入

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

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

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

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

示意圖如下：

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

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

4. 刪除結點

4.1 尾部刪除

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

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

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

4.2 頭部刪除

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

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

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

4.3 中間刪除

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

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

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

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

如下所示：

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

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

五. 結語

本篇文章，我們一起學習了鏈表的概念，認識了單向鏈表、雙向鏈表、循環(huán)鏈表等不同的鏈表類型。并以單向鏈表為例，分析了鏈表中的結點炒作及對應的時間復雜度分析，不知道你現(xiàn)在對鏈表了解了嗎？

以上就是詳解Java線性結構中的鏈表的詳細內(nèi)容，更多關于Java 鏈表的資料請關注腳本之家其它相關文章！

最新評論