摘要：一源碼分析本文分析雙向鏈表的查詢操作源碼實(shí)現(xiàn)。中源程序中，的查詢操作，通過函數(shù)實(shí)現(xiàn)。源程序中使用循環(huán)進(jìn)行遍歷。表示鏈表元素索引，初值為。針對(duì)空元素的情況，用循環(huán)遍歷，查找元素為的節(jié)點(diǎn)，并返回索引。

本文分析雙向鏈表LinkedList的查詢操作源碼實(shí)現(xiàn)。jdk中源程序中，LinkedList的查詢操作，通過contains(Object o)函數(shù)實(shí)現(xiàn)。具體見下面兩部分程序：
①

public boolean contains(Object o) {
    return indexOf(o) != -1;
}

②

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

indexOf函數(shù)查詢對(duì)象o在鏈表中的索引位置。

源碼首先將元素為null的情形多帶帶判讀剝離，個(gè)人分析，應(yīng)該是如果不多帶帶分析，null元素在下邊的for循環(huán)中，不能執(zhí)行o.equals操作（編譯器輸入null.，會(huì)自動(dòng)將已有輸入替換為NullPointerException.，提示空指針異常）。

由于鏈表不同于數(shù)組，在內(nèi)存中并非連續(xù)存儲(chǔ)，因此訪問某個(gè)元素需要遍歷。源程序中使用for循環(huán)進(jìn)行遍歷。index表示鏈表元素索引，初值為0。

1、針對(duì)空元素（null）的情況，用for循環(huán)遍歷，查找元素為null的節(jié)點(diǎn)，并返回索引index。for循環(huán)初始條件為頭指針（無元素），判斷條件為節(jié)點(diǎn)不為null，自增表達(dá)式為x重賦值為下個(gè)節(jié)點(diǎn)（利用節(jié)點(diǎn)x的next指針實(shí)現(xiàn)，在java中next為node對(duì)象的屬性成員）。每次自增，index+1。
2、針對(duì)非空元素，遍歷操作同上。函數(shù)結(jié)束的判斷條件變?yōu)?strong>o.equals(x.item)，這里equals方法為Object超類的方法，程序中元素類型非Object也可調(diào)用。

兩種情形下，鏈表遍歷完畢（仍為return），表明該元素o在鏈表中不存在，因此返回-1。

通過查閱，發(fā)現(xiàn)remove方法和contains方法的源碼實(shí)現(xiàn)非常相似，列出如下：

/**
 * Removes the first occurrence of the specified element from this list, 
 * if it is present.  If this list does not contain the element, it is
 * unchanged. 
 * @param o element to be removed from this list, if present
 * @return {@code true} if this list contained the specified element
 */

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

對(duì)比發(fā)現(xiàn)，和contains類似，remove操作首先也是查找Object o是否存在與表中。空節(jié)點(diǎn)元素和非空節(jié)點(diǎn)的循環(huán)判斷基本相同，在找到Object o后，區(qū)別與contains的返回索引，remove需要?jiǎng)h除節(jié)點(diǎn)link（LinkedList的刪除需要對(duì)next鏈進(jìn)行重配置引用）。

刪除節(jié)點(diǎn)的方法unlink的源碼如下：

//Unlinks non-null node x. 
E unlink(Node x) {
    // assert x != null;
    final E element = x.item;
    final Node next = x.next;
    final Node 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++;  //注：已從結(jié)構(gòu)上修改此列表的次數(shù)。AbstractList屬性
    return element;
}

分析：
刪除節(jié)點(diǎn)程序中，需要考慮節(jié)點(diǎn)在鏈表中的不同位置，進(jìn)行不同的操作。

1、節(jié)點(diǎn)于鏈表首端

此時(shí)，特殊操作是需要將first指針（引用）指向其后的節(jié)點(diǎn)。

first = next;

2、節(jié)點(diǎn)于鏈表尾端

此時(shí)，需要將上一個(gè)節(jié)點(diǎn)的next指針指向null，即上個(gè)節(jié)點(diǎn)稱為尾節(jié)點(diǎn)。

last = prev;

3、節(jié)點(diǎn)于鏈表中間情況

如果不仔細(xì)思考，我們?cè)趯懗绦驎r(shí)，會(huì)直接在兩個(gè)if判斷后，將剩余的相關(guān)操作寫在一起。而源碼并沒有這么做，稍作分析，就能看出，如果前一個(gè)if中，條件是prev，因此可對(duì)該節(jié)點(diǎn)的prev進(jìn)行相關(guān)操作。而后續(xù)的if語句，還需判斷該節(jié)點(diǎn)的next引用，因此在第一個(gè)if-else語句體中，不對(duì)next進(jìn)行操作，否則更改后，后學(xué)的next已經(jīng)不是該節(jié)點(diǎn)的原next值。

因此，第一個(gè)if-else中：

prev.next = next;
x.prev = null;

第二個(gè)if-else中：

next.prev = prev;
x.next = null;

從LinkedList的源碼可以看到，源程序中相應(yīng)方法代碼簡(jiǎn)潔，邏輯清晰正確，在學(xué)習(xí)java的過程中，除了學(xué)習(xí)知識(shí)為我所用，也要避免閉門造車，多查看源碼和其他優(yōu)秀的項(xiàng)目程序，參考優(yōu)秀的編程習(xí)慣和思想，從而積累經(jīng)驗(yàn)，提高自己的水平。