首頁 > 軟體

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

2023-04-04 06:00:50

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資料結構之連結串列的概念及結構的文章就介紹到這了,更多相關Java 連結串列的概念結構內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com!


IT145.com E-mail:sddin#qq.com