LinkedList中查詢(contains)和刪除(remove)源碼分析

timger 發布于2019-08-16 15:15 / 990人閱讀

摘要：一源碼分析本文分析雙向鏈表的查詢操作源碼實現。中源程序中，的查詢操作，通過函數實現。源程序中使用循環進行遍歷。表示鏈表元素索引，初值為。針對空元素的情況，用循環遍歷，查找元素為的節點，并返回索引。

一、contains源碼分析

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

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函數查詢對象o在鏈表中的索引位置。

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

由于鏈表不同于數組，在內存中并非連續存儲，因此訪問某個元素需要遍歷。源程序中使用for循環進行遍歷。index表示鏈表元素索引，初值為0。

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

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

二、remove源碼對比

通過查閱，發現remove方法和contains方法的源碼實現非常相似，列出如下：

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

對比發現，和contains類似，remove操作首先也是查找Object o是否存在與表中。空節點元素和非空節點的循環判斷基本相同，在找到Object o后，區別與contains的返回索引，remove需要刪除節點link（LinkedList的刪除需要對next鏈進行重配置引用）。

刪除節點的方法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++;  //注：已從結構上修改此列表的次數。AbstractList屬性
    return element;
}

分析：
刪除節點程序中，需要考慮節點在鏈表中的不同位置，進行不同的操作。

1、節點于鏈表首端

此時，特殊操作是需要將first指針（引用）指向其后的節點。

first = next;

2、節點于鏈表尾端

此時，需要將上一個節點的next指針指向null，即上個節點稱為尾節點。

last = prev;

3、節點于鏈表中間情況

如果不仔細思考，我們在寫程序時，會直接在兩個if判斷后，將剩余的相關操作寫在一起。而源碼并沒有這么做，稍作分析，就能看出，如果前一個if中，條件是prev，因此可對該節點的prev進行相關操作。而后續的if語句，還需判斷該節點的next引用，因此在第一個if-else語句體中，不對next進行操作，否則更改后，后學的next已經不是該節點的原next值。

因此，第一個if-else中：

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

第二個if-else中：

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

三、總結

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/73371.html

LinkedList源碼解析

摘要：我們來看相關源碼我們看到封裝的和操作其實就是對頭結點的操作。迭代器通過指針，能指向下一個節點，無需做額外的遍歷，速度非常快。不同的遍歷性能差距極大，推薦使用迭代器進行遍歷。LinkedList類介紹上一篇文章我們介紹了JDK中ArrayList的實現，ArrayList底層結構是一個Object[]數組，通過拷貝，復制等一系列封裝的操作，將數組封裝為一個幾乎是無限的容器。今天我們來介紹JD...

番茄西紅柿 2019-05-23 16:08 評論0 收藏0
LinkedList源碼解析

摘要：我們來看相關源碼我們看到封裝的和操作其實就是對頭結點的操作。迭代器通過指針，能指向下一個節點，無需做額外的遍歷，速度非常快。不同的遍歷性能差距極大，推薦使用迭代器進行遍歷。LinkedList類介紹上一篇文章我們介紹了JDK中ArrayList的實現，ArrayList底層結構是一個Object[]數組，通過拷貝，復制等一系列封裝的操作，將數組封裝為一個幾乎是無限的容器。今天我們來介紹JD...

番茄西紅柿 2019-05-23 16:08 評論0 收藏0
Java 常用List集合使用場景分析

摘要：常用集合使用場景分析過年前的最后一篇，本章通過介紹，，，底層實現原理和四個集合的區別。和都是線程安全的，不同的是前者使用類，后者使用關鍵字。面試官會認為你是一個基礎扎實，內功深厚的人才到這里常用集合使用場景分析就結束了。 Java 常用List集合使用場景分析過年前的最后一篇，本章通過介紹ArrayList，LinkedList，Vector，CopyOnWriteArrayList...

godruoyi 2019-08-16 11:03 評論0 收藏0
容器之Collection、Iterable、List、Vector(Stack)分析(三)

摘要：容器相關的操作及其源碼分析說明本文是基于分析的。通常，我們通過迭代器來遍歷集合。是接口所特有的，在接口中，通過返回一個對象。為了偷懶啊，底層使用了迭代器。即返回的和原在元素上保持一致，但不可修改。容器相關的操作及其源碼分析說明 1、本文是基于JDK 7 分析的。JDK 8 待我工作了得好好研究下。Lambda、Stream。 2、本文會貼出大量的官方注釋文檔，強迫自己學英語，篇幅...

liaosilzu2007 2019-08-15 14:38 評論0 收藏0