一、contains源碼分析

本文分析雙向鏈表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<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; }

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

源碼首先將元素為null的情形單獨(dú)判讀剝離，個(gè)人分析，應(yīng)該是如果不單獨(dú)分析，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。

二、remove源碼對(duì)比

通過查閱，發(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<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; }

對(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<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++; //注：已從結(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;

三、總結(jié)

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

總結(jié)

以上是生活随笔為你收集整理的LinkedList中查询(contains)和删除(remove)源码分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。