Java資料結構之鍊錶的概念及結構是什麼

1、 鍊錶的概念

概念：鍊錶是一種物理儲存結構上非連續、非順序的儲存結構，資料元素的邏輯順序是透過鍊錶中的指標連結順序來實現的

1、鍊錶由一系列結點（鍊錶中每一個元素稱為結點）所組成。

2、結點可以在運行時動態(malloc)產生。

3、每個結點包含兩個部分：一個是儲存資料元素的資料域，另一個是儲存下一個結點位址的指標域（詳見1.2 節點部分）。

4、相較於線性表順序結構，鍊錶操作複雜。但是由於不需要按順序存儲，鍊錶在插入的時候可以達到O(1)的複雜度，比順序表快得多；但是查找一個節點或訪問特定編號的節點則需要O(n)的時間，而順序表只需O(1)

2、 結點

鍊錶由一個個結點構成，每個結點採用結構體的形式。結構體內前面的變數依需求給予，最後一個變數是這個結構體類型的指針，用來存放下一節點的首位址‘

鍊錶結點分成兩個域
資料域：存放各種實際的資料
指標域 ：存放下一結點的位址

#（圖為具有哨兵位頭結點的鍊錶）

3、 鍊錶的使用情境

線性表在 需要經常插入或刪除資料元素 的情況下適合採用鍊式儲存結構。

因為對於鍊錶來說，插入或刪除資料只需要建立一個結點、輸入資料、修改指標把該結點連接到鍊錶中的某一位置即可； 而對於順序表，插入一個數據可能需要搬移其他數據，複雜度高。

4、 鍊錶分類和常用的結構

#雖然組合起來一共有8種鍊錶可以選擇，但是實際中最常用的主要還是 無頭單向非循環 鍊錶和 帶頭雙向循環 鍊錶。

1、無頭單向非循環鍊錶：俗稱 「單鍊錶」。結構簡單，一般不會單獨用來儲存資料。實際上更多是作為其他資料結構的子結構（如哈希桶、圖的鄰接表、棧的鍊式結構等）

2、帶頭雙向循環鍊錶：結構最複雜，一般用來單獨儲存資料。實際使用的鍊錶，大多都是帶頭雙向循環鍊錶。雖然結構最複雜，但是這種結構會帶來許多優勢。

5、 與順序表的比較

鍊錶： 鍊錶是透過結點把離散的資料連結成一個表，透過對結點的插入、刪除操作從而實現對資料的存取。

順序表： 順序表是透過開啟一段連續的記憶體（直接使用 陣列 或 malloc後realloc擴容）來儲存資料。

但是由於 realloc 擴容分為原地擴容和異地擴容，前者代價較低，而後者擴容時不僅需要拷貝數據，還要釋放舊空間。再者，擴容時一般會擴到原來容量的2倍，擴容次數多了就容易造成空間的浪費

順序表的每個成員對應鍊錶的結點；成員和結點的資料類型可以是標準的c類型或是使用者自訂的結構體類型。

#儲存空間連續不連續#插入或刪除資料

物件	順序表	鍊錶

###可能要搬移數據，複雜度O (n)######只需修改指標############push#######動態順序表：空間不夠了需要擴容#######沒有「容量」的概念，push時直接malloc新的結點############應用#######需要頻繁存取######需要頻繁插入、刪除資料#### ########

以上是Java資料結構之鍊錶的概念及結構是什麼的詳細內容。更多資訊請關注PHP中文網其他相關文章！