按照從構(gòu)造方法->常用API（增、刪、改、查）的順序來(lái)閱讀源碼，并會(huì)講解閱讀方法中涉及的一些變量的意義。

• ArrayList與LinkedList
  ArrayList與LinkedList是List接口的兩種不同的實(shí)現(xiàn)，ArrayList的增刪效率低，但是改查效率高。
  而LinkedList正好相反，增刪由于不需要移動(dòng)底層數(shù)組數(shù)據(jù)，其底層是鏈表實(shí)現(xiàn)的，只需要修改鏈表節(jié)點(diǎn)指針，所以效率較高。
  而改和查，都需要先定位到目標(biāo)節(jié)點(diǎn)，所以效率較低。
• Collection.toArray(); 。
  這個(gè)方法很重要，不管是ArrayList、LinkedList 在批量add的時(shí)候，都會(huì)先轉(zhuǎn)化成數(shù)組去做。 因?yàn)閿?shù)組可以用for循環(huán)直接花式遍歷。比較方便 高效

一. 定義

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

• 實(shí)現(xiàn) List 接口
  能對(duì)它進(jìn)行隊(duì)列操作
• 實(shí)現(xiàn) Deque 接口
  即能將LinkedList當(dāng)作雙端隊(duì)列使用
• 實(shí)現(xiàn)了Cloneable接口
  即覆蓋了函數(shù)clone()，能克隆
• 實(shí)現(xiàn)java.io.Serializable接口
  支持序列化，能通過(guò)序列化去傳輸

二. 屬性

主要有三個(gè)：

• size：當(dāng)前有多少個(gè)節(jié)點(diǎn)
• first：第一個(gè)節(jié)點(diǎn)
• last：最后一個(gè)節(jié)點(diǎn)

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

Node<E>

雙向鏈表。

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òu)造方法

1）無(wú)參構(gòu)造方法

public LinkedList() {
}

什么都沒(méi)做，表示初始化的時(shí)候size為0，first和last的節(jié)點(diǎn)都為空：

2）Collection對(duì)象作為入?yún)?/h2>

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

四. 增加---add addAll

添加一個(gè)元素(在末尾)--add(E e)

在尾部插入一個(gè)節(jié)點(diǎn)： add

add(E e)

Appends the specified element to the end of this list.

public boolean add(E e) {
    linkLast(e);
    return true;
}

linkLast(E e)

生成新節(jié)點(diǎn) 并插入到 鏈表尾部， 更新 last/first 節(jié)點(diǎn)。
只用維護(hù)前面的鏈子

void linkLast(E e) {
    final Node<E> l = last;//記錄原尾部節(jié)點(diǎn)
    final Node<E> newNode = new Node<>(l, e, null);//以原尾部節(jié)點(diǎn)為新節(jié)點(diǎn)的前置節(jié)點(diǎn)
    last = newNode;//更新尾部節(jié)點(diǎn)
    if (l == null)//若原鏈表為空鏈表，需要 額外 更新頭結(jié)點(diǎn)
        first = newNode;
    else//否則更新原尾節(jié)點(diǎn)的后置節(jié)點(diǎn)為 新節(jié)點(diǎn) 
        l.next = newNode;
    size++;
    modCount++;
}

在指定位置添加一個(gè)元素--add(int index, E element)

public void add(int index, E element) {
    checkPositionIndex(index);//檢查下標(biāo)是否越界[0,size]
    if (index == size)//在尾節(jié)點(diǎn)后插入
        linkLast(element);
    else//在中間插入
        linkBefore(element, node(index));
}

linkBefore(E e, Node<E> succ)

在succ節(jié)點(diǎn)前，插入一個(gè)新節(jié)點(diǎn)e
重新維護(hù)前后兩條鏈子

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev; //保存后置節(jié)點(diǎn)的前置節(jié)點(diǎn)
    final Node<E> newNode = new Node<>(pred, e, succ); //構(gòu)建一個(gè)新節(jié)點(diǎn)
    //插在succ前
    succ.prev = newNode;//新節(jié)點(diǎn)newNode是原節(jié)點(diǎn)succ的前置節(jié)點(diǎn)
    //如果之前的前置節(jié)點(diǎn)是空，說(shuō)明succ是原頭結(jié)點(diǎn)。所以新節(jié)點(diǎn)是現(xiàn)在的頭結(jié)點(diǎn)
    if (pred == null)
        first = newNode;
    else//否則新節(jié)點(diǎn)是pred的后繼節(jié)點(diǎn)
        pred.next = newNode;
    size++;//修改數(shù)量
    modCount++;
}

