什么是鏈表數(shù)據(jù)結(jié)構(gòu)？
鏈表是線性表的一種，但是在存儲上和線性表結(jié)構(gòu)的數(shù)組有很大的差異，數(shù)組的存儲在內(nèi)存上是一塊連續(xù)的空間，鏈表卻可以理由分散空間進行存儲，因此，當內(nèi)存大小不夠，或者內(nèi)存碎片過多，而此時又需要為一個長度很大數(shù)組分配空間，可能就會出現(xiàn)內(nèi)存不夠，觸發(fā)jvm提起回收內(nèi)存的情況，甚至拋出OutOfMemoryError異常。但是鏈表就不用擔心這一點，因為無需向數(shù)組一樣，提前開辟好一塊內(nèi)存連續(xù)的空間。鏈表的長度時增加，占用的內(nèi)存可以充分利用內(nèi)存碎片來完成。
鏈表數(shù)據(jù)結(jié)構(gòu)的核心就是下面這樣的，包含一個保存實際數(shù)值的val，還有指向上一個、下一個鏈表節(jié)點的引用或者是指針（java為引用，c為指針），這里描述的是雙鏈表的基礎(chǔ)節(jié)點數(shù)據(jù)結(jié)構(gòu)。
public class ListNode {
int val;
ListNode next;
ListNode pre;
ListNode(int x) { val = x; }
}
鏈表的種類
1.單向鏈表
對于普通單鏈表的隨機訪問時間復(fù)雜度為O(n)，因為需要從鏈表頭依次順序查找，但是對于鏈表結(jié)構(gòu)添加和刪除節(jié)點的時間復(fù)雜度都是O(1)不需要像數(shù)組一樣進行數(shù)據(jù)遷移，不過查找插入和刪除位置還要單獨計算時間復(fù)雜度。插入和刪除節(jié)點其實就是先通過查詢找到需要進行操作的位置，然后修改節(jié)點的next連接就可以了。被刪除的節(jié)點如果是C或者是C＋＋需要進行資源回收，如果是java，因為已經(jīng)沒有其他地方引用，GC會自動回收資源。
2.循環(huán)鏈表
循環(huán)鏈表是一種特殊的單鏈表，實際上循環(huán)鏈表也非常簡單，他和單鏈表的唯一區(qū)別就是在尾節(jié)點，單鏈表的尾節(jié)點指向null，表示鏈表結(jié)束，循環(huán)鏈表的尾是指向鏈表頭節(jié)點。
3.雙向鏈表
我們常見的單向鏈表因為是一個方向的鏈接，這就導致無法直接查找前繼節(jié)點，需要從頭節(jié)點遍歷才行，單向鏈表查找前繼節(jié)點的時間復(fù)雜度是O(n)。如果我們在一些場景頻繁需要查找前繼節(jié)點那么就可以使用雙向鏈表，雙向鏈表和單向鏈表的區(qū)別就在于在節(jié)點結(jié)構(gòu)里多了一個前繼節(jié)點引用或指針，在維護鏈表的時候也要多維護一個前繼指針的關(guān)系。所以同樣的數(shù)據(jù)，雙向鏈表需要的空間要多出O(n)，但是雙向鏈表查找前繼節(jié)點的時間復(fù)雜度降到了O(1)。
特點介紹
1.內(nèi)存中地址非連續(xù)，
2.長度可以實時變化
3.不支持隨機查找 查找元素時間復(fù)雜度O（n）
4.適用于需要進行大量增添/刪除元素操作，而對訪問元素無要求的程序
Java中的鏈表數(shù)據(jù)結(jié)構(gòu)
1.LinkedList
LinkedList是基于雙向鏈表實現(xiàn)的，不論是增刪改查方法還是隊列和棧的實現(xiàn)，都可通過操作結(jié)點實現(xiàn)。
LinkedList根據(jù)index查詢時采取的是二分法，即index小于總長度一半時從鏈表頭開始往后查找，大于總長度一半時從鏈表尾往前查找。如果是根據(jù)元素查找，則需要從頭開始遍歷。
2.HashMap，ConcurrentHashMap
采用拉鏈法解決哈希沖突，拉鏈法是一種開放散列的解決哈希沖突的形式。所謂 “拉鏈法” 就是：將鏈表和數(shù)組相結(jié)合。也就是說創(chuàng)建一個鏈表數(shù)組，數(shù)組中每一格就是一個鏈表。若遇到哈希沖突，則將沖突的值加到鏈表中即可。
相比于之前的版本，jdk1.8在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為8）時，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時間。
tips：封閉散列解決哈希沖突有：開放定址法，再哈希法等。
3.LinkedHashMap
通過維護一個運行于所有條目的雙向鏈表，LinkedHashMap保證了元素迭代的順序。該迭代順序可以是插入順序或者是訪問順序。
LinkedHashMap可以認為是HashMap+LinkedList，即它既使用HashMap操作數(shù)據(jù)結(jié)構(gòu)，又使用LinkedList維護插入元素的先后順序。
總結(jié)
對于通過下標隨機讀取非常多、插入和刪除數(shù)據(jù)是從末尾操作的場景適合用數(shù)組，對于隨機讀較少、插入和刪除操作較多的場景適合用鏈表，對于需要頻繁查找前繼和后繼節(jié)點的場景適合用雙向鏈表，對于資源可以循環(huán)利用的可以使用循環(huán)鏈表。
通過單向鏈表和雙向鏈表的介紹，還需要明白可以通過定義數(shù)據(jù)結(jié)構(gòu)用空間換時間的設(shè)計思想。當內(nèi)存空間充足的時候，如果追求代碼執(zhí)行效率，可以選擇空間復(fù)雜度更高的數(shù)據(jù)結(jié)構(gòu)或算法來提高執(zhí)行效率。
拓展
java中的List集合最常見的有ArrayList，和LinkedList，ArraysList 實現(xiàn)了 RandomAccess 接口， 而 LinkedList 沒有實現(xiàn)。為什么呢？
ArraysList 底層是數(shù)組，而 LinkedList 底層是鏈表。數(shù)組天然支持隨機訪問，時間復(fù)雜度為 O（1），所以稱為快速隨機訪問。
鏈表需要遍歷到特定位置才能訪問特定位置的元素，時間復(fù)雜度為 O（n），所以不支持快速隨機訪問。
ArraysList 實現(xiàn)了 RandomAccess 接口，就表明了他具有快速隨機訪問功能。 RandomAccess 接口只是標識，并不是說 ArraysList 實現(xiàn) RandomAccess 接口才具有快速隨機訪問功能的！
下面再總結(jié)一下 list 的遍歷方式選擇：
實現(xiàn)了RandomAccess接口的ArrayList，優(yōu)先選擇普通for循環(huán) ，其次foreach,
未實現(xiàn)RandomAccess接口的LinkedList， 優(yōu)先選擇iterator遍歷（foreach遍歷底層也是通過iterator實現(xiàn)的）。
ps：大size的數(shù)據(jù)，千萬不要使用普通for循環(huán)
