慣例，笑話開頭。

哈哈哈

閱讀本文你可以掌握，LinkedList 相關(guān)知識點(diǎn)和細(xì)節(jié)。

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

鏈表的特點(diǎn)

1，鏈表查詢數(shù)據(jù)，需要遍歷整個鏈表，即便是做了優(yōu)化，判斷當(dāng)前index，確定從前邊遍歷或者從后邊遍歷，時間復(fù)雜度仍是O(n)。
2，鏈表插入和刪除的，首先需要找到當(dāng)前插入的點(diǎn)，也需要遍歷鏈表，然后把節(jié)點(diǎn)指針相連，所以時間復(fù)雜度也是O(n);但是為什么都說鏈表更適合插入和刪除呢，因為鏈表查找的時間要比移動數(shù)據(jù)快很多。
3 ，內(nèi)存利用率高，不會浪費(fèi)內(nèi)存（數(shù)組需要提前分配內(nèi)存，鏈表則不需要，而且沒有大小限制，內(nèi)存也可以不連續(xù)）

單鏈表和雙鏈表

單鏈表
缺點(diǎn)：每個節(jié)點(diǎn)只有一個next指針，只能一種遍歷方式，
優(yōu)點(diǎn)：單鏈表存儲一個節(jié)點(diǎn)，就比較節(jié)省內(nèi)存，當(dāng)節(jié)點(diǎn)N無線大的時候，節(jié)省的內(nèi)存還是挺可觀的。
雙鏈表
優(yōu)點(diǎn)：每個節(jié)點(diǎn)有兩個指針，可以從前邊或者從后邊遍歷，利用二分查找，所以理論上雙鏈表遍歷效率是比單鏈表快的，
缺點(diǎn)：但是相對單鏈表來說占用內(nèi)存相對較大

LinkedList源碼解析

Node 節(jié)點(diǎn)代碼

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

成員屬性

 transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

為什么定義兩個節(jié)點(diǎn)？

如果只有一個頭節(jié)點(diǎn)，添加數(shù)據(jù)就需要從頭結(jié)點(diǎn)遍歷拿到最后一個節(jié)點(diǎn)，這樣時間復(fù)雜度O(n)，數(shù)據(jù)量龐大的時候效果非常明顯，定義一個last節(jié)點(diǎn)，添加單個數(shù)據(jù)的時間復(fù)雜度就變成了O(1).

 void linkBefore(E e) {

        Node newNode = new Node(e, null);
        Node next = first;

        if (next ==null){
            first =newNode;
        }else{
            //遍歷找到最后一個節(jié)點(diǎn)
            for (int i = 0; i < size; i++){
                next = next.next;
            }
            next.next =newNode;
        }
  size++;
    }
這種寫法 每次添加數(shù)據(jù)的時候需要找到最后一個節(jié)點(diǎn)，時間復(fù)雜度O(n)；

    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++;
    }
定義一個last節(jié)點(diǎn)，添加就變成了O(1)級別

構(gòu)造方法

    public LinkedList() {
    }

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

第二種，把當(dāng)前數(shù)據(jù)轉(zhuǎn)換成數(shù)組，然后遍歷數(shù)組，創(chuàng)建Node節(jié)點(diǎn)添加到鏈表中。

為什么使用雙鏈表？

單鏈表遍歷只能一個方向遍歷，時間復(fù)雜度O(n),使用雙鏈表可以兩個方向遍歷，時間復(fù)雜度O(n/2),當(dāng)N足夠大其實也是O(n)，但是這樣實際減少了遍歷消耗。

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

面試知識

LinkdeList 面試大部分是對比ArrayList 來的。
1，為什么實現(xiàn)不是單鏈表
答 ：空間換時間，消耗了一定空間，遍歷的時候速度相對來說加快一倍。
2，為什么定義兩個節(jié)點(diǎn)？
答：優(yōu)化了添加的時間復(fù)雜度，一個節(jié)點(diǎn)需要遍歷找到最后的節(jié)點(diǎn)，定義一個尾節(jié)點(diǎn)，使得添加時間復(fù)雜度從O(n)降低為O(1);
3，什么時候使用Arraylist 什么時候使用lindekList？
答：如果需要頻繁移除或者中間插入這種，arraylist都需要調(diào)用arraycopy比較消耗性能，這種時候需要考慮linkedlist，如果只是遍歷就用arraylist 查詢級別O(1)；linkedlist查詢雖然做了優(yōu)化，(二分查找) 但是數(shù)據(jù)足夠大還是o(n)級別。