在尾部批量增加---addAll(Collection<? extends E> c)

Appends all of the elements in the specified collection to the end of this list

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);//以size為插入下標(biāo)，插入集合c中所有元素
}

在尾部批量增加---addAll(int index, Collection<? extends E> c)

以size為插入下標(biāo)，插入集合c中所有元素

1. 判斷加在隊(duì)尾還是中間（為了找到插入后的前驅(qū)后繼節(jié)點(diǎn)，在插入前的位置）
2. 循環(huán)加入元素
   2.1從前驅(qū)節(jié)點(diǎn)進(jìn)行后接
   2.2設(shè)置為前驅(qū)的后繼
   2.3當(dāng)前節(jié)點(diǎn)設(shè)置為下一節(jié)點(diǎn)的前驅(qū)-
3. 判斷加在隊(duì)尾還是中間（為了判斷l(xiāng)ast位置，和設(shè)置新的前驅(qū)后繼）

public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);//檢查越界 [0,size] 閉區(qū)間
    Object[] a = c.toArray();//拿到目標(biāo)集合數(shù)組
    int numNew = a.length;
    if (numNew == 0)//如果新增元素?cái)?shù)量為0，則不增加，并返回false
        return false;
    //successor and predecessor---------------------------
    Node<E> pred, succ;//index節(jié)點(diǎn)的前置節(jié)點(diǎn)，后置節(jié)點(diǎn)
    if (index == size) { //在鏈表尾部追加數(shù)據(jù)
        succ = null;//size節(jié)點(diǎn)（隊(duì)尾）的后置節(jié)點(diǎn)一定是null
        pred = last;//前置節(jié)點(diǎn)是隊(duì)尾
    } else {
        succ = node(index);//取出index節(jié)點(diǎn)，作為后置節(jié)點(diǎn)
        pred = succ.prev;//前置節(jié)點(diǎn)是，index節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
    }
     //for循環(huán)遍歷原數(shù)組，依次執(zhí)行插入節(jié)點(diǎn)操作，對(duì)鏈表批量增加
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        //之前的最后一個(gè)節(jié)點(diǎn)是現(xiàn)在的前驅(qū)節(jié)點(diǎn)
    //1. 從前驅(qū)節(jié)點(diǎn)進(jìn)行后接----------------
        Node<E> newNode = new Node<>(pred, e, null);
    //2. 設(shè)置為前驅(qū)的后繼----------------------------
        if (pred == null)//如果前置節(jié)點(diǎn)是空，說(shuō)明是頭結(jié)點(diǎn)
            first = newNode;
        else//否則 新節(jié)點(diǎn)是前置節(jié)點(diǎn)的后置節(jié)點(diǎn)
            pred.next = newNode;
    //3. 當(dāng)前節(jié)點(diǎn)設(shè)置為下一節(jié)點(diǎn)的前驅(qū)----------------
        pred = newNode;//步進(jìn)，當(dāng)前的節(jié)點(diǎn)為前置節(jié)點(diǎn)了，為下次添加節(jié)點(diǎn)做準(zhǔn)備
    }
    //循環(huán)結(jié)束后，判斷
    if (succ == null) {//在隊(duì)尾添加的
        last = pred; //last節(jié)點(diǎn)發(fā)生變化
    } else {// 否則是在隊(duì)中插入的節(jié)點(diǎn)
        pred.next = succ; //接尾
        succ.prev = pred;//接頭
    }
    size += numNew;
    modCount++;
    return true;
}

根據(jù)index 查詢出Node---node(int index)

Returns the (non-null) Node at the specified element index.

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;
    }
}

范圍判定

private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

五. 刪除---remove

• 按下標(biāo)刪，是先根據(jù)index找到Node，然后去鏈表上unlink掉這個(gè)Node
• 按元素刪，會(huì)先去遍歷鏈表尋找是否有該Node，考慮到允許null值，所以會(huì)遍歷兩遍，然后再去unlink它

刪除頭--remove()

public E remove() {
    return removeFirst();
}

removeFirst()

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

unlinkFirst(f)

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

根據(jù)索引位置刪除元素--remove(int index)

Removes the element at the specified position in this list

