LinkedList是一個(gè)實(shí)現(xiàn)了List接口和Deque接口的雙端鏈表。
有關(guān)索引的操作可能從鏈表頭開(kāi)始遍歷到鏈表尾部，也可能從尾部遍歷到鏈表頭部，這取決于看索引更靠近哪一端

LinkedtList內(nèi)部的成員變量如下:

    transient int size = 0;
    
    transient Node<E> first;  //指向鏈表頭部
    
    transient Node<E> last; //指向鏈表尾部

其中size表示當(dāng)前鏈表中的數(shù)據(jù)個(gè)數(shù)。下面是Node節(jié)點(diǎn)的定義，Node類LinkedList的靜態(tài)內(nèi)部類:

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

add(E e)

add(E e)用于將元素添加到鏈表尾部，實(shí)現(xiàn)如下:

    public boolean add(E e) {
            linkLast(e);
            return true;
        }
    
    void linkLast(E e) {
            final Node<E> l = last;//指向鏈表尾部
            final Node<E> newNode = new Node<>(l, e, null);//以尾部為前驅(qū)節(jié)點(diǎn)創(chuàng)建一個(gè)新節(jié)點(diǎn)
            last = newNode;//將鏈表尾部指向新節(jié)點(diǎn)
            if (l == null)//如果鏈表為空，那么該節(jié)點(diǎn)既是頭節(jié)點(diǎn)也是尾節(jié)點(diǎn)
                first = newNode;
            else//鏈表不為空，那么將該結(jié)點(diǎn)作為原鏈表尾部的后繼節(jié)點(diǎn)
                l.next = newNode;
            size++;//增加尺寸
            modCount++;
        }

從上面代碼可以看到，linkLast方法中就是一個(gè)鏈表尾部添加一個(gè)雙端節(jié)點(diǎn)的操作，但是需要注意對(duì)鏈表為空時(shí)頭節(jié)點(diǎn)的處理

add(int index,E e)

add(int index,E e)用于在指定位置添加元素。實(shí)現(xiàn)如下：

    public void add(int index, E element) {
            checkPositionIndex(index); //檢查索引是否處于[0-size]之間
    
            if (index == size)//如果要插入的索引位置就是鏈表的長(zhǎng)度，就添加在鏈表尾部
                linkLast(element);
            else//添加在鏈表指定位置
                linkBefore(element, node(index));
        }

從上面代碼可以看到，主要分為3步：

1. 檢查index的范圍，否則拋出異常
2. 如果插入位置是鏈表尾部，那么調(diào)用linkLast方法
3. 如果插入位置是鏈表之間，那么調(diào)用linkBefore方法

linkLast方法前面已經(jīng)討論了，下面看一下linkBefore的實(shí)現(xiàn)。在看linkBefore之前，先看一下node(int index)方法，該方法返回指定位置的節(jié)點(diǎn)，實(shí)現(xiàn)如下：

    Node<E> node(int index) {
            // assert isElementIndex(index);
    
            //如果索引位置靠鏈表前半部分，從頭開(kāi)始遍歷
            if (index < (size >> 1)) {
                Node<E> x = first;
                for (int i = 0; i < index; i++)
                    x = x.next;
                return x;
            }
            //否則，從尾開(kāi)始遍歷
            else {
                Node<E> x = last;
                for (int i = size - 1; i > index; i--)
                    x = x.prev;
                return x;
            }
        }

從上面可以看到，node(int index)方法將根據(jù)index是靠近頭部還是尾部選擇不同的遍歷方向。一旦得到了指定索引位置的節(jié)點(diǎn)，再看linkBefore()方法，實(shí)現(xiàn)如下：

    void linkBefore(E e, Node<E> succ) {
            // assert succ != null;
            final Node<E> pred = succ.prev; //找到指定位置的節(jié)點(diǎn)的前一個(gè)位置的節(jié)點(diǎn)
            final Node<E> newNode = new Node<>(pred, e, succ);  //創(chuàng)建新的節(jié)點(diǎn)
            succ.prev = newNode;  //這個(gè)新節(jié)點(diǎn)就是要插入元素的節(jié)點(diǎn)，變成指定位置的前一個(gè)節(jié)點(diǎn)
            if (pred == null)
                first = newNode;  //如果指定位置前一個(gè)沒(méi)有節(jié)點(diǎn)，則新節(jié)點(diǎn)變成第一個(gè)節(jié)點(diǎn)
            else
                pred.next = newNode; //前一個(gè)有節(jié)點(diǎn)則讓前一個(gè)節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)指向新節(jié)點(diǎn)，也就是新節(jié)點(diǎn)就在pred和succ節(jié)點(diǎn)之間了
            size++;
            modCount++;
        }

從上圖以及代碼可以看到linkBefore主要分三步：

1. 創(chuàng)建newNode節(jié)點(diǎn)，將newNode的后繼指針指向succ，前驅(qū)指針指向pred
2. 將succ的前驅(qū)指針指向newNode
3. 根據(jù)pred是否為null，進(jìn)行不同操作。

• 如果pred為null，說(shuō)明該節(jié)點(diǎn)插入在頭節(jié)點(diǎn)之前，要重置first頭節(jié)點(diǎn)
• 如果pred不為null，那么直接將pred的后繼指針指向newNode即可