LinkedList

LinkedList是List接口的一個(gè)實(shí)現(xiàn)類，內(nèi)部是基于一個(gè)雙向鏈表實(shí)現(xiàn)的。支持添加，移除，替換三種操作。
同時(shí)，LinkedList中的元素可以是任意類型的，包括null。當(dāng)需要隊(duì)列一樣的數(shù)據(jù)操作的時(shí)候使用LinkedList是很有用的。

先來(lái)看看LinkedList的繼承結(jié)構(gòu)：

AbstractCollection

AbstractList

AbstractSequentialList

LinkedList

此外LinkedList還直接實(shí)現(xiàn)了一下的接口：

List<E>, Deque<E>, Queue<E>, Cloneable, Serializable

List接口在之前額ArrayList分析中已近講過(guò)了。這里就不贅述了。下面主要看看Deque<E>, Queue<E>這兩個(gè)接口。

Queue

Queue被設(shè)計(jì)用來(lái)做預(yù)先處理的收集器。它除了有繼承子Collection的功能實(shí)現(xiàn)外，還有插入，刪除，查找三個(gè)操作。
并且這三個(gè)操作都有對(duì)應(yīng)的兩種類型的實(shí)現(xiàn)方法。一種會(huì)拋出異常，另一種則是返回一個(gè)指定的值。在插入操作還會(huì)有容量限制，沒(méi)有容量限制的話能保證插入不會(huì)失敗。

Deque(其實(shí)是雙向隊(duì)列的縮寫)

繼承自Queue。

Deque是一個(gè)線性收集器，支持從開(kāi)頭或者結(jié)尾添加或者刪除元素。Deque的實(shí)現(xiàn)類基本都不加入容量限制，但是保留有這個(gè)功能。Deque支持的操作有添加，移除，檢索元素。每種操作都有兩種類型，一種是操作失敗直接拋出異常，另一種是返回一個(gè)指定的值。

在Deque和Queue中可能拋出的異常有：
IllegalStateException，ClassCastException，NullPointerException，IllegalArgumentException

LinkedList

先來(lái)看看它的一個(gè)內(nèi)部靜態(tài)類。
實(shí)際上是對(duì)數(shù)據(jù)的封裝，以及加上它的前后元素的引用。其實(shí)和C語(yǔ)言中的鏈表的指針的意思是一樣的。

private static final class Link<ET> {
    ET data;　//封裝的數(shù)據(jù)元素

    Link<ET> previous, next;//該元素指向它的前后元素的引用。

    Link(ET o, Link<ET> p, Link<ET> n) {
        data = o;//我們使用LinkedList的時(shí)候裝載的數(shù)據(jù)對(duì)象本身。
        previous = p;
        next = n;
    }
}

內(nèi)部還有兩個(gè)迭代器內(nèi)部類：

• LinkIterator
• ReverseLinkIterator

我們看看LinkIterator的內(nèi)部實(shí)現(xiàn)：

Link<ET> link, lastLink;//link當(dāng)前元素，lastLink最后一次訪問(wèn)到元素

//從指定位置開(kāi)始迭代
LinkIterator(LinkedList<ET> object, int location) {
    list = object;//隊(duì)列本身
    //得到原list中的操作記數(shù)。后續(xù)對(duì)list的操作都會(huì)使用到，判別是否存在并發(fā)操作
    if (location >= 0 && location <= list.size) {
    expectedModCount = list.modCount;
        link = list.voidLink;
        //查找的優(yōu)化，根據(jù)索引位置與list的size比較，從頭向尾，還是從末尾向開(kāi)頭開(kāi)始尋找指定位置的元素
        if (location < list.size / 2) {
            for (pos = -1; pos + 1 < location; pos++) {
                link = link.next;
            }
        } else {
            for (pos = list.size; pos >= location; pos--) {
                link = link.previous;
            }
        }
    } else {
        throw new IndexOutOfBoundsException();
    }
}

設(shè)置元素

public void set(ET object) {
    ...
      //lastLink就是最后一個(gè)訪問(wèn)到的元素  
        lastLink.data = object;
    ...  
}

添加元素

public void add(ET object) {
    if (expectedModCount == list.modCount) {
        Link<ET> next = link.next;//當(dāng)前元素的下一個(gè)元素
        Link<ET> newLink = new Link<ET>(object, link, next);//將新添加的數(shù)據(jù)封裝
        link.next = newLink;//link.next指向新元素
        next.previous = newLink;//當(dāng)前元素的下一個(gè)元素的previous指向新元素
        link = newLink;//當(dāng)前的節(jié)點(diǎn)更新為新加入的節(jié)點(diǎn)
        lastLink = null;//最后訪問(wèn)的節(jié)點(diǎn)置為空
        pos++;//這實(shí)際是新添加元素的節(jié)點(diǎn)位置索引值
        //同時(shí)自加LinkedList中的操作次數(shù)和迭代器中的操作次數(shù)，不然肯定會(huì)報(bào)異常，因?yàn)槊看?        //對(duì)list的操作都會(huì)檢查這兩個(gè)值是否相等。
        expectedModCount++;
        list.modCount++;
        list.size++;
    } else {
        throw new ConcurrentModificationException();
    }

public boolean hasNext() {
    return link.next != list.voidLink;//判斷一個(gè)節(jié)點(diǎn)的next域是否指向null，null就說(shuō)明到末尾了
}
//link為空值說(shuō)明沒(méi)有前繼幾點(diǎn)啦，用link.previous != null,可能link==null時(shí)，link.previous會(huì)報(bào)空指針異常。
public boolean hasPrevious() {
    return link != list.voidLink;
}

public ET next() {
    if (expectedModCount == list.modCount) {
        LinkedList.Link<ET> next = link.next;//當(dāng)前元素的下一個(gè)元素
        if (next != list.voidLink) {
            lastLink = link = next;//同時(shí)將保存當(dāng)前節(jié)點(diǎn)和最后訪問(wèn)的節(jié)點(diǎn)更新為剛得到的下一個(gè)元素
            pos++;
            return link.data;
        }
        throw new NoSuchElementException();//已到達(dá)末尾是調(diào)用next，會(huì)拋異常
    }
    throw new ConcurrentModificationException();
}

public ET previous() {
      ...
        lastLink = link;
        link = link.previous;//直接從保存當(dāng)前節(jié)點(diǎn)信息的link的previous域獲得前繼節(jié)點(diǎn)
        pos--;
        return lastLink.data;
      ....
}
//其實(shí)就是add的逆操作，需要注意的是remove操作是將最后訪問(wèn)到的節(jié)點(diǎn)刪除的，也就是lastLink
public void remove() {
    ...
        Link<ET> next = lastLink.next;
        Link<ET> previous = lastLink.previous;
        next.previous = previous;
        previous.next = next;
        //當(dāng)前節(jié)點(diǎn)與最后訪問(wèn)的節(jié)點(diǎn)指向同意元素，next()或者previous()后，該條件為true
        if (lastLink == link) {
            pos--;
        }
        link = previous;//更新當(dāng)前節(jié)點(diǎn)為刪除節(jié)點(diǎn)的前一個(gè)元素
        lastLink = null;
        expectedModCount++;
        list.size--;
        list.modCount++;
      ...
}

add remove next previous set 這五個(gè)操作都會(huì)有以下異常判斷（并發(fā)操作異常）

if (expectedModCount == list.modCount) {
    ...
} else {
    throw new ConcurrentModificationException();
}

ReverseLinkIterator只是LinkIterator的反序迭代而已，理解好LinkIterator就很好理解ReverseLinkIterator了

迭代器都說(shuō)了這么多，下面我們看看LinkedList的主體部分：

//默認(rèn)構(gòu)造方法會(huì)創(chuàng)建一個(gè)空節(jié)點(diǎn)
public LinkedList() {
    voidLink = new Link<E>(null, null, null);//此時(shí)voidLink.previous==voidLink.next==null
    voidLink.previous = voidLink;//指向?qū)ο蟊旧?，保證使用voidLink.previous不會(huì)空指針異常
    voidLink.next = voidLink;
}
public LinkedList(Collection<? extends E> collection) {
    this();//new一個(gè)LinkedList的時(shí)候，總會(huì)調(diào)用到默認(rèn)構(gòu)造方法
    addAll(collection);
}

voidLink是維持整個(gè)list的關(guān)鍵所在，基本每個(gè)操作都離不開(kāi)它　看后面的分析就知道了。

添加元素的時(shí)候邏輯基本和上面迭代器中的邏輯一樣，只是add(E e),offerFirst(E e)內(nèi)部是直接調(diào)用addLastImpl(E e)執(zhí)行添加操作而已，而指定位置的添加注意一點(diǎn)上面提及到根據(jù)插入點(diǎn)的索引與list的size的中點(diǎn)比較，從而選擇從頭開(kāi)始還是從尾開(kāi)始尋找該位置而已。其實(shí)涉及查找的操作都會(huì)使用這個(gè)策略的。

//public void add(int location, E object)的片段而已
if (location < (size / 2)) {
    for (int i = 0; i <= location; i++) {
        link = link.next;
    }
} else {
    for (int i = size; i > location; i--) {
        link = link.previous;
    }
}
----------------------------------------------
public boolean add(E object) {
    return addLastImpl(object);
}

private boolean addLastImpl(E object) {
    Link<E> oldLast = voidLink.previous;
    Link<E> newLink = new Link<E>(object, oldLast, voidLink);
    voidLink.previous = newLink;
    oldLast.next = newLink;
    size++;
    modCount++;
    return true;
}

在addAll方法中國(guó)，插入邏輯是不變的，只是參數(shù)檢查而已

public boolean addAll(Collection<? extends E> collection) {
    int adding = collection.size();
    if (adding == 0) {
        return false;//collection沒(méi)有元素直接返回
    }
    //判斷是不是LinkedList的自己的相同對(duì)象。是的話會(huì)拷貝它所有的元素到ArrayList中。
    Collection<? extends E> elements = (collection == this) ?
            new ArrayList<E>(collection) : collection;

    //由LinkedList的構(gòu)造方法可知，voidLink　== voidLink.previous（初次調(diào)用的時(shí)候）
    //不是第一次調(diào)用時(shí)，voidLink.previous已經(jīng)指向了最后添加的那個(gè)元素了。詳見(jiàn)一下幾行代碼
    Link<E> previous = voidLink.previous;
    //循環(huán)插入collection中的元素
    for (E e : elements) {
        Link<E> newLink = new Link<E>(e, previous, null);
        previous.next = newLink;
        previous = newLink;
    }
    previous.next = voidLink;
    voidLink.previous = previous;
    //至此，會(huì)使得voidLink.next和voidLink.previous都指向最后一個(gè)添加的元素，
    size += adding;
    modCount++;
    return true;
}

我們?cè)賮?lái)看看addFirst的實(shí)現(xiàn)：

public void addFirst(E object) {
    addFirstImpl(object);
}

private boolean addFirstImpl(E object) {
    //第一次addFirstImpl的時(shí)候voidLink.next＝＝voidLink，否則則是上次添加在頭部的節(jié)點(diǎn)
    Link<E> oldFirst = voidLink.next;
    //此時(shí)newLink.previous = voidLink，頭結(jié)點(diǎn)的前繼肯定指向空節(jié)點(diǎn)嘛（不同于c語(yǔ)言指向的是NULL）
    //newLink.next == voidLink.next
    Link<E> newLink = new Link<E>(object, voidLink, oldFirst);
    voidLink.next = newLink;//看到?jīng)]，voidLink.next保存著每次點(diǎn)在在頭部的節(jié)點(diǎn)信息
    oldFirst.previous = newLink;//oldFirst則是上一次添加在頭部的節(jié)點(diǎn)啦，它的previous指向newLink就順理成章啦
    size++;
    modCount++;
    return true;


}

到這里就能搞明白voidLink的previous和next的作用啦，那么其他的操作都是基于這兩個(gè)東西操作的。
以下舉一些例子：

@Override
public boolean contains(Object object) {
    Link<E> link = voidLink.next;//頭節(jié)點(diǎn)
    //注意分兩種情況查找即可
    if (object != null) {
        while (link != voidLink) {
            if (object.equals(link.data)) {
                return true;
            }
            link = link.next;
        }
    } else {
        while (link != voidLink) {
            if (link.data == null) {
                return true;
            }
            link = link.next;
        }
    }
    return false;
}


@Override
public E get(int location) {
    if (location >= 0 && location < size) {
        Link<E> link = voidLink;//這里，下一步就用到next 和　previous了
        if (location < (size / 2)) {
            for (int i = 0; i <= location; i++) {
                link = link.next;
            }
        } else {
            for (int i = size; i > location; i--) {
                link = link.previous;
            }
        }
        return link.data;
    }
    throw new IndexOutOfBoundsException();
}

@Override
public int indexOf(Object object) {
    int pos = 0;
    Link<E> link = voidLink.next;
    ....
｝

再看看幾個(gè)重要的方法：

//會(huì)拋異常
//注意是從頭部移除
public E pop() {
    return removeFirstImpl();
}
//從頭部添加
public void push(E e) {
    addFirstImpl(e);
}
//從頭部移除元素
public E remove() {
    return removeFirstImpl();
}
//沒(méi)有元素返回null
public E poll() {
    return size == 0 ? null : removeFirst();
}
public E peek() {
    return peekFirstImpl();
}

只有poll peek操作遇到LinkedList無(wú)元素返回null，其他做此類型會(huì)拋出異常，其實(shí)現(xiàn)的接口已有說(shuō)明

我們需要主要一下clear():僅是將size置零，voidLink的next,previous指向空元素而已，可見(jiàn)voidLink的作用很關(guān)鍵

public void clear() {
  if (size > 0) {
      size = 0;
      voidLink.next = voidLink;
      voidLink.previous = voidLink;
      modCount++;
  }

通過(guò)以上的分析，基本能理解好LinkedList了。其他具體的方法就不一一貼出來(lái)了，操作原理和上面的分析大同小異。
需要對(duì)每個(gè)方法詳細(xì)的理解，可以直接去看LinkedList的源碼。

均不是線程安全的，并發(fā)操作會(huì)報(bào)異常

you KO LinkedList !!!