我們都知道，ArrayList和LinkedList2個是List接口最重要的2個實現(xiàn)；
上篇文章通過自己定義1個ArrayList的方式來分析了ArrayList的實現(xiàn)原理垮庐，
這篇我們也通過這個方式來分析下LinkedList的實現(xiàn)原理亭螟，并分析下ArrayList和LinkedList的區(qū)別磺陡；
LinkedList支持無參構(gòu)造减途，并且在構(gòu)造中可以什么 也不用做捎废，我們直接進(jìn)入他的增刪改查方法來分析种玛；
Node類
Node的作用我們之后再說藐鹤，暫時知道他是LinkedList的一個內(nèi)部類就可以；
LinkedList中定義了個Node的變量赂韵，1個first娱节，1個last;我們繼續(xù)往下分析
LinkedList底層維護(hù)的是1個鏈表，所以我們簡單下畫圖祭示；
LinkedList中的結(jié)構(gòu)就是1個Node（節(jié)點）肄满，每個節(jié)點都包含1個prev 1個next和1個element,其中prev是指向上一個節(jié)點的指針，next是指向下1個節(jié)點的指針质涛，element才是我們放進(jìn)去的值稠歉；
因此我們就可以得出first的結(jié)構(gòu)和last的結(jié)構(gòu)為下圖：
first為鏈表的第一個節(jié)點，所以他的prev為null,last為鏈表的最后1個節(jié)點汇陆，所以他的next為null怒炸，之后我們的邏輯中就以此為判斷依據(jù)來區(qū)分節(jié)點是否為頭（尾）節(jié)點
現(xiàn)在我們來看看
Add方法：
add方法是在集合的尾部增加1個元素，所以最重要的方法就是linkLast方法毡代；
該方法的邏輯也很簡單阅羹，就是將目前鏈表的最后1個元素，也就是last教寂，賦給1個臨時節(jié)點l捏鱼，之后將這個臨時節(jié)點l作為prev創(chuàng)建1個新節(jié)點，將此新節(jié)點設(shè)置為鏈表的最后1個節(jié)點酪耕，也就是last = newNode;
最后判斷當(dāng)前創(chuàng)建的是不是鏈表中 的第一個節(jié)點导梆，如果是，則直接賦值給first,如果不是，則將新節(jié)點接入到舊鏈表的尾部(next節(jié)點指針)问潭，完成1次元素的添加
上面說了是add方法在集合的尾部增加元素的情況猿诸，那下面接著分析下在具體位置如何插入1個元素
根據(jù)上面代碼邏輯，如果是在尾部插入的話狡忙，直接走尾部插入的邏輯梳虽；
首先，先找到需要插入的位置的節(jié)點數(shù)據(jù)
我們可以將鏈表想象成如下圖的結(jié)構(gòu)：
假設(shè)集合中一共10個數(shù)據(jù)灾茁，當(dāng)我們需要在鏈表的第三個位置也就是index = 2的位置插入數(shù)據(jù)時窜觉，我們首先就需要找到index = 2時候Node的數(shù)據(jù)；
鏈表一共10個數(shù)據(jù)北专，index = 2禀挫，位于鏈表的前半部分，所以可以從鏈表的頭節(jié)點開始找拓颓；
循環(huán)遍歷列表语婴，first 的next指針指向的是Node2,Node2的next指針指向的Node3，此時我們只需要遍歷2次就找到了index = 2對應(yīng)的節(jié)點數(shù)據(jù)了驶睦；
如果此時index = 8砰左，位于鏈表的后半部分，如果還從頭結(jié)點開始尋找就顯得效率很慢场航，這時候就可以轉(zhuǎn)換下思路缠导，從尾節(jié)點反向查找；
尾節(jié)點last的 prev指針指向的就是Node9溉痢，Node9的prev指針指向的就是Node8,只需要查找2此就能找到index = 8所對應(yīng)的節(jié)點數(shù)據(jù)僻造，大大提高了查找的效率；
以上就是node()的實現(xiàn)原理孩饼，現(xiàn)在得到了需要插入的Index的位置所對應(yīng)的節(jié)點數(shù)據(jù)髓削，我們繼續(xù)看下是如何在 指定位置插入數(shù)據(jù)的；
還是以在Index為2插入1個數(shù)據(jù)為例來講解捣辆。
可以由上圖看到蔬螟，如果要在index為2的位置插入新的節(jié)點，那原來的Node3就得往后移動汽畴；改動涉及到3個節(jié)點：Node2,Node3和newNode
Node2的next指針指向的節(jié)點由指向Node3改成newNode；
Node3的prev指針由指向Node2改成指向newNode;
newNode的prev指針指向的是Node2,next指針指向的是Node3
如果插入的位置是頭節(jié)點耸序，那很顯然的prev是空的忍些。則可以直接將新節(jié)點賦為頭結(jié)點
以上就在指定位置插入數(shù)據(jù)的具體實現(xiàn)細(xì)節(jié)
set和get方法的具體實現(xiàn)細(xì)節(jié)最主要的就node方法的細(xì)節(jié)，獲取index位置的節(jié)點數(shù)據(jù)坎怪。參考上面的node的解析
remove方法
具體接著看unLink()方法的實現(xiàn)細(xì)節(jié)
同樣是需要獲取需要刪除位置的節(jié)點數(shù)據(jù)
針對頭節(jié)點罢坝，尾節(jié)點和中間節(jié)點參照下三圖
如果刪除的是中間節(jié)點 Node3,那么收到牽連的就有3個節(jié)點：
Node2節(jié)點的next指針指向的由Node3--->Node4
Node4節(jié)點的prev指針指向由Node3--->Node2
Node3節(jié)點的prev指針指向由Node2--->null，next指針指向由Node4--->null；
如果刪除的是頭節(jié)點嘁酿，則直接把Node2移到first節(jié)點上當(dāng)做頭節(jié)點隙券，其他的都不需要改動
如果刪除的是尾節(jié)點，則直接把Node9移到last節(jié)點上當(dāng)做鏈表的尾節(jié)點闹司，其他也不需要改動
以上就LinkedList的基本實現(xiàn)原理娱仔；