public E remove(int index) {
    checkElementIndex(index);//檢查是否越界 下標(biāo)[0,size)
    return unlink(node(index));//從鏈表上刪除某節(jié)點(diǎn)
}

unlink(Node<E> 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) { //如果前驅(qū)節(jié)點(diǎn)為空，說(shuō)明當(dāng)x原本是頭結(jié)點(diǎn)
        first = next; //則頭結(jié)點(diǎn)等于后置節(jié)點(diǎn) 
    } else { //----------改后連接
        prev.next = next;
        x.prev = null;  //將當(dāng)前節(jié)點(diǎn)的 前置節(jié)點(diǎn)置空
    }

    if (next == null) {//如果后繼節(jié)點(diǎn)為空，說(shuō)明x原本是尾節(jié)點(diǎn)
        last = prev; //則 尾節(jié)點(diǎn)為前置節(jié)點(diǎn)
    } else {//---------改前連接
        next.prev = prev;
        x.next = null;//將當(dāng)前節(jié)點(diǎn)的 后置節(jié)點(diǎn)置空
    }

    x.item = null; 
    size--; 
    modCount++;  
    return element; 
}

根據(jù)元素內(nèi)容刪除，只刪除匹配的第一個(gè)

remove(Object o)

Removes the first occurrence of the specified element from this list, if it is present.

• null值要用==比較

public boolean remove(Object o) {
    if (o == null) {//如果要?jiǎng)h除的是null節(jié)點(diǎn)
        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;
}

六. 查找---get

查詢節(jié)點(diǎn)---get(int index)

Returns the element at the specified position in this list.

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;//調(diào)用node()方法 取出 Node節(jié)點(diǎn)
}

查詢下標(biāo)---indexOf(Object o)

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

7. 更新---set

將指定位置的元素更新為新元素

Replaces the element at the specified position in this list with the specified element.

• 注意返回值是oldValue

public E set(int index, E element) {
    checkElementIndex(index); 
    Node<E> x = node(index);
    E oldVal = x.item;//保存舊值 供返回
    x.item = element;//覆蓋舊值
    return oldVal;
}

9. toArray()

new 一個(gè)新數(shù)組 然后遍歷鏈表，將每個(gè)元素存在數(shù)組里，返回

Returns an array containing all of the elements in this list in proper sequence (from first to last element).

public Object[] toArray() {
     Object[] result = new Object[size];
     int i = 0;
     for (Node<E> x = first; x != null; x = x.next)
         result[i++] = x.item;
     return result;
}

10. LinkedList和 ArrayList的區(qū)別

• 增刪效率比ArrayList高
  底層數(shù)據(jù)結(jié)構(gòu)是鏈表，增刪只需要移動(dòng)指針即可故時(shí)間效率較高。不需要批量擴(kuò)容，也不需要預(yù)留空間，所以空間效率比ArrayList高。
• 查效率比ArrayList低
  缺點(diǎn)就是需要隨機(jī)訪問(wèn)元素時(shí)，時(shí)間效率很低，雖然底層在根據(jù)下標(biāo)查詢Node的時(shí)候，會(huì)根據(jù)index判斷目標(biāo)Node在前半段還是后半段，然后決定是順序還是逆序查詢，以提升時(shí)間效率?？傮w時(shí)間效率依然O(n)

11. 小總結(jié)

它的CRUD操作里，都涉及到根據(jù)index去找到Node的操作

• 鏈表批量增加，是靠for循環(huán)遍歷原數(shù)組，依次執(zhí)行插入節(jié)點(diǎn)操作
  對(duì)比ArrayList是通過(guò)System.arraycopy完成批量增加的
• 通過(guò)下標(biāo)獲取某個(gè)node 的時(shí)候，會(huì)根據(jù)index處于前半段還是后半段進(jìn)行一個(gè)折半，以提升查詢效率
• 按下標(biāo)刪是先根據(jù)index找到Node，然后去鏈表上unlink掉這個(gè)Node
  按元素刪，會(huì)先去遍歷鏈表尋找是否有該Node，如果有，去鏈表上unlink掉這個(gè)Node
• 改也是先根據(jù)index找到Node，然后替換值。改不修改modCount。
• 查本身就是根據(jù)index找到Node。

參考文章
Java集合干貨系列-（二）LinkedList源碼解析
Java官方文檔
LinkedList源碼解析（JDK8）