上次我講了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榕茧。
萌新手打垃沦,有問題請指正。