實(shí)現(xiàn)：

基于鏈表的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，實(shí)現(xiàn)了List和Deque接口，有List和隊(duì)列的特性，底層實(shí)現(xiàn)是一個(gè)雙端鏈表，內(nèi)部有個(gè)私有類Node，如下：

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

增刪改查都是通過(guò)操作該類中item(當(dāng)前節(jié)點(diǎn))、prev(前驅(qū)節(jié)點(diǎn))、next(后繼結(jié)點(diǎn))實(shí)現(xiàn)。

特性：

1. 插入和刪除效率比較高
2. 繼承了隊(duì)列的先進(jìn)先出以及擁有棧的先進(jìn)后出特性
3. 保存了next和prev指針，浪費(fèi)空間
4. 線程不安全

源碼解析：

結(jié)構(gòu)

每個(gè)節(jié)點(diǎn)都保存了上/下節(jié)點(diǎn)的指針，第一個(gè)節(jié)點(diǎn)的prev和最后一個(gè)節(jié)點(diǎn)的next都為空，這就是LinkedList內(nèi)部的結(jié)構(gòu)。

接下來(lái)我們從源碼角度分析add流程，get和remove這里不分析，與add是類似的。
通過(guò)Ctrl+鼠標(biāo)左鍵進(jìn)入到LinkedList源碼中，搜索add(index, E element)方法，先看該方法：

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

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

調(diào)用checkPositionIndex,去檢查index是否合法，不合法直接拋出異常，然后判斷index是不是最后一個(gè)元素，如果是，調(diào)用linkLast(element)方法，否則調(diào)用linkBefore(element, node(index))將該元素插入index前。

我們來(lái)看LinkLast(element)源碼：

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

先用一個(gè)局部變量l保存當(dāng)前表中最后一個(gè)元素last，然后新建一個(gè)節(jié)點(diǎn)newNode，將l當(dāng)成newNode的prev節(jié)點(diǎn)，next節(jié)點(diǎn)為空(請(qǐng)參考上面鏈表結(jié)構(gòu)圖)，然后將newNode指向last，完成最后一個(gè)節(jié)點(diǎn)的插入，如果l是空的，說(shuō)明該鏈表之前就是個(gè)空列表，first節(jié)點(diǎn)也應(yīng)該為newNode，如果不是，則需要更新l.next的指向，將l.next指向newNode，關(guān)聯(lián)上鏈表，最后size加1.

接著看linkBefore(element, node(index))方法，我們先看他的第2個(gè)參數(shù)，需要通過(guò)index去查找到要插入的Node節(jié)點(diǎn)，這里通過(guò)node(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;
        }
    }

我們可以看到這里查找并不是一個(gè)一個(gè)去查的，而是將整個(gè)列表折半，看index在哪個(gè)區(qū)間，提升了一點(diǎn)效率。
接下來(lái)我們?cè)倏磍inkBefore(element, succ)方法本身，上源碼：

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

這里我們先將要插入節(jié)點(diǎn)的succ.prev保存到pred中，然后創(chuàng)建一個(gè)新節(jié)點(diǎn)newNode，該節(jié)點(diǎn)就是要插入的節(jié)點(diǎn)，所以該新節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)就是pred,當(dāng)前節(jié)點(diǎn)就是element,后繼結(jié)點(diǎn)就是succ本身，將newNode放到succ.prev中，節(jié)點(diǎn)就插入進(jìn)去了，然后判斷pred是不是為null,如果是，說(shuō)明列表之前是空的，first節(jié)點(diǎn)就是newNode,如果不是，需要指定pred.next節(jié)點(diǎn)為newNode。
這樣就完成了一個(gè)Node插入到指定的位置中，其他操作基本都是這樣實(shí)現(xiàn)的。