在前面的文章里，我們講了數(shù)組和ArrayList纬凤，在現(xiàn)實(shí)中，不管什么系統(tǒng)撩嚼，如果不考慮性能的話停士，用其中的一個(gè)就可以完成所有工作，那為什么不用它們來(lái)進(jìn)行所有的數(shù)據(jù)存儲(chǔ)呢完丽？
在數(shù)組/ArrayList中讀取和存儲(chǔ)(get/set)的性能非常高恋技，為O(1)，但插入(add(int index, E element))和刪除(remove(int index))卻花費(fèi)了O(N)時(shí)間逻族，效率并不高蜻底。
今天我們來(lái)看Java中的另一種List即LinkedList，LinkedList是基于雙向鏈表來(lái)實(shí)現(xiàn)的聘鳞，關(guān)于鏈表的知識(shí)我們Java數(shù)據(jù)結(jié)構(gòu)之線性表 - 知乎專欄一文中有過(guò)介紹薄辅，HashMap和鏈表也有關(guān)系，所以我們要先講它抠璃，話不多說(shuō)站楚，上代碼。
這段代碼和我們之前的往ArrayList添加元素的代碼基本上是一模一樣的鸡典，只是修改了紅框的內(nèi)容為L(zhǎng)inkedList源请，這時(shí)候再往里添加元素枪芒，調(diào)用的就是LinkedList里面的add方法了彻况。在之前的面向?qū)ο?/a>一文中我們已經(jīng)說(shuō)過(guò)了，這是多態(tài)的體現(xiàn)舅踪，利用好多態(tài)纽甘，在編碼過(guò)程中，我們可以少修改很多東西抽碌，忘記了的朋友可以回過(guò)頭去看一下悍赢。一看到new這個(gè)關(guān)鍵字，我們腦海里應(yīng)該是货徙，這貨在堆內(nèi)存中開辟了一塊空間左权，我們先從構(gòu)造函數(shù)入手吧广辰。
滿懷希望的打開構(gòu)造函數(shù)膝晾，好傷心，里面沒(méi)有任何邏輯妥凳，只能從成員變量入手蠢棱。
發(fā)現(xiàn)三個(gè)成員變量锌杀，size就不多說(shuō)了甩栈，大家猜一下就知道是LinkedList的邏輯長(zhǎng)度，初始化為0糕再，并持有兩個(gè)Node引用量没，first看名字一猜就是第一個(gè)，last看名字就是最后一個(gè)突想，我們先來(lái)畫一畫
初始化完了殴蹄，在堆內(nèi)存中就是這個(gè)樣子，size為0猾担。引用類型的成員變量初始化為null饶套，再來(lái)看一看這個(gè)Node是什么東東
這是一個(gè)內(nèi)部靜態(tài)私有類，該類只能在LinkedList中訪問(wèn)垒探，先記住它妓蛮，debug看一下
和我們圖中一致，我們繼續(xù)執(zhí)行碼里的add方法圾叼，看源碼
很普通蛤克，e是我們往里添加的Person對(duì)象“張三”，繼續(xù)跟蹤linkLast方法：
第一次往LinkedList里添加元素夷蚊，我們看上圖11-1就知道构挤，first為null，last也為null惕鼓，把我們的Person對(duì)象“張三”傳給了Node的構(gòu)造函數(shù)筋现，再看Node的構(gòu)造函數(shù)：
用Person張三為入?yún)?gòu)造了一個(gè)Node對(duì)象，好了箱歧，又到了畫圖的時(shí)候
老規(guī)矩矾飞，debug一下：
和我們圖中所畫的一致，我們繼續(xù)添加“李四”這個(gè)Person對(duì)象呀邢，再打開源碼分析一下洒沦。
張三這個(gè)Node指向新new出來(lái)的Node對(duì)象，再看Node是怎么創(chuàng)建的
創(chuàng)建Node對(duì)象价淌，新new出來(lái)的Node對(duì)象的prev引用指向包含Person張三的Node對(duì)象申眼。item引用指向Person李四對(duì)象，繼續(xù)畫圖：
看上圖蝉衣，原來(lái)的next引用指向新new出來(lái)的Node括尸，同時(shí)新new出來(lái)的Node的prev引用指向原來(lái)的Node對(duì)象，item指向新new出來(lái)的Person李四這個(gè)對(duì)象病毡，同時(shí)perList這個(gè)LinkedList對(duì)象的last引用指向新new出來(lái)的這個(gè)Node濒翻，再debug看一下
好的，繼續(xù)添加“王五”剪验，“趙六”
很簡(jiǎn)單肴焊，沒(méi)有了底層數(shù)組前联，新增加了一個(gè)Node對(duì)象，記錄了Person的內(nèi)容娶眷，每個(gè)Node對(duì)象都持有next引用(下一個(gè))和prev引用(上一個(gè))似嗤，其實(shí)就是之前Java數(shù)據(jù)結(jié)構(gòu)之線性表 - 知乎專欄一文里介紹的雙向鏈表，這個(gè)圖看起來(lái)有點(diǎn)亂届宠，多年前我在讀這段代碼的時(shí)候烁落，差點(diǎn)暈過(guò)去了，又是next豌注，prew伤塌，first，last轧铁，容易亂每聪，因此大家在學(xué)習(xí)源碼的過(guò)程中，有不明白的地方齿风，找張紙和筆畫一畫药薯，就清晰了。放張簡(jiǎn)化版的圖救斑，方便大家理解童本。
大家有什么看不明白的地方，可以在評(píng)論區(qū)留言脸候，本文在寫作過(guò)程中如果有什么勘誤穷娱，還希望細(xì)心的讀者提出來(lái)，下一篇我們研究LinkedList的查找运沦、插入與刪除泵额，并引入時(shí)間復(fù)雜度來(lái)分析。
轉(zhuǎn)載出自：https://zhuanlan.zhihu.com/p/28101975
