昨天大概看了ArrayList的源碼實(shí)現(xiàn)吴藻，其實(shí)還是比較簡(jiǎn)單的。主要就是操作內(nèi)部的數(shù)組首有，而用的也比較多的就是今天要看的LinkedList了抖棘，它相對(duì)于ArrayList具有更高的增加/刪除效率，適合作為經(jīng)常變動(dòng)的列表使用净捅，其讀取的時(shí)間復(fù)雜度為O(n)疑枯。而ArrayList的讀取時(shí)間復(fù)雜度為O(1)，變動(dòng)多的話經(jīng)常會(huì)導(dǎo)致數(shù)組的復(fù)制操作蛔六，所以更適合作為不經(jīng)常變動(dòng)的列表荆永。

源碼分析

不得不提的Node節(jié)點(diǎn)

/**
 * 作為整個(gè)鏈表實(shí)現(xiàn)的核心封裝，Node節(jié)點(diǎn)作為一個(gè)靜態(tài)內(nèi)部類使用古今，每一個(gè)插入的數(shù)據(jù)元素都被Node節(jié)點(diǎn)包裹著
 */
private static class Node<E> {
        E item;
        Node<E> next; //指向下一個(gè)節(jié)點(diǎn)
        Node<E> prev; //指向上一個(gè)節(jié)點(diǎn)

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
之后所有關(guān)于LinkedList的操作其實(shí)都是關(guān)于Node的操作屁魏，理解Node節(jié)點(diǎn)就是理解LinkedList的基礎(chǔ)，接下來(lái)我們還是從基本的類定義開始看捉腥。

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
AbstractSequentialList ：為實(shí)現(xiàn)序列訪問(wèn)的數(shù)據(jù)儲(chǔ)存結(jié)構(gòu)的提供了所需要的最小化的接口實(shí)現(xiàn)(這接口主要是說(shuō)明他是希望實(shí)現(xiàn)者通過(guò)順序訪問(wèn)的)
Deque：雙向列表(就是支持鏈表兩頭操作的意思)

接口不是講解的重點(diǎn)氓拼，只有在需要的時(shí)候我才會(huì)去解讀接口中的具體方法含義，如果一個(gè)一個(gè)接口跟進(jìn)去的內(nèi)容比較繁瑣抵碟，而且意義也不大

屬性值

//transient 關(guān)鍵字表示在序列化的時(shí)候并不會(huì)隨著鏈表序列化為二進(jìn)制數(shù)存儲(chǔ)桃漾，可以這么做是因?yàn)榧词狗葱蛄谢鬀](méi)有這些值，
//但是在改變鏈表結(jié)構(gòu)的時(shí)候這些值又會(huì)重新生成拟逮，減少了不必要的字段也就減少了序列化的開銷撬统。
//源碼編寫者確實(shí)很精打細(xì)算。非常細(xì)微的地方都考慮到了
    transient int size = 0; //鏈表長(zhǎng)度
    transient Node<E> first; //鏈表頭節(jié)點(diǎn)
    transient Node<E> last; //鏈表尾節(jié)點(diǎn)

構(gòu)造函數(shù)

/**
 * 其中空的構(gòu)造函數(shù)我就不說(shuō)了敦迄。恋追。這個(gè)構(gòu)造函數(shù)就是直接將Collection中的數(shù)據(jù)插入到鏈表中
 */
public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index); //插入位置必須在[0,size]之間
        //為了便利方便所以轉(zhuǎn)換為數(shù)組
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;
        //succ:index所在位置的Node引用,pred:index所在位置的前一個(gè)Node引用
        Node<E> pred, succ;
        if (index == size) { //如果插入的位置就是鏈表末尾的話那就可以直接插入而不用移動(dòng)元素
            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) //說(shuō)明插入的位置是頭節(jié)點(diǎn)位置(原始的鏈表為空)
                first = newNode;
            else //上一句已經(jīng)將newNode的前節(jié)點(diǎn)指向pred，這次要將pred的后節(jié)點(diǎn)指向newNode了(注意是雙向認(rèn)定)
                pred.next = newNode;
            pred = newNode;//節(jié)點(diǎn)后移
        }

        if (succ == null) {
            last = pred; //注意經(jīng)過(guò)移動(dòng)之后現(xiàn)在pred已經(jīng)指向了新鏈表末尾的Node節(jié)點(diǎn)
        } else { //因?yàn)槭窃趕ucc這個(gè)節(jié)點(diǎn)原來(lái)的位置進(jìn)行插入的罚屋，所以現(xiàn)在succ其實(shí)已經(jīng)拋離整個(gè)鏈表了苦囱，需要跟新的前段鏈表重新連接一下
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++; //作用與ArrayList中的modCount一樣
        return true;
    }
