快捷導(dǎo)航

詳解Java線性結(jié)構(gòu)中的鏈表

更新時(shí)間：2023年07月07日 10:46:35 作者：一一哥Sun

除了一些算法之外，我們還有掌握一些常見的數(shù)據(jù)結(jié)構(gòu)，比如數(shù)組、鏈表、棧、隊(duì)列、樹等結(jié)構(gòu)，所以接下來就給大家詳細(xì)講解一下線性結(jié)構(gòu)中的鏈表,需要的朋友可以參考下

一. 鏈表簡介

1. 概念

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

所謂的鏈表，顧名思義，就是鏈?zhǔn)降木€性表，即鏈表也是一種線性表。與數(shù)組不同的是，鏈表采用的是鏈?zhǔn)酱鎯?，這種鏈?zhǔn)浇Y(jié)構(gòu)是非連續(xù)、非順序的內(nèi)存空間。鏈表中的每一個(gè)獨(dú)立的元素被稱為結(jié)點(diǎn)，故鏈表由一系列的結(jié)點(diǎn)組成。

其中鏈?zhǔn)酱鎯Φ暮x如下：

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

2. 表示方式

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

圖1-鏈表的結(jié)構(gòu)示意圖

上圖所示的節(jié)點(diǎn)細(xì)節(jié)如下：

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

3. 特點(diǎn)

通過上文所述，壹哥就可以給大家總結(jié)出鏈表的主要特點(diǎn)：

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

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

(3). 鏈表和數(shù)組相比，內(nèi)存空間消耗更大，因?yàn)槊總€(gè)存儲數(shù)據(jù)的結(jié)點(diǎn)都需要額外的空間存儲地址指針。

二. 鏈表分類

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

1. 單向鏈表

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

圖2-單向鏈表結(jié)構(gòu)示意圖

我們以Java為例，給出單向鏈表的結(jié)構(gòu)定義：

class Node{
    Object value;
    Node next;
}

2. 雙向鏈表

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

圖3-雙向鏈表結(jié)構(gòu)示意圖

如上圖所示：

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

使用Java進(jìn)行雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)定義如下：

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

3. 循環(huán)鏈表

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

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

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

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

三. 存儲原理

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

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

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

四. 鏈表常見操作

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

1. 查找結(jié)點(diǎn)

在查找元素時(shí)，鏈表只能從頭結(jié)點(diǎn)開始向后，一個(gè)結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)逐一查找，如下圖所示：

時(shí)間復(fù)雜度分析，分兩種情況：

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

2. 更新結(jié)點(diǎn)

更新結(jié)點(diǎn)操作需要兩個(gè)步驟：

找到要更新的結(jié)點(diǎn)；
將舊數(shù)據(jù)替換成新數(shù)據(jù)。

如下圖所示：

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

與查找結(jié)點(diǎn)操作時(shí)間復(fù)雜度情況類似，更新時(shí)間復(fù)雜度分兩種情況：

更新頭結(jié)點(diǎn)：單向鏈表更新頭結(jié)點(diǎn)的時(shí)間復(fù)雜度是O(1)；
更新非頭結(jié)點(diǎn)：更新其他結(jié)點(diǎn)的最壞情況時(shí)間復(fù)雜度是O(n)。

3. 插入結(jié)點(diǎn)

3.1 尾部插入

尾部插入即把最后一個(gè)結(jié)點(diǎn)的next指針指向新插入的結(jié)點(diǎn)即可，如下圖所示：

圖9-單向鏈表尾部插入結(jié)點(diǎn)示意圖

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

3.2 頭部插入

頭部插入新結(jié)點(diǎn)需要兩個(gè)步驟：

(1). 把新結(jié)點(diǎn)的next指針指向原先的頭結(jié)點(diǎn)；

(2). 把新結(jié)點(diǎn)變?yōu)殒湵淼念^結(jié)點(diǎn)。

如下圖所示：

圖10-單鏈表頭部插入結(jié)點(diǎn)示意圖

時(shí)間復(fù)雜度分析：因?yàn)橹苯訉⑿鹿?jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)即可完成操作，因此添加頭結(jié)點(diǎn)的時(shí)間復(fù)雜度是O(1)。

3.3 中間插入

在鏈表的中間位置插入結(jié)點(diǎn)同樣需要三步：

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

(2). 新結(jié)點(diǎn)的next指針指向插入位置的結(jié)點(diǎn)；

(3). 插入位置前置結(jié)點(diǎn)的next指針指向新結(jié)點(diǎn)；

示意圖如下：

圖11-單向鏈表中間位置插入結(jié)點(diǎn)

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

4. 刪除結(jié)點(diǎn)

4.1 尾部刪除

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

圖12-單向鏈表尾部刪除結(jié)點(diǎn)示意圖

時(shí)間復(fù)雜度分析：因?yàn)橐獜念^開始遍歷，所以單向鏈表刪除尾結(jié)點(diǎn)的時(shí)間復(fù)雜度是O(n)。

4.2 頭部刪除

頭部刪除與頭部插入操作類似，只需要把鏈表的頭結(jié)點(diǎn)設(shè)為原先頭結(jié)點(diǎn)的next指針即可如圖：

圖13-單向鏈表頭部刪除結(jié)點(diǎn)示意圖

時(shí)間復(fù)雜度分析：刪除頭結(jié)點(diǎn)的時(shí)間復(fù)雜度也是O(1)。

4.3 中間刪除

中間位置刪除結(jié)點(diǎn)操作類似于中間插入操作，需要三步：

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

(2). 找到刪除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)和后一個(gè)結(jié)點(diǎn)；

(3). 將要刪除結(jié)點(diǎn)的前置結(jié)點(diǎn)的next指針，指向要刪除元素的下一個(gè)結(jié)點(diǎn)；

如下所示：