源碼版本JDK1.8

今天帶來(lái)的是List的另一種實(shí)現(xiàn)——LinkedList滔以，這是一種基于雙向鏈表實(shí)現(xiàn)的列表鲁驶。接下來(lái)讓我們通過(guò)源碼來(lái)分析一下它吧椅文。

關(guān)于源碼中的一些小改動(dòng)

在JDK1.6及之前冒晰，LinkedList底層是一個(gè)雙向循環(huán)鏈表，容器中的元素都是靜態(tài)內(nèi)部類Entry的對(duì)象蚜枢，列表中必有一個(gè)空頭結(jié)點(diǎn)缸逃；
在JDK1.7及之后，LinkedList底層是一個(gè)雙向非循環(huán)鏈表厂抽，容器中的元素都是靜態(tài)內(nèi)部類Node的對(duì)象需频。
基于這些小差別，筆者分享下自己的見(jiàn)解：

• 使用非循環(huán)鏈表后筷凤，可以少一個(gè)空的頭結(jié)點(diǎn)昭殉，在頭尾加入元素時(shí)可以少一些引用操作（對(duì)于循環(huán)鏈表來(lái)說(shuō)，由于首尾相連，還是需要處理兩頭的前驅(qū)和后繼引用饲化。而非循環(huán)鏈表只需要處理一邊f(xié)irst.previous/last.next莽鸭，所以理論上非循環(huán)鏈表更高效吗伤。恰恰在兩頭(鏈頭/鏈尾) 操作是最普遍的）
• 對(duì)于Entry改變成Node吃靠，本質(zhì)上是沒(méi)有差別的∽阆可能大家對(duì)Entry的印象是Map中實(shí)現(xiàn)的一個(gè)內(nèi)部類巢块，用來(lái)存儲(chǔ)鍵值對(duì)<key,value>，而在LinkedList中是要存儲(chǔ)<previous,item,next>巧号，不便于凸顯Entry存儲(chǔ)鍵值對(duì)的特性吧族奢，容易造成混淆。（這只是個(gè)人的猜測(cè)丹鸿，若有不同見(jiàn)解可以交流）
  補(bǔ)充：不論是Entry還是Node越走，都是外部類LinkedList實(shí)現(xiàn)的一個(gè)靜態(tài)內(nèi)部類，這么做是把一個(gè)類相關(guān)的類型放到內(nèi)部靠欢，提高類的高內(nèi)聚廊敌，而且通常情況下只有該外部類會(huì)調(diào)用其內(nèi)部類，如果把Entry或者Node放到外部门怪，明顯就提高了耦合性骡澈，對(duì)于其他集合類型的內(nèi)部實(shí)現(xiàn)來(lái)說(shuō)都是不利的。
  再有一個(gè)掷空，內(nèi)部類會(huì)隨著外部類的加載而產(chǎn)生肋殴。
  傳送門(mén)：關(guān)于靜態(tài)內(nèi)部類
  
  雙向循環(huán)鏈表結(jié)構(gòu)
  
  
  雙向非循環(huán)鏈表結(jié)構(gòu)

一、LinkedList概述

在源碼中對(duì)LinkedList是這么描述的：

