Java資料結構之連結串列的概念及結構

2023-04-04 06:00:50

1、連結串列的概念

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

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

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

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

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

連結串列由一個個結點構成，每個結點採用結構體的形式。結構體內前面的變數按照需要給予，最後一個變數是這個結構體型別的指標，用來存放下一節點的首地址‘

連結串列結點分為兩個域
資料域：存放各種實際的資料
指標域：存放下一結點的地址

（圖為帶哨兵位頭結點的連結串列）

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

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

雖然組合起來一共有8種連結串列可以選擇，但是實際中最常用的主要還是 無頭單向非迴圈 連結串列和 帶頭雙向迴圈 連結串列。

1、無頭單向非迴圈連結串列：俗稱 “單連結串列”。結構簡單，一般不會單獨用來儲存資料。實際上更多是作為其他資料結構的子結構（如雜湊桶、圖的鄰接表、棧的鏈式結構等）

2、帶頭雙向迴圈連結串列：結構最複雜，一般用來單獨儲存資料。實際使用的連結串列，大多都是帶頭雙向迴圈連結串列。雖然結構最複雜，但是這種結構會帶來很多優勢。

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

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

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

順序表的每個成員對應連結串列的結點；成員和結點的資料型別可以是標準的c型別或者是使用者自定義的結構體型別。

到此這篇關於Java資料結構之連結串列的概念及結構的文章就介紹到這了,更多相關Java 連結串列的概念結構內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！