本文原創(chuàng)地址，我的博客：https://jsbintask.cn/2019/03/26/jdk/jdk8-linkedlist/(食用效果最佳)拱雏，轉(zhuǎn)載請(qǐng)注明出處!

前言

LinkedList內(nèi)部是一個(gè)鏈表的實(shí)現(xiàn)帘皿，一個(gè)節(jié)點(diǎn)除了保持自身的數(shù)據(jù)外晾匠，還持有前后专，后兩個(gè)節(jié)點(diǎn)的引用禁舷。所以就數(shù)據(jù)存儲(chǔ)上來(lái)說(shuō)拦键，它相比使用數(shù)組作為底層數(shù)據(jù)結(jié)構(gòu)的ArrayList來(lái)說(shuō)谣光，會(huì)更加耗費(fèi)空間。但也正因?yàn)檫@個(gè)特性芬为，它刪除萄金，插入節(jié)點(diǎn)很快！LinkedList沒(méi)有任何同步手段媚朦，所以多線程環(huán)境須慎重考慮氧敢，可以使用Collections.synchronizedList(new LinkedList(...));保證線程安全。

LinkedList

友情鏈接：jdk1.8 ArrayList源碼全分析

LinkedList結(jié)構(gòu)

類(lèi)關(guān)系

LinkedList

類(lèi)成員

LinkedList

LinkedList

源碼解析

add(E e)方法

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

這個(gè)方法直接調(diào)用linkLast:

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

我們用作圖來(lái)解釋下這個(gè)方法的執(zhí)行過(guò)程窥妇，一開(kāi)始舷胜，first和last都為null，此時(shí)鏈表什么都沒(méi)有活翩，當(dāng)?shù)谝淮握{(diào)用該方法后逞带，first和last均指向了第一個(gè)新加的節(jié)點(diǎn)E1：

LinkedList

接著，第二次調(diào)用該方法纱新，加入新節(jié)點(diǎn)E2。首先穆趴，將last引用賦值給l脸爱，接著new了一個(gè)新節(jié)點(diǎn)E2，并且E2的prve指向l未妹，接著將新節(jié)點(diǎn)E2賦值為last〔痉希現(xiàn)在結(jié)構(gòu)如下：

LinkedList

LinkedList

接著size+1族檬，modCount+1歪赢，退出該方法，局部變量l銷(xiāo)毀单料，所以現(xiàn)在數(shù)據(jù)結(jié)構(gòu)如下：

LinkedList

add(int index, E element) 這個(gè)方法是在指定位置插入新元素

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

1. index位置檢查（不能小于0，大于size）
2. 如果index==size扫尖，直接在鏈表最后插入白对，相當(dāng)于調(diào)用add(E e)方法
3. 小于size，首先調(diào)用node方法將index位置的節(jié)點(diǎn)找出换怖，接著調(diào)用linkBefore

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

我們同樣作圖分析甩恼，假設(shè)現(xiàn)在鏈表中有三個(gè)節(jié)點(diǎn)，調(diào)用node方法后找到的第二個(gè)節(jié)點(diǎn)E2沉颂，則進(jìn)入方法后条摸，結(jié)構(gòu)如下：

LinkedList

接著，將succ的prev賦值給pred铸屉，并且構(gòu)造新節(jié)點(diǎn)E4钉蒲，E4的prev和next分別為pred和suc，同時(shí)將新節(jié)點(diǎn)E4賦值為succ的prev引用抬探，則現(xiàn)在結(jié)構(gòu)如下：

LinkedList

LinkedList

最后小压，size+1线梗，modCount+1，推出方法怠益，本地變量succ仪搔，pred銷(xiāo)毀，最后結(jié)構(gòu)如下：

LinkedList

E get(int index)獲取指定節(jié)點(diǎn)數(shù)據(jù)

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

直接調(diào)用node方法：

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

1. 判斷index在鏈表的哪邊。
2. 遍歷查找index或者size-index次抱虐，找出對(duì)應(yīng)節(jié)點(diǎn)昌阿。
   這里我們知道，相比于數(shù)組的直接索引獲取，遍歷獲取節(jié)點(diǎn)效率并不高懦冰。

E remove(int index)移除指定節(jié)點(diǎn)

public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

1. 檢查index位置
2. 調(diào)用node方法獲取節(jié)點(diǎn)灶轰，接著調(diào)用unlink(E e)

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

這個(gè)方法就不做分析了，其原理就是將當(dāng)前節(jié)點(diǎn)X的前一個(gè)節(jié)點(diǎn)P的next直接指向X的下一個(gè)節(jié)點(diǎn)D刷钢，這樣X(jué)就不再關(guān)聯(lián)任何引用笋颤，等待垃圾回收即可。
這里我們同樣知道内地，相比于ArrayList的copy數(shù)組覆蓋原來(lái)節(jié)點(diǎn)伴澄，效率同樣更高！

到現(xiàn)在瓤鼻，我們關(guān)于鏈表的核心方法秉版，增刪改都分析完畢，最后介紹下它實(shí)現(xiàn)的隊(duì)列Deque的各個(gè)方法：

LinkedList

• add(E e):隊(duì)尾插入新節(jié)點(diǎn)茬祷，如果隊(duì)列空間不足清焕，拋出異常；LinkedList沒(méi)有空間限制祭犯，所以可以無(wú)限添加秸妥。
• offer(E e):隊(duì)尾插入新節(jié)點(diǎn)，空間不足沃粗，返回false粥惧，在LinkedList中和add方法同樣效果。
• remove():移除隊(duì)頭節(jié)點(diǎn)最盅，如果隊(duì)列為空（沒(méi)有節(jié)點(diǎn)突雪，first為null），拋出異常涡贱。LinkedList中就是first節(jié)點(diǎn)（鏈表頭）
• poll()：同remove咏删，不同點(diǎn)：隊(duì)列為空，返回null
• element()：查詢隊(duì)頭節(jié)點(diǎn)(不移除)问词，如果隊(duì)列為空督函，拋出異常。
• peek()：同element激挪，不同點(diǎn)：隊(duì)列為空辰狡，返回null。

總結(jié)

1. LinkedList內(nèi)部使用鏈表實(shí)現(xiàn)垄分，相比于ArrayList更加耗費(fèi)空間宛篇。
2. LinkedList插入，刪除節(jié)點(diǎn)不用大量copy原來(lái)元素薄湿，效率更高叫倍。
3. LinkedList查找元素使用遍歷豌鸡，效率一般。
4. LinkedList同時(shí)是雙向隊(duì)列的實(shí)現(xiàn)段标。

關(guān)注我，這里只有干貨炉奴！