Java LinkedList原始碼剖析（圖）

總體介紹

LinkedList同時實作了List介面和Deque接口，也就是說它既可以看作一個順序容器，又可以看作一個佇列（Queue），同時又可以看作一個堆疊（Stack）。這樣看來，LinkedList簡直就是個全能冠軍。當你需要使用堆疊或佇列的時候，首先應該考慮的就是LinkedList。因為Java官方已經聲明不建議使用Stack類，建議使用LinkedList，更遺憾的是，Java裡根本沒有一個叫做Queue的類別（它是個介面名字）。

LinkedList底層透過雙向鍊錶實現，本節將著重講解插入和刪除元素時雙向鍊錶的維護過程，也即是之間解跟List介面相關的函數，而將Queue和Stack以及Deque相關的知識放在下一節講。雙向鍊錶的每個節點都用內部類別Node表示。 LinkedList透過first和last引用分別指向鍊錶的第一個和最後一個元素。注意這裡沒有所謂的啞元，當鍊錶為空的時候first和last都指向<a href="http://www.php.cn/wiki/62.html" target="_blank">null</a>##。

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

LinkedList的實作方式決定了所有跟下標相關的運算都是線性時間，而在首段或結尾刪除元素只需要常數時間。為追求效率LinkedList沒有實現同步（syn

chronized），如果需要多個線程並發訪問，可以先採用Collections.synchronizedList()方法對其進行包裝。

方法剖析

add()

add()方法有兩個版本，一個是

add(E e)，該方法在LinkedList的末尾插入元素，因為有last指向鍊錶末尾，在末尾插入元素的花費是常數時間。只需要簡單修改幾個相關參考即可；另一個是add(int index, E element)，該方法是在指定下表處插入元素，需要先透過線性查找找到具體位置，然後修改相關參考完成插入操作。

結合上圖，可以看出

add(E e)的邏輯非常簡單。

//add(E e)
public boolean add(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++;
    return true;
}

add(int index, E element)的邏輯稍微複雜，可以分成兩部，1.先根據index找到要插入的位置；2.修改引用，完成插入操作。

//add(int index, E element)
public void add(int index, E element) {
    checkPositionIndex(index);//index >= 0 && index <= size;
    if (index == size)//插入位置是末尾，包括列表为空的情况
        add(element);
    else{
        Node<E> succ = node(index);//1.先根据index找到要插入的位置
        //2.修改引用，完成插入操作。
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)//插入位置为0
            first = newNode;
        else
            pred.next = newNode;
        size++;
    }
}

上面程式碼中的

node(int index)函數有一點小小的trick，因為鍊錶雙向的，可以從開始往後找，也可以從結尾往前找，具體朝那個方向找取決於條件index < (size >> 1)，也也就是index是靠近前端還是後端。

remove()

remove()方法也有兩個版本，一個是刪除跟指定元素相等的第一個元素remove( Object<a href="http://www.php.cn/wiki/60.html" target="_blank"> o)</a>，另一個是刪除指定下標處的元素remove(int index)。

兩個刪除操作都要1.先找到要刪除元素的引用，2.修改相關引用，完成刪除操作。在尋找被刪元素引用的時候

remove(Object o)呼叫的是元素的equals方法，而remove(int index)使用的是下標計數，兩種方式都是線性時間複雜度。在步驟2中，兩個revome()方法都是透過unlink(Node x)方法完成的。這裡需要考慮刪除元素是第一個或最後一個時的邊界情況。

//unlink(Node<E> x)，删除一个Node
E unlink(Node<E> x) {
    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;//let GC work
    size--;
    return element;
}

get()

get(int index)得到指定下標處元素的引用，透過呼叫上文中提到的node(int index )方法實作。

public E get(int index) {
    checkElementIndex(index);//index >= 0 && index < size;
    return node(index).item;
}

set()

set(int index, E element)方法將指定下標處的元素修改成指定值，也是先透過node (int index)找到對應下表元素的引用，然後修改Node中item的值。

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;//替换新值
    return oldVal;
}

以上是Java LinkedList原始碼剖析（圖）的詳細內容。更多資訊請關注PHP中文網其他相關文章！