❤️用武俠小說的形式來閱讀LinkedList的源碼，絕了！(2)

addFirst 内部其實調用的是 linkFirst：

public void addFirst(E e) {
    linkFirst(e);
}      

linkFirst 負責把新的節點設為 first，并将新的 first 的 next 更新為之前的 first。

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}      

addLast 的核心其實和 addFirst 差不多，就交給大家自行了解了。

2）招式二：删

我這個删的招式還挺多的：

remove()：删除第一個節點

remove(int)：删除指定位置的節點

remove(Object)：删除指定元素的節點

removeFirst()：删除第一個節點

removeLast()：删除最後一個節點

remove 内部調用的是 removeFirst，是以這兩個招式的功效一樣。

remove(int) 内部其實調用的是 unlink 方法。

public E remove(int index) {

   checkElementIndex(index);

   return unlink(node(index));

}

unlink 方法其實很好了解，就是更新目前節點的 next 和 prev，然後把目前節點上的元素設為 null。

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

remove(Object) 内部也調用了 unlink 方法，隻不過在此之前要先找到元素所在的節點：

public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}      

這内部就分為兩種，一種是元素為 null 的時候，必須使用 == 來判斷；一種是元素為非 null 的時候，要使用 equals 來判斷。equals 是不能用來判 null 的，會抛出 NPE 錯誤。

removeFirst 内部調用的是 unlinkFirst 方法：

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}      

unlinkFirst 負責的就是把第一個節點毀屍滅迹，并且捎帶把後一個節點的 prev 設為 null。

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}      

3）招式三：改

可以調用 set() 方法來更新元素：

list.set(0, "沉默王五");

1

來看一下 set() 方法：

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

首先對指定的下标進行檢查，看是否越界；然後根據下标查找原有的節點：

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

size >> 1：也就是右移一位，相當于除以 2。對于計算機來說，移位比除法運算效率更高，因為資料在計算機内部都是二進制存儲的。

換句話說，node 方法會對下标進行一個初步判斷，如果靠近前半截，就從下标 0 開始周遊；如果靠近後半截，就從末尾開始周遊。

找到指定下标的節點就簡單了，直接把原有節點的元素替換成新的節點就 OK 了，prev 和 next 都不用改動。

4）招式四：查

我這個查的招式可以分為兩種：

indexOf(Object)：查找某個元素所在的位置

get(int)：查找某個位置上的元素

indexOf 的内部分為兩種，一種是元素為 null 的時候，必須使用 == 來判斷；一種是元素為非 null 的時候，要使用 equals 來判斷。因為 equals 是不能用來判 null 的，會抛出 NPE 錯誤。

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}      

get 方法的核心其實還是 node 方法，這個之前已經說明過了，這裡略過。

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

其實，查這個招式還可以演化為其他的一些，比如說：

getFirst() 方法用于擷取第一個元素；

getLast() 方法用于擷取最後一個元素；

poll() 和 pollFirst() 方法用于删除并傳回第一個元素（兩個方法盡管名字不同，但方法體是完全相同的）；

pollLast() 方法用于删除并傳回最後一個元素；

peekFirst() 方法用于傳回但不删除第一個元素。

四、LinkedList 的挑戰

說句實在話，我不是很喜歡和師兄 ArrayList 拿來比較，因為我們各自修煉的内功不同，沒有孰高孰低。

雖然師兄經常喊我一聲師弟，但我們之間其實挺和諧的。但我知道，在外人眼裡，同門師兄弟，總要一較高下的。

比如說，我們倆在增删改查時候的時間複雜度。

也許這就是命運吧，從我進入師門的那天起，這種争論就一直沒有停息過。

無論外人怎麼看待我們，在我眼裡，師兄永遠都是一哥，我敬重他，他也願意保護我。

好了，LinkedList 這篇就到這了。

如果大家有閑情逸緻的話，建議手撕一下連結清單，可以從單向連結清單開始撕起。

希望大家能點贊下，給我注入一點點更新的動力。我也會不斷地提升品質，給大家帶來更硬核的技術文章，筆芯~