• 雙向鏈表實(shí)現(xiàn) List和Deque接口坦弟。實(shí)現(xiàn)所有可選的列表操作护锤，并允許所有元素null。
• 所有操作的執(zhí)行方式與雙向鏈表都是一樣的酿傍。索引到列表中的操作將從開(kāi)始或結(jié)束遍歷列表烙懦，無(wú)論哪個(gè)更接近指定的索引。
• 此實(shí)現(xiàn)未同步拧粪。
  *此類的 iterator和listIterator方法返回的迭代器：如果在創(chuàng)建迭代器之后的任何時(shí)間對(duì)結(jié)構(gòu)進(jìn)行修改修陡，除了通過(guò)迭代器自己的remove}或{@code add方法，迭代器將拋出一個(gè)ConcurrentModificationException可霎。因此魄鸦，面對(duì)并發(fā)修改，迭代器快速而干凈地失敗癣朗，而不是在將來(lái)的未確定時(shí)間冒任意的拾因，非確定性行為的風(fēng)險(xiǎn)。

二、LinkedList的繼承绢记、實(shí)現(xiàn)關(guān)系

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

• 繼承自AbstractSequentialList扁达，而AbstractSequentialList父類為AbstractList，AbstractSequentialList 實(shí)現(xiàn)了get(int index)蠢熄、set(int index, E element)跪解、add(int index, E element) 和 remove(int index)這些骨干性函數(shù)。
• 實(shí)現(xiàn)List接口签孔，能對(duì)它進(jìn)行隊(duì)列操作叉讥。
• 實(shí)現(xiàn)Deque接口，而Deque是Queue的子接口饥追。Queue是一種隊(duì)列形式图仓，而Deque則是雙向隊(duì)列，它支持從兩個(gè)端點(diǎn)方向檢索和插入元素但绕，因此Deque既可以支持LIFO形式也可以支持LIFO形式救崔。Deque接口是一種比Stack和Vector更為豐富的抽象數(shù)據(jù)形式,因?yàn)樗瑫r(shí)實(shí)現(xiàn)了以上兩者。傳送門(mén)：Deque雙端隊(duì)列
• 實(shí)現(xiàn)了Cloneable接口捏顺，即覆蓋了函數(shù)clone()六孵，能克隆。
• 實(shí)現(xiàn)java.io.Serializable接口草丧，這意味著LinkedList支持序列化狸臣，能通過(guò)序列化去傳輸
  
  繼承實(shí)現(xiàn)關(guān)系.jpg

三、LinkedList屬性聲明及構(gòu)造函數(shù)

transient int size = 0;
transient Node<E> first;//指向第一個(gè)節(jié)點(diǎn)的指針
transient Node<E> last;//指向最后一個(gè)節(jié)點(diǎn)的指針

//構(gòu)造一個(gè)空列表
public LinkedList() {
    }
//按照集合的迭代器返回的順序構(gòu)造包含指定集合的??元素的列表
public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

—addAll()方法

public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        Node<E> pred, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }

        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }

        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }

帶Collection值的構(gòu)造方法的執(zhí)行邏輯：
1）使用this（）調(diào)用默認(rèn)的無(wú)參構(gòu)造函數(shù)昌执；
2）調(diào)用addAll（）方法烛亦，傳入當(dāng)前的節(jié)點(diǎn)個(gè)數(shù)size，此時(shí)size為0懂拾，并將collection對(duì)象傳遞進(jìn)去煤禽；
3）檢查index有沒(méi)有數(shù)組越界的嫌疑；
4）將collection轉(zhuǎn)換成數(shù)組對(duì)象a岖赋；
5）循環(huán)遍歷a數(shù)組檬果，然后將a數(shù)組里面的元素創(chuàng)建成擁有前后連接的節(jié)點(diǎn)，然后一個(gè)個(gè)按照順序連起來(lái)唐断；
6）修改當(dāng)前的節(jié)點(diǎn)個(gè)數(shù)size的值选脊；
7）操作次數(shù)modCount自增1。

四脸甘、LinkedList的方法

（一）添加元素

—在頭部添加元素

//在此列表的開(kāi)頭插入指定的元素
public void addFirst(E e) {
        linkFirst(e);
    }

private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

linkFirst(E e)是一個(gè)私有方法恳啥，所以無(wú)法在外部程序中調(diào)用（當(dāng)然，這是一般情況丹诀，你可以通過(guò)反射上面的還是能調(diào)用到的）钝的。
linkFirst(E e)首先構(gòu)造一個(gè)變量結(jié)點(diǎn)f = first翁垂，再 new一個(gè)newNode（為要添加進(jìn)來(lái)的節(jié)點(diǎn)），其前驅(qū)引用previous為null硝桩，后繼引用為f沿猜，再另頭結(jié)點(diǎn)指向新的節(jié)點(diǎn)newNode。
判斷碗脊，如果f == null啼肩，即列表為空，則頭尾節(jié)點(diǎn)指向同一個(gè)節(jié)點(diǎn)newNode望薄；如果不為空疟游，原來(lái)頭結(jié)點(diǎn)的前驅(qū)引用指向新節(jié)點(diǎn)newNode。
—在尾部添加元素

//將指定的元素追加到此列表的末尾
public void addLast(E e) {
        linkLast(e);
    }
void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

原理與在頭部添加元素類似痕支，可參照上面進(jìn)行解讀。
—在任意位置添加元素