/**
 * 即使一個(gè)簡(jiǎn)單的取下標(biāo)的方法都很精致，考慮的前半段還是后半段(返回節(jié)點(diǎn)一定非空)
 */
    Node<E> node(int index) {
        if (index < (size >> 1)) { //如果index在鏈表的前半段就從頭部開始查找脾猛，這里不用size/2是因?yàn)橐莆徊僮鞲?            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else { //如果index在鏈表的后半段就從尾部開始查找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

基本方法

public boolean add(E e) {
        linkLast(e);
        return true;
}
void linkLast(E e) {
        final Node<E> oldTail = last;
        final Node<E> newNode = new Node<>(oldTail , e, null);
        last = newNode; //這里其實(shí)只要注意一下原來(lái)的鏈表是不是空鏈表就行
        if (oldTail  == null)
            first = newNode;
        else
            oldTail.next = newNode; //沒(méi)有if判斷的話這里就報(bào)NPE了
        size++;
        modCount++;
    }
因?yàn)閘inkFirst跟linkLast一模一樣撕彤，所以我就不看了。

void linkBefore(E e, Node<E> succ) {
        // 因?yàn)檫@是一個(gè)內(nèi)部調(diào)用的方法猛拴，所以已經(jīng)保證succ不為null
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)//如果succ是頭結(jié)點(diǎn)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

private E unlinkFirst(Node<E> f) {
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // 是f沒(méi)有其他的引用鏈羹铅，促進(jìn)垃圾回收
        first = next;
        if (next == null) //如果原來(lái)鏈表只有一個(gè)節(jié)點(diǎn)的話
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

E unlink(Node<E> x) {
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
        if (prev == null) { //如果x節(jié)點(diǎn)是頭結(jié)點(diǎn)
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
        if (next == null) { //如果x節(jié)點(diǎn)是尾節(jié)點(diǎn)
            last = prev;
        } else {
            next.prev = prev;
            x.next = null; //取消x節(jié)點(diǎn)對(duì)于前后節(jié)點(diǎn)的引用
        }
        x.item = null;//還是使用置空的方式促進(jìn)GC
        size--;
        modCount++;
        return element;
    }
現(xiàn)在為止基本的變更操作已經(jīng)介紹完了蚀狰，像removeLast，removeFirst职员，addFirst麻蹋，addLast等等這些方法其實(shí)只要明白上面操作就完全夠了。還有一些poll廉邑，take等方法都是基于以上的方法所講哥蔚，基本沒(méi)有其他內(nèi)容倒谷，就是有的報(bào)錯(cuò)有的不報(bào)錯(cuò)之類的差別蛛蒙。看一下其他典型的方法
public boolean removeLastOccurrence(Object o) {
//這里的核心內(nèi)容就是判斷所移除的對(duì)象是不是null渤愁，因?yàn)槭莕ull的話就沒(méi)法使用equals方法比較
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = last; x != null; x = x.prev) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
//無(wú)參的toArray()沒(méi)啥可看的牵祟，就是遍歷然后賦值就可以
public <T> T[] toArray(T[] a) {
        if (a.length < size) //如果a轉(zhuǎn)不下鏈表內(nèi)容的話就創(chuàng)建一個(gè)包含T類型元素的數(shù)組
            a = (T[])java.lang.reflect.Array.newInstance(
                                a.getClass().getComponentType(), size);
        int i = 0;
        Object[] result = a;
        for (Node<E> x = first; x != null; x = x.next)
            result[i++] = x.item;

        if (a.length > size) //注意這里的置空操作
            a[size] = null;

        return a;
    }

public Object clone() {
        LinkedList<E> clone = superClone();
        clone.first = clone.last = null;
        clone.size = 0;
        clone.modCount = 0;
       //從這里看到這個(gè)克隆還是淺克隆,因?yàn)閤.item還是原來(lái)的地址
        for (Node<E> x = first; x != null; x = x.next)
            clone.add(x.item);
        return clone;
    }

接下來(lái)我們看一下Iterator的詳細(xì)實(shí)現(xiàn)，通常遍歷有兩種方式抖格，一種是通過(guò)for循環(huán)進(jìn)行遍歷诺苹，另外一種就是通過(guò)Iterator了，而且Iterator可以在遍歷的過(guò)程中改變鏈表節(jié)點(diǎn)雹拄，但是在for循環(huán)過(guò)程中改變鏈表節(jié)點(diǎn)的話會(huì)有你喜歡的東西出現(xiàn)噢收奔。。

private class ListItr implements ListIterator<E> //內(nèi)部類ListItr
private Node<E> lastReturned = null; //記錄本次操作的目標(biāo)對(duì)象(next()返回是它滓玖，刪除的話也是它)
private Node<E> next; //下一個(gè)遍歷出的節(jié)點(diǎn)
private int nextIndex; //下一個(gè)節(jié)點(diǎn)的下標(biāo)
private int expectedModCount = modCount; //用來(lái)判斷在遍歷過(guò)程中有沒(méi)有節(jié)點(diǎn)變更

ListItr(int index) {//初始化的時(shí)候從下標(biāo)為index的位置開始
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }
//下面這兩個(gè)方法應(yīng)該是我們最常調(diào)用的方法了
public boolean hasNext() {
            return nextIndex < size;
        }
//從這里我們就知道m(xù)odCount的用途了坪哄，如果是for循環(huán)的話，循環(huán)過(guò)程中改變節(jié)點(diǎn)會(huì)改變modCount.
//因?yàn)閒or循環(huán)本質(zhì)上還是靠Iterator來(lái)實(shí)現(xiàn)的势篡，所以在遍歷過(guò)程中發(fā)現(xiàn)節(jié)點(diǎn)變化就立馬報(bào)錯(cuò)了
public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();
            lastReturned = next; //這個(gè)lastReturned主要是用來(lái)保存返回結(jié)果的
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }
final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
//這就解釋了為什么遍歷過(guò)程之中Iteraort的remove是可以的
public void remove() {
            checkForComodification(); //操作開始時(shí)候的modCount與expectedModCount的相等還是要保證的
            if (lastReturned == null)
                throw new IllegalStateException();
            Node<E> lastNext = lastReturned.next;
            unlink(lastReturned);
//正常情況兩者是不會(huì)相等的翩肌，但是為了保證代碼的健壯性我們要考慮這種操作，例如我在多線程情況下進(jìn)行操作禁悠，調(diào)用next()方法到了
//第四行時(shí)候忽然切到另外一個(gè)線程念祭，這時(shí)候其實(shí)next = lastReturned而且由于next()還沒(méi)有運(yùn)行到nextIndex++所以這里也就不用nextIndex--
//雖然LinkedList不是線程安全的，但是在這里盡量去保證其在多線程運(yùn)行環(huán)境下的安全性
            if (next == lastReturned) 
                next = lastNext;
            else
                nextIndex--; //刪除了一個(gè)next前的元素,nextIndex--是必要的
            lastReturned = null;
            expectedModCount++; //在unlink中modCount++了碍侦，所以expectedModCount在這里也自增
        }
public void add(E e) {
            checkForComodification();
            lastReturned = null;
            if (next == null) //如果插入位置在鏈表末尾的話
                linkLast(e);
            else
                linkBefore(e, next);
            nextIndex++;
            expectedModCount++;
        }

當(dāng)然LinkedList內(nèi)部還有一個(gè)DescendingIterator作為逆向遍歷使用的粱坤，因?yàn)長(zhǎng)inkedList是雙向鏈表，所以不管正向還是逆向其實(shí)內(nèi)部實(shí)現(xiàn)都是一樣的瓷产，不需要再進(jìn)行過(guò)多的關(guān)注了站玄。
<strong>到這里其實(shí)LinkedList的整個(gè)實(shí)現(xiàn)都已經(jīng)講解清楚了，沒(méi)有提到的方法往往是因?yàn)樘^(guò)簡(jiǎn)單或者內(nèi)容重復(fù)拦英，凡是我覺(jué)得值得注意的地方我都進(jìn)行了清晰的注釋蜒什，如果有哪些大家覺(jué)得我理解有誤的地方一定要在評(píng)論的時(shí)候?qū)懗鰜?lái)，我會(huì)積極參與討論疤估。</strong>