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

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

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

一. 鏈表簡介

1. 概念

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

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

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

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

2. 表示方式

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

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

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

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

3. 特點

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

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

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

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

二. 鏈表分類

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

1. 單向鏈表

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

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

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

class Node{
    Object value;
    Node next;
}

2. 雙向鏈表

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

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

如上圖所示：

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

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

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

3. 循環(huán)鏈表

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

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

如上圖，每個結(jié)點有數(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)存存儲示意圖

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

四. 鏈表常見操作

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

1. 查找結(jié)點

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

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

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