Java數據結構之鏈表的概念及結構是什么

今天小編給大家分享一下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類型或者是用戶自定義的結構體類型。

以上就是“Java數據結構之鏈表的概念及結構是什么”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。