// 在此列表中指定的位置插入指定的元素蛮原。將當(dāng)前在該位置的元素(如果有)和任何后續(xù)元素向右移(將一個(gè)添加到它們的索引)
public void add(int index, E element) {
        checkPositionIndex(index);
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
//在非空節(jié)點(diǎn)succ之前插入元素e
void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

從源碼中看出卧须，若索引index==size，便直接在尾部添加元素儒陨；若不是花嘶，則調(diào)用linkBefore(E e, Node<E> succ)函數(shù)。
linkBefore(E e, Node<E> succ)首先構(gòu)造一個(gè)變量結(jié)點(diǎn)pred = succ.prev蹦漠，再 new一個(gè)newNode（為要添加進(jìn)來(lái)的節(jié)點(diǎn)）椭员，其前驅(qū)引用previous為pred ，后繼引用為succ笛园，再另結(jié)點(diǎn)succ的前驅(qū)指向新的節(jié)點(diǎn)newNode隘击。
判斷，如果pred == null研铆，即列表為空埋同，則頭尾節(jié)點(diǎn)指向同一個(gè)節(jié)點(diǎn)newNode；如果不為空棵红，原來(lái)pred結(jié)點(diǎn)的后繼引用指向新節(jié)點(diǎn)newNode凶赁。

（二）查看元素

查看元素使用get方法。getFirst()逆甜、getLast()分別返回頭結(jié)點(diǎn)和尾節(jié)點(diǎn)虱肄。下面主要看看返回指定索引的方法get(int index)。

//返回此列表中指定位置的元素
public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
 private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }
//返回指定元素索引處的(非空)節(jié)點(diǎn)
Node<E> node(int index) {
        // assert isElementIndex(index);
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

get(int index)首先判斷給定索引是否存在交煞，若存在執(zhí)行node(index).item;其中item為元素的內(nèi)容咏窿。
node(int index)方法返回的是一個(gè)節(jié)點(diǎn)Node<E>，代碼中使用了類似二分法的查找方法來(lái)遍歷元素错敢。若index < (size >> 1)翰灾，即索引在前半部分缕粹，則從前向后依次查找；否則索引就在后半部分纸淮，從后向前依次查找平斩。
此段代碼能夠有效的提高遍歷效率，也反映了雙向鏈表的優(yōu)點(diǎn)——雙向鏈表增加了一點(diǎn)點(diǎn)的空間消耗（每個(gè)Node里面還要維護(hù)它的前置Node的引用）咽块，同時(shí)也增加了一定的編程復(fù)雜度绘面，卻大大提升了遍歷效率（體現(xiàn)在可以雙向遍歷）。

（三）刪除元素

removeFirst()侈沪，removeLast()分別用來(lái)刪除頭結(jié)點(diǎn)和尾結(jié)點(diǎn)揭璃，public E remove()方法刪除的也是列表的第一個(gè)元素，但是列表為空時(shí)使用不會(huì)拋出異常（removeFirst()會(huì)拋出異常）亭罪。
和ArrayList一樣瘦馍，LinkedList支持按元素刪除和按下標(biāo)刪除,下面我們主要介紹public E remove(int index)，public boolean remove(Object o)

//刪除此列表中指定位置的元素应役。將任何后續(xù)元素向左移(從它們的索引中減去一個(gè))情组。返回從列表中刪除的元素
public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }
//取消鏈接非空節(jié)點(diǎn)x
E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
        x.item = null;
        size--;
        modCount++;
        return element;
    }

按索引刪除remove(int index)：
首先通過(guò)遍歷node(index)得到指定索引的節(jié)點(diǎn)，后通過(guò)unlink()方法進(jìn)行刪除箩祥。
(1)x.prev = null;//前驅(qū)設(shè)置為null
(2)x.next = null;//后繼設(shè)置為null
(3)x.item = null;//內(nèi)容設(shè)置為null
至此節(jié)點(diǎn)x為空節(jié)點(diǎn)院崇，最后交給虛擬機(jī)gc完成回收，刪除操作結(jié)束袍祖。

//從列表中刪除指定元素的第一次出現(xiàn)(如果存在)底瓣。如果此列表不包含元素,則不會(huì)更改。
public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

按元素刪除內(nèi)容remove(Object o)：
不論元素內(nèi)容為空還是不為空蕉陋，均通過(guò)節(jié)點(diǎn)的遍歷捐凭，依次查找，若找到與指定內(nèi)容一致的節(jié)點(diǎn)則刪除并返回寺滚。
注意：該方法從列表中刪除第一次出現(xiàn)的指定元素柑营。

LinkedList的方法比較簡(jiǎn)單，沒(méi)有擴(kuò)容環(huán)節(jié)村视，翻閱源碼基本能懂官套，不存在什么大問(wèn)題。由于LinkedList實(shí)現(xiàn)了Deque接口蚁孔，該接口比List提供了更多的方法奶赔，包括 offer()，peek()杠氢，poll()等站刑。

//檢索,但不刪除此列表的頭(第一個(gè)元素)
public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }
//檢索并刪除此列表的頭(第一個(gè)元素)
public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }
//檢索但不刪除此列表的第一個(gè)元素,如果此列表為空,則返回null
public E peekFirst() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
     }
//檢索但不刪除此列表的最后一個(gè)元素,如果此列表為空,則返回null
public E peekLast() {
        final Node<E> l = last;
        return (l == null) ? null : l.item;
    }
//檢索并刪除此列表的第一個(gè)元素,如果此列表為空,則返回null
public E pollFirst() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }
//檢索并刪除此列表的最后一個(gè)元素,如果此列表為空,則返回null
public E pollLast() {
        final Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }
//將指定的元素添加為此列表的尾部(最后一個(gè)元素)
public boolean offer(E e) {
        return add(e);
    }
//在此列表的前面插入指定的元素
public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }
//在此列表的結(jié)尾插入指定的元素
public boolean offerLast(E e) {
        addLast(e);
        return true;
    }
//將元素推送到此列表所表示的堆棧。換句話說(shuō),將元素插入此列表的前面,此方法等效于addFirst
public void push(E e) {
        addFirst(e);
    }
//此列表所表示的堆棧中彈出一個(gè)元素鼻百。換句話說(shuō),刪除并返回此列表的第一個(gè)元素,此方法等效于removeFirst()
public E pop() {
        return removeFirst();
    }

五绞旅、ArrayList與LinkedList的區(qū)別

（一）從插入摆尝、刪除元素分析

對(duì)于兩者的插入、刪除操作不能片面的蓋棺定論因悲，應(yīng)視情況而定堕汞，下面以插入操作做分析（刪除操作的分析類似）
順序插入：

• ArrayList在不擴(kuò)容的情況下順序插入速度較快，因?yàn)樵跇?gòu)造ArrayList之前已經(jīng)分配好空間晃琳，順序插入元素只是往指定內(nèi)存空間補(bǔ)個(gè)元素讯检；在需要擴(kuò)容的情況下，ArrayList的順序插入則顯得比較慢卫旱，因?yàn)榈讓有枰獔?zhí)行copy操作人灼，既耗時(shí)又耗空間。
• LinkedList順序添加元素會(huì)教慢點(diǎn)顾翼，因?yàn)槊刻砑右粋€(gè)元素都要新new一個(gè)節(jié)點(diǎn)對(duì)象投放，并且還有執(zhí)行其他的引用賦值操作。

中間插入：

• ArrayList在執(zhí)行中間插入的過(guò)程中耗時(shí)的是索引后面的元素copy移動(dòng)暴构，若果插入的位置越靠前則越慢跪呈，反之越快。
• LinkedList在任何位置插入的效率基本上是一致的取逾，耗時(shí)的部分主要是定位索引（尋址），賦值部分只需修改引用苹支。

綜合以上所述：
（1）LinkedList做插入砾隅、刪除的時(shí)候，慢在尋址债蜜，快在只需要改變前后Node的引用地址晴埂。
（2）ArrayList做插入、刪除的時(shí)候寻定，慢在數(shù)組元素的批量copy儒洛，快在尋址。

所以狼速，如果待插入琅锻、刪除的元素是在數(shù)據(jù)結(jié)構(gòu)的前半段尤其是非常靠前的位置的時(shí)候向胡，LinkedList的效率將大大快過(guò)ArrayList恼蓬，因?yàn)?em>ArrayList將批量copy大量的元素；越往后僵芹，對(duì)于LinkedList來(lái)說(shuō)处硬，因?yàn)樗请p向鏈表，所以在第2個(gè)元素后面插入一個(gè)數(shù)據(jù)和在倒數(shù)第2個(gè)元素后面插入一個(gè)元素在效率上基本沒(méi)有差別拇派，但是ArrayList由于要批量copy的元素越來(lái)越少荷辕，操作速度必然追上乃至超過(guò)LinkedList凿跳。

（二）從遍歷列表分析

未完待續(xù)。疮方。控嗜。