什么是鏈表數(shù)據(jù)結(jié)構(gòu)怠惶？
鏈表是線性表的一種耀态，但是在存儲(chǔ)上和線性表結(jié)構(gòu)的數(shù)組有很大的差異轮傍，數(shù)組的存儲(chǔ)在內(nèi)存上是一塊連續(xù)的空間，鏈表卻可以理由分散空間進(jìn)行存儲(chǔ)首装，因此创夜，當(dāng)內(nèi)存大小不夠，或者內(nèi)存碎片過(guò)多仙逻，而此時(shí)又需要為一個(gè)長(zhǎng)度很大數(shù)組分配空間驰吓，可能就會(huì)出現(xiàn)內(nèi)存不夠，觸發(fā)jvm提起回收內(nèi)存的情況系奉，甚至拋出OutOfMemoryError異常檬贰。但是鏈表就不用擔(dān)心這一點(diǎn)，因?yàn)闊o(wú)需向數(shù)組一樣缺亮，提前開辟好一塊內(nèi)存連續(xù)的空間翁涤。鏈表的長(zhǎng)度時(shí)增加，占用的內(nèi)存可以充分利用內(nèi)存碎片來(lái)完成萌踱。
鏈表數(shù)據(jù)結(jié)構(gòu)的核心就是下面這樣的葵礼，包含一個(gè)保存實(shí)際數(shù)值的val，還有指向上一個(gè)并鸵、下一個(gè)鏈表節(jié)點(diǎn)的引用或者是指針（java為引用鸳粉，c為指針），這里描述的是雙鏈表的基礎(chǔ)節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)能真。
public class ListNode {
int val;
ListNode next;
ListNode pre;
ListNode(int x) { val = x; }
}
鏈表的種類
1.單向鏈表
對(duì)于普通單鏈表的隨機(jī)訪問時(shí)間復(fù)雜度為O(n)赁严，因?yàn)樾枰獜逆湵眍^依次順序查找扰柠，但是對(duì)于鏈表結(jié)構(gòu)添加和刪除節(jié)點(diǎn)的時(shí)間復(fù)雜度都是O(1)不需要像數(shù)組一樣進(jìn)行數(shù)據(jù)遷移，不過(guò)查找插入和刪除位置還要單獨(dú)計(jì)算時(shí)間復(fù)雜度疼约。插入和刪除節(jié)點(diǎn)其實(shí)就是先通過(guò)查詢找到需要進(jìn)行操作的位置卤档，然后修改節(jié)點(diǎn)的next連接就可以了。被刪除的節(jié)點(diǎn)如果是C或者是C＋＋需要進(jìn)行資源回收程剥，如果是java劝枣，因?yàn)橐呀?jīng)沒有其他地方引用，GC會(huì)自動(dòng)回收資源织鲸。
2.循環(huán)鏈表
循環(huán)鏈表是一種特殊的單鏈表舔腾，實(shí)際上循環(huán)鏈表也非常簡(jiǎn)單，他和單鏈表的唯一區(qū)別就是在尾節(jié)點(diǎn)搂擦，單鏈表的尾節(jié)點(diǎn)指向null稳诚，表示鏈表結(jié)束，循環(huán)鏈表的尾是指向鏈表頭節(jié)點(diǎn)瀑踢。
3.雙向鏈表
我們常見的單向鏈表因?yàn)槭且粋€(gè)方向的鏈接扳还，這就導(dǎo)致無(wú)法直接查找前繼節(jié)點(diǎn)，需要從頭節(jié)點(diǎn)遍歷才行橱夭，單向鏈表查找前繼節(jié)點(diǎn)的時(shí)間復(fù)雜度是O(n)氨距。如果我們?cè)谝恍﹫?chǎng)景頻繁需要查找前繼節(jié)點(diǎn)那么就可以使用雙向鏈表，雙向鏈表和單向鏈表的區(qū)別就在于在節(jié)點(diǎn)結(jié)構(gòu)里多了一個(gè)前繼節(jié)點(diǎn)引用或指針棘劣，在維護(hù)鏈表的時(shí)候也要多維護(hù)一個(gè)前繼指針的關(guān)系俏让。所以同樣的數(shù)據(jù)，雙向鏈表需要的空間要多出O(n)茬暇，但是雙向鏈表查找前繼節(jié)點(diǎn)的時(shí)間復(fù)雜度降到了O(1)首昔。
特點(diǎn)介紹
1.內(nèi)存中地址非連續(xù)，
2.長(zhǎng)度可以實(shí)時(shí)變化
3.不支持隨機(jī)查找 查找元素時(shí)間復(fù)雜度O（n）
4.適用于需要進(jìn)行大量增添/刪除元素操作而钞，而對(duì)訪問元素?zé)o要求的程序
Java中的鏈表數(shù)據(jù)結(jié)構(gòu)
1.LinkedList
LinkedList是基于雙向鏈表實(shí)現(xiàn)的沙廉，不論是增刪改查方法還是隊(duì)列和棧的實(shí)現(xiàn)拘荡，都可通過(guò)操作結(jié)點(diǎn)實(shí)現(xiàn)臼节。
LinkedList根據(jù)index查詢時(shí)采取的是二分法，即index小于總長(zhǎng)度一半時(shí)從鏈表頭開始往后查找珊皿，大于總長(zhǎng)度一半時(shí)從鏈表尾往前查找网缝。如果是根據(jù)元素查找，則需要從頭開始遍歷蟋定。
2.HashMap粉臊，ConcurrentHashMap
采用拉鏈法解決哈希沖突，拉鏈法是一種開放散列的解決哈希沖突的形式驶兜。所謂 “拉鏈法” 就是：將鏈表和數(shù)組相結(jié)合扼仲。也就是說(shuō)創(chuàng)建一個(gè)鏈表數(shù)組远寸，數(shù)組中每一格就是一個(gè)鏈表。若遇到哈希沖突屠凶，則將沖突的值加到鏈表中即可驰后。
相比于之前的版本，jdk1.8在解決哈希沖突時(shí)有了較大的變化矗愧，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為8）時(shí)灶芝，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時(shí)間唉韭。
tips：封閉散列解決哈希沖突有：開放定址法夜涕，再哈希法等。
3.LinkedHashMap
通過(guò)維護(hù)一個(gè)運(yùn)行于所有條目的雙向鏈表属愤，LinkedHashMap保證了元素迭代的順序女器。該迭代順序可以是插入順序或者是訪問順序。
LinkedHashMap可以認(rèn)為是HashMap+LinkedList住诸，即它既使用HashMap操作數(shù)據(jù)結(jié)構(gòu)晓避，又使用LinkedList維護(hù)插入元素的先后順序。
總結(jié)
對(duì)于通過(guò)下標(biāo)隨機(jī)讀取非常多只壳、插入和刪除數(shù)據(jù)是從末尾操作的場(chǎng)景適合用數(shù)組俏拱，對(duì)于隨機(jī)讀較少、插入和刪除操作較多的場(chǎng)景適合用鏈表吼句，對(duì)于需要頻繁查找前繼和后繼節(jié)點(diǎn)的場(chǎng)景適合用雙向鏈表锅必，對(duì)于資源可以循環(huán)利用的可以使用循環(huán)鏈表。
通過(guò)單向鏈表和雙向鏈表的介紹惕艳，還需要明白可以通過(guò)定義數(shù)據(jù)結(jié)構(gòu)用空間換時(shí)間的設(shè)計(jì)思想搞隐。當(dāng)內(nèi)存空間充足的時(shí)候，如果追求代碼執(zhí)行效率远搪，可以選擇空間復(fù)雜度更高的數(shù)據(jù)結(jié)構(gòu)或算法來(lái)提高執(zhí)行效率劣纲。
拓展
java中的List集合最常見的有ArrayList，和LinkedList谁鳍，ArraysList 實(shí)現(xiàn)了 RandomAccess 接口癞季， 而 LinkedList 沒有實(shí)現(xiàn)。為什么呢倘潜？
ArraysList 底層是數(shù)組绷柒，而 LinkedList 底層是鏈表。數(shù)組天然支持隨機(jī)訪問涮因，時(shí)間復(fù)雜度為 O（1）废睦，所以稱為快速隨機(jī)訪問。
鏈表需要遍歷到特定位置才能訪問特定位置的元素养泡，時(shí)間復(fù)雜度為 O（n）嗜湃，所以不支持快速隨機(jī)訪問奈应。
ArraysList 實(shí)現(xiàn)了 RandomAccess 接口，就表明了他具有快速隨機(jī)訪問功能购披。 RandomAccess 接口只是標(biāo)識(shí)钥组，并不是說(shuō) ArraysList 實(shí)現(xiàn) RandomAccess 接口才具有快速隨機(jī)訪問功能的！
下面再總結(jié)一下 list 的遍歷方式選擇：
實(shí)現(xiàn)了RandomAccess接口的ArrayList今瀑，優(yōu)先選擇普通for循環(huán) 程梦，其次foreach,
未實(shí)現(xiàn)RandomAccess接口的LinkedList， 優(yōu)先選擇iterator遍歷（foreach遍歷底層也是通過(guò)iterator實(shí)現(xiàn)的）橘荠。
ps：大size的數(shù)據(jù)屿附，千萬(wàn)不要使用普通for循環(huán)
