上次我講了ArrayList的使用宋彼，那么這次我就來講講他的“兄弟”锨咙，LinkedList。
相信大家都知道眶根，LinkedList是通過鏈表來進行連接的腥放。那么具體是如何進行的呢泛啸？我們還是通過源碼來進行學(xué)習(xí)。
一秃症、底層結(jié)構(gòu)
大家可以看到候址，他定義了兩個Node類型的結(jié)構(gòu)，first和last种柑。其中的注釋說明岗仑，first永遠都代表著第一個節(jié)點，而last會永遠代表著最后一個節(jié)點聚请。
接下來荠雕，我們看一下這個Node的實現(xiàn)是什么樣的。
它是一個泛型驶赏，因為鏈表里可以包含任意的數(shù)據(jù)結(jié)構(gòu)炸卑。它內(nèi)部包含一個item，也就是當(dāng)前的內(nèi)容母市；一個next矾兜，也就是下一個節(jié)點损趋；一個prev患久，也就是previous，是代表之前一個節(jié)點浑槽。這個結(jié)構(gòu)說明蒋失，LinkedList中所有節(jié)點都是用一種鏈表的形式連接起來的。而且可以看出桐玻，這是一個雙向鏈表篙挽，不但有next還有prev。
二镊靴、常用方法
2.1 add
LinkedList支持多種add方法铣卡，下面我一個個來進行分析
首先是常見的xxx.add（element）方法链韭。
顧名思義，它是把一個新的內(nèi)容節(jié)點采用linkLast方法加到最后面并且如果不報錯就返回true煮落。那么這個方法具體是怎么實現(xiàn)的呢敞峭？下面是源碼。
這里有一個last類型蝉仇，它是什么旋讹？他就是這篇文章最開始提到的那個最末尾的節(jié)點。我們先把這個值傳入l轿衔，再新建一個節(jié)點沉迹，其中l(wèi)作為它之前的節(jié)點（prev），e也就是當(dāng)前的節(jié)點害驹，null作為它之后的節(jié)點（next）鞭呕。在完成這一步之后，把這個節(jié)點變成新的last宛官。這一步其實非常好理解琅拌，相信大家不需要我畫圖也能夠想明白。
這里最后還有一個判斷摘刑，如果說這個節(jié)點是第一個節(jié)點进宝，那么first也要被賦值，不然邏輯不合理枷恕；反之党晋，就讓前任的last和當(dāng)前的節(jié)點連起來。如此徐块，就形成了一個鏈表結(jié)構(gòu)未玻。
最后的size是list的size，和ArrayList類似胡控，而這個modCount是什么呢扳剿？
在ArrayList,LinkedList,HashMap等等的內(nèi)部實現(xiàn)增，刪昼激，改中我們總能看到modCount的身影庇绽，modCount字面意思就是修改次數(shù)，但為什么要記錄modCount的修改次數(shù)呢橙困？
大家發(fā)現(xiàn)一個公共特點沒有瞧掺，所有使用modCount屬性的全是線程不安全的，這是為什么呢凡傅？說明這個玩意肯定和線程安全有關(guān)系嘍辟狈，那有什么關(guān)系呢？
簡單的說，在一個迭代器初始的時候會賦予它調(diào)用這個迭代器的對象的mCount哼转，如何在迭代器遍歷的過程中明未，一旦發(fā)現(xiàn)這個對象的mcount和迭代器中存儲的mcount不一樣那就拋異常。具體通過調(diào)用這個checkForComodification來實現(xiàn)壹蔓。
好的亚隅，下面是這個的完整解釋
Fail-Fast 機制
我們知道 java.util.LinkedList 不是線程安全的，因此如果在使用迭代器的過程中有其他線程修改了LinkedList庶溶，那么將拋出ConcurrentModificationException煮纵，這就是所謂fail-fast策略。這一策略在源碼中的實現(xiàn)是通過 modCount域偏螺，modCount顧名思義就是修改次數(shù)行疏，對LinkedList內(nèi)容的修改都將增加這個值，那么在迭代器初始化過程中會將這個值賦給迭代器的expectedModCount套像。在迭代過程中酿联，判斷 modCount 和expectedModCount是否相等，如果不相等就表示已經(jīng)有其他線程修改了LinkedList夺巩。
所以在這里和大家建議贞让，當(dāng)大家遍歷那些非線程安全的數(shù)據(jù)結(jié)構(gòu)時，盡量使用迭代器柳譬。
然后是是xxx.add（index, element）方法喳张。
其實也很好理解，如果設(shè)置的index剛好是當(dāng)前的目錄就會直接插入到最后美澳，不然就是插入到指定的index位置销部。
linkBefore方法如下
首先，我們讓一個pred為指定index之前的鏈表位置制跟；在新建一個newNode舅桩，內(nèi)容是指定的e，位置處于pred和succ中間雨膨。完成這一步后擂涛，我們肯定要把他們連接起來，所以我們讓succ之前連接上newNode聊记。最后還是一部判斷撒妈，如果說我們插入的是第二個值（之前僅有一個succ）就會讓newNode成為第一個；不然就把pred后面連接上newNode甥雕。有人會問踩身，如果說我們插入之前是空怎么辦呢胀茵？其實是不可能的社露，根據(jù)之前的checkPositionIndex方法，index的值一定是小于等于當(dāng)前的size的琼娘。如果等于則進入linkLast方法峭弟，而進入linkBefore方法的時候index一定小于size附鸽。也就意味著，size至少為1瞒瘸。
2.2 remove
直接根據(jù)index刪除
首先我們還是要檢查index小于等于size坷备。然后返回unlink方法，入?yún)⑹且粋€node方法情臭。大家也許會好奇這個node方法是啥樣的省撑，所以我們先講一下這個node。
這個代碼中進行了一個判斷俯在，如果說我們當(dāng)前的index小于size的一半竟秫，就從前往后找到對應(yīng)的節(jié)點；不然跷乐，我們就從后往前找到對應(yīng)的節(jié)點肥败。也就是說，這個方法就是幫助我們找到對應(yīng)index下的鏈表節(jié)點的愕提。
言歸正傳馒稍，我們看一下這個unlink方法的實現(xiàn)。
這個代碼相信大家都看的懂浅侨，其實就是進行了一頭一尾的判斷纽谒。如果是第一個，那么我們需要讓這個first變成原來的第二個如输；不然佛舱，就需要把這個節(jié)點之前的節(jié)點的next變成原來這個節(jié)點的后一個。這樣一來挨决，從前往后的邏輯就成立了请祖。然后同理可以進行從后往前的連接。最后我們把這個節(jié)點的內(nèi)容置為null脖祈，size-1肆捕，并且讓modCount增加。
根據(jù)內(nèi)容刪除
這里是使用了一個object來作為入?yún)⒏歉撸驗槲覀儾恢肋@個list里具體會裝載什么類型的數(shù)據(jù)慎陵。因為null無法使用equals方法，所以需要單獨拿出來進行判斷喻奥。具體的邏輯其實和之前是一樣的席纽，不過從前往后一旦找到一個就會直接返回并返回true，也就是只會刪除第一個出現(xiàn)的對應(yīng)的數(shù)據(jù)撞蚕。
三润梯、和ArrayList的區(qū)別
相信看到這個雙向鏈表的結(jié)構(gòu),大家都會明白,我們可以直接從后往前操作這個list了。比如addLast，removeLast等方法就說明了這點
get方法中纺铭，ArrayList的內(nèi)部實現(xiàn)是基于基礎(chǔ)的對象數(shù)組的寇钉，因此，它使用get方法訪問列表中的任意一個元素時(random access)舶赔，它的速度要比LinkedList快（O1）扫倡。LinkedList中的get方法是按照順序從列表的一端開始檢查，直到另外一端（node方法）（On）竟纳。對LinkedList而言撵溃，訪問列表中的某個指定元素沒有更快的方法了
但在某些情況下LinkedList的表現(xiàn)要優(yōu)于ArrayList，有些算法在LinkedList中實現(xiàn)時效率更高锥累。比方說征懈，利用Collections.reverse方法對列表進行反轉(zhuǎn)時，其性能就要好些揩悄。當(dāng)要對list進行大量的插入和刪除操作時卖哎，LinkedList也是一個較好的選擇。
今天一個同事問我删性，ArrayList和LinkedList誰更加消耗空間亏娜？我當(dāng)時脫口而出LinkedList，因為想著他是鏈表要進行連接蹬挺。但是仔細一想维贺，ArrayList存在一個內(nèi)容擴充的機制（詳情可以看https://91jkys.yuque.com/trt71o/snfgpf/gahgkv），所以在大多數(shù)情況下都是會消耗更多的空間的巴帮。簡而言之溯泣，ArrayList的空間浪費主要體現(xiàn)在在list列表的結(jié)尾預(yù)留一定的容量空間，而LinkedList的空間花費則體現(xiàn)在它的每一個元素都需要消耗相當(dāng)?shù)目臻g榕茧。
萌新手打垃沦，有問題請指正。
