LinkedList簡析

上次我講了ArrayList的使用宋彼,那么這次我就來講講他的“兄弟”锨咙,LinkedList。

相信大家都知道眶根,LinkedList是通過鏈表來進行連接的腥放。那么具體是如何進行的呢泛啸?我們還是通過源碼來進行學(xué)習(xí)。

一秃症、底層結(jié)構(gòu)

image.png

大家可以看到候址,他定義了兩個Node類型的結(jié)構(gòu),first和last种柑。其中的注釋說明岗仑,first永遠都代表著第一個節(jié)點,而last會永遠代表著最后一個節(jié)點聚请。

接下來荠雕,我們看一下這個Node的實現(xiàn)是什么樣的。

image.png

它是一個泛型驶赏,因為鏈表里可以包含任意的數(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)方法链韭。

image.png

顧名思義,它是把一個新的內(nèi)容節(jié)點采用linkLast方法加到最后面并且如果不報錯就返回true煮落。那么這個方法具體是怎么實現(xiàn)的呢敞峭?下面是源碼。

image.png

這里有一個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)系呢?

image.png

簡單的說,在一個迭代器初始的時候會賦予它調(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)方法喳张。

image.png

其實也很好理解,如果設(shè)置的index剛好是當(dāng)前的目錄就會直接插入到最后美澳,不然就是插入到指定的index位置销部。

linkBefore方法如下

image.png

首先,我們讓一個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刪除

image.png

首先我們還是要檢查index小于等于size坷备。然后返回unlink方法,入?yún)⑹且粋€node方法情臭。大家也許會好奇這個node方法是啥樣的省撑,所以我們先講一下這個node。

image.png

這個代碼中進行了一個判斷俯在,如果說我們當(dāng)前的index小于size的一半竟秫,就從前往后找到對應(yīng)的節(jié)點;不然跷乐,我們就從后往前找到對應(yīng)的節(jié)點肥败。也就是說,這個方法就是幫助我們找到對應(yīng)index下的鏈表節(jié)點的愕提。

言歸正傳馒稍,我們看一下這個unlink方法的實現(xiàn)。

image.png

這個代碼相信大家都看的懂浅侨,其實就是進行了一頭一尾的判斷纽谒。如果是第一個,那么我們需要讓這個first變成原來的第二個如输;不然佛舱,就需要把這個節(jié)點之前的節(jié)點的next變成原來這個節(jié)點的后一個。這樣一來挨决,從前往后的邏輯就成立了请祖。然后同理可以進行從后往前的連接。最后我們把這個節(jié)點的內(nèi)容置為null脖祈,size-1肆捕,并且讓modCount增加。

根據(jù)內(nèi)容刪除

image.png

這里是使用了一個object來作為入?yún)⒏歉撸驗槲覀儾恢肋@個list里具體會裝載什么類型的數(shù)據(jù)慎陵。因為null無法使用equals方法,所以需要單獨拿出來進行判斷喻奥。具體的邏輯其實和之前是一樣的席纽,不過從前往后一旦找到一個就會直接返回并返回true,也就是只會刪除第一個出現(xiàn)的對應(yīng)的數(shù)據(jù)撞蚕。

三润梯、和ArrayList的區(qū)別

相信看到這個雙向鏈表的結(jié)構(gòu),大家都會明白,我們可以直接從后往前操作這個list了。比如addLast,removeLast等方法就說明了這點

image.png

get方法中纺铭,ArrayList的內(nèi)部實現(xiàn)是基于基礎(chǔ)的對象數(shù)組的寇钉,因此,它使用get方法訪問列表中的任意一個元素時(random access)舶赔,它的速度要比LinkedList快(O1)扫倡。LinkedList中的get方法是按照順序從列表的一端開始檢查,直到另外一端(node方法)(On)竟纳。對LinkedList而言撵溃,訪問列表中的某個指定元素沒有更快的方法了

image.png

但在某些情況下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榕茧。

萌新手打垃沦,有問題請指正。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末用押,一起剝皮案震驚了整個濱河市肢簿,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌蜻拨,老刑警劉巖池充,帶你破解...
    沈念sama閱讀 222,729評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異缎讼,居然都是意外死亡收夸,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評論 3 399
  • 文/潘曉璐 我一進店門血崭,熙熙樓的掌柜王于貴愁眉苦臉地迎上來卧惜,“玉大人厘灼,你說我怎么就攤上這事⌒蛩眨” “怎么了手幢?”我有些...
    開封第一講書人閱讀 169,461評論 0 362
  • 文/不壞的土叔 我叫張陵捷凄,是天一觀的道長忱详。 經(jīng)常有香客問我,道長跺涤,這世上最難降的妖魔是什么匈睁? 我笑而不...
    開封第一講書人閱讀 60,135評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮桶错,結(jié)果婚禮上航唆,老公的妹妹穿的比我還像新娘。我一直安慰自己院刁,他們只是感情好糯钙,可當(dāng)我...
    茶點故事閱讀 69,130評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著退腥,像睡著了一般任岸。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上狡刘,一...
    開封第一講書人閱讀 52,736評論 1 312
  • 那天享潜,我揣著相機與錄音,去河邊找鬼嗅蔬。 笑死剑按,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的澜术。 我是一名探鬼主播艺蝴,決...
    沈念sama閱讀 41,179評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼鸟废!你這毒婦竟也來了吴趴?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,124評論 0 277
  • 序言:老撾萬榮一對情侶失蹤侮攀,失蹤者是張志新(化名)和其女友劉穎锣枝,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體兰英,經(jīng)...
    沈念sama閱讀 46,657評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡撇叁,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,723評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了畦贸。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片陨闹。...
    茶點故事閱讀 40,872評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡楞捂,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出趋厉,到底是詐尸還是另有隱情寨闹,我是刑警寧澤,帶...
    沈念sama閱讀 36,533評論 5 351
  • 正文 年R本政府宣布君账,位于F島的核電站繁堡,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏乡数。R本人自食惡果不足惜椭蹄,卻給世界環(huán)境...
    茶點故事閱讀 42,213評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望净赴。 院中可真熱鬧绳矩,春花似錦、人聲如沸玖翅。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽金度。三九已至应媚,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間审姓,已是汗流浹背珍特。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留魔吐,地道東北人扎筒。 一個月前我還...
    沈念sama閱讀 49,304評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像酬姆,于是被迫代替她去往敵國和親嗜桌。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,876評論 2 361