LinkedList -> AbstractSequentialList -> List
同時(shí)實(shí)現(xiàn)了接口Deque, Cloneable, Serializable

書同上文，LinkedList就是上學(xué)時(shí)學(xué)的鏈表，很多公司，比如華為的應(yīng)屆基礎(chǔ)面試題很多就是考的這個(gè)，比如鏈表反轉(zhuǎn)，雙向鏈表等。Java openJDK里的LinkedList理念上和這個(gè)并沒(méi)有本質(zhì)區(qū)別，從繼承結(jié)構(gòu)可以看出，這個(gè)LinkedList實(shí)現(xiàn)了List接口，那就是有序的線性結(jié)構(gòu)，同時(shí)也實(shí)現(xiàn)了Deque（讀音，待客）就是雙向鏈表的意思，有head有tail，根據(jù)不同場(chǎng)景可以當(dāng)隊(duì)列和棧來(lái)用。當(dāng)然它的插入刪除都比數(shù)組Array的開銷要小很多，畢竟就只有一些指針的指向變動(dòng)，而數(shù)組是要真的復(fù)制數(shù)據(jù)，移動(dòng)數(shù)據(jù)，有較重的內(nèi)存拷貝等操作，缺點(diǎn)也很明顯，無(wú)法RandomAccess，不可能像數(shù)組一樣做到指哪打哪。這個(gè)來(lái)看看它是如何實(shí)現(xiàn)的，撿重點(diǎn)看。

構(gòu)造 - Constructor

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

內(nèi)部有三個(gè)變量，大小size，head首元素first和tail元素last，Node其實(shí)就是

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

一個(gè)私有靜態(tài)內(nèi)部類，方便內(nèi)部的數(shù)組結(jié)構(gòu)組織，其實(shí)也很簡(jiǎn)單，就三個(gè)要素，節(jié)點(diǎn)的信息item，前一個(gè)節(jié)點(diǎn)指針prev，后一個(gè)節(jié)點(diǎn)指針next。
兩個(gè)構(gòu)造函數(shù)，一個(gè)無(wú)參構(gòu)造器和一個(gè)集合構(gòu)造器簽名為addAll(Collection<? extends E> c)，無(wú)參構(gòu)造器什么也沒(méi)有不談了。重點(diǎn)看下這個(gè)傳入一個(gè)Collection的構(gòu)造器，里面調(diào)用的addAll(size，c)。這個(gè)函數(shù)的意思就是從size所在的index開始把集合c加入到LinkedList中。
要做到這點(diǎn)，首先要定位到這個(gè)index所指向的元素，這里源碼里用了一個(gè)位操作的技巧。

Node<E> node(int index) {
    if (index < (size >> 1)) {
        Node<E> x = first;
        // Iterate & Search
    } else {
        Node<E> x = last;
        // Iterate & Search
    }
}

size >> 1意思就是把size變?yōu)?進(jìn)制然后往右移一位，也就是除以2，這個(gè)其實(shí)就是為了判斷這個(gè)index是更靠近head還是tail，如果小于中間的index，那就從head找，否則從tail找。找到這個(gè)node后，后面就很簡(jiǎn)單了，把要插入的node的prev指向這個(gè)節(jié)點(diǎn)的prev，以此類推可以把整個(gè)collection插入進(jìn)去，其實(shí)就是頭插法，最后把collection的最后一個(gè)元素的next指向之前找到的這個(gè)node，然后再把node的prev指向collection里的最后一個(gè)元素，完成。整個(gè)LinkedList的size和modCount都要變，size變?yōu)樵笮〖觕ollection的大小之和，modCount加一。這里再說(shuō)下這個(gè)modCount，它存在的目的就是為了避免多個(gè)修改集合的操作導(dǎo)致臟讀，設(shè)計(jì)原則是fast-fail，如果在遍歷期間有其他操作改變了這個(gè)集合，那么在下次取操作時(shí)立刻拋出異常告訴用戶這個(gè)集合改變了，無(wú)法繼續(xù)遍歷。

增 - Add

一共三個(gè)方法

public boolean add(E e)
public void add(int index, E element)
public void addFirst(E e)
public void addLast(E e)
public boolean addAll(Collection<? extends E> c)

這里addAll因?yàn)橹疤徇^(guò)了就不再進(jìn)一步討論了，add(E e)有兩個(gè)版本一個(gè)是尾插法，直接把node插入到尾部，也可以利用addAll，傳入尾部的index做插入。add(index，element)如果index不是size的話，就在這個(gè)元素之前做插入，如果是size的話就在tail后再插入一個(gè)新節(jié)點(diǎn)。addFirst就是頭插法，在head之前插入一個(gè)節(jié)點(diǎn)，然后把這個(gè)節(jié)點(diǎn)變?yōu)閔ead，addLast與之相反。

刪 - Remove

public E remove()

默認(rèn)刪除head元素，如果有的話把head下一個(gè)元素變?yōu)閔ead，同時(shí)把head的prev和next都指向null，幫助GC回收內(nèi)存。

E remove(int index)

刪除指定index的元素，利用之前提到的方法定位到元素，再用同樣的方法把該節(jié)點(diǎn)prev和next都置null。

public boolean remove(Object o)

如果object為null，刪除第一個(gè)item為null的節(jié)點(diǎn)，如果不為空，則刪除滿足equals(object)的節(jié)點(diǎn)。
還有removeFirst和removeLast，其實(shí)就是判斷head和tail，如果不為空則刪除。至于像removeFirstOccurrence和removeLastOccurrence，一個(gè)從前往后找，一個(gè)從后往前找，找打就刪掉該節(jié)點(diǎn)。

改 - update/replace

LinkedList里沒(méi)有replace方法，也沒(méi)有update方法，但有set方法。當(dāng)然你也可以創(chuàng)建一個(gè)新節(jié)點(diǎn)，然后把這個(gè)節(jié)點(diǎn)插入進(jìn)去并刪除原有的節(jié)點(diǎn)?；蛘哒业揭薷牡墓?jié)點(diǎn)，然后修改節(jié)點(diǎn)內(nèi)部的item。還有個(gè)replaceAll，來(lái)自List接口的default實(shí)現(xiàn)，傳入一個(gè)UnaryOperator，對(duì)集合的所有元素做一個(gè)mapping轉(zhuǎn)換操作。set方法原理類似，只不過(guò)需要指定下標(biāo)index，然后用新節(jié)點(diǎn)替換這個(gè)index所在的節(jié)點(diǎn)。

查 - get/read

public E get(int index)

利用前文提到的node方法，找到指定下標(biāo)的節(jié)點(diǎn)并返回。
getFirst和getLast原理很簡(jiǎn)單，這里不贅述了，就是返回head和tail，如果為null就拋出NoSuchElementException。

offer & poll

生產(chǎn)者消費(fèi)者模型，相關(guān)的方法還有peek，take，remove，add，put等。叫法大同小異。因?yàn)長(zhǎng)inkedList實(shí)現(xiàn)了Deque，所以是有頭有尾的雙向鏈表，生產(chǎn)者可以不停的做尾插法往tail加入node，消費(fèi)者可以不停的從head取走并刪除元素。offer就是生產(chǎn)者，提供一個(gè)node，poll就是消費(fèi)者，取走一個(gè)node。在LinkedList里的offer和poll是非阻塞的，如果call的時(shí)候沒(méi)有元素可以poll那么就返回null。當(dāng)然也可以繼承這個(gè)LinkedList把這個(gè)改造成阻塞的版本，加一個(gè)timeout即可。后面在講BlockingQueue的時(shí)候會(huì)細(xì)講，這里不展開。

push & pop

典型的棧操作，默認(rèn)實(shí)現(xiàn)是從頭部插入，從頭部刪除，這里不贅述了。

以上就是LinkedList里所有的比較重要的方法和用法。