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數據結構之鏈表的概念及結構的文章就介紹到這瞭,更多相關Java 鏈表的概念結構內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！