關於清除鏈接列表的Java最佳實踐

Question

我正在編寫一個數據結構java中的鏈接列表（爲了我的學習緣故，我沒有使用任何標準的java庫），我想通過空引用清除數據結構。請告訴我哪種方法更好

1）只是null列表的開始引用，這就足夠了。

2）除了使開始無效之外，我將所有內部節點的所有下一個指針都解除爲空。這是否以任何方式幫助垃圾回收器？

在我看到的方法2時遵循的JDK LinkedList的implementation.But我沒有看到同爲TreeMap的

我使用JDK 8

Answer 1

這是一個有趣的問題，和混亂答案具有悠久的歷史和微妙的權衡。

簡而言之，清除引用對於數據結構的正確操作不是必需的。由於您正在學習數據結構，因此我建議您不要在自己的實現中擔心這個問題。我的預感（儘管我沒有對此進行基準測試）是，在典型情況下，清除所有鏈路節點可能產生的任何好處很少會引起注意。

（此外，很可能是典型的條件下，LinkedList將由ArrayList或ArrayDeque跑贏。有是基準，說明了這一點。這不是太難拿出工作量，其中LinkedList優於別人，但它的比人們想象的要少）

我很驚訝地發現LinkedList的clear操作使得所有節點彼此之間以及所包含的元素之間無法鏈接。這是鏈接到code in JDK 8。這種變化可以追溯到2003年，並且變化出現在JDK 5中。此變更由bug JDK-4863813追蹤。該更改（或稍早）會從個別節點清除與列表中未鏈接的下一個和上一個引用。這個bug報告中還有一個測試用例，這個測試用例很有趣。

問題似乎是可以對創建垃圾節點的LinkedList進行更改，比垃圾回收器可以回收它們的速度更快。這最終會導致JVM耗盡內存。垃圾節點全部鏈接在一起的事實似乎也具有阻礙垃圾收集器的作用，使得增變器線程更容易超出收集器線程。 （我不清楚讓多個線程變更列表的重要性，在測試用例中它們都在列表上同步，所以沒有實際的並行性。）通過更改爲LinkedList以斷開彼此的節點可以更容易爲收集器做工作，顯然使測試不再耗盡內存。

快進到2009年，當LinkedList代碼被給予「整容」。這由bug JDK-6897553跟蹤並在email review thread中討論。 「整容」的最初動機之一是將操作從O（n）減少到O（1），因爲斷開連接所有節點對於該錯誤的提交者來說似乎是不必要的。 （對我來說這似乎沒有必要！）但經過一番討論後，決定解除鏈接行爲爲垃圾收集器保留並記錄垃圾收集器提供了足夠的好處。

該評論還表示，取消與相應節點

是一定要釋放內存，即使是有到達迭代器

這是指如下所示的有些病理情況：

// fields in some class 
List<Obj> list = createAndPopulateALinkedList(); 
Iterator<Object> iterator; 

void someMethod() { 
    iterator = list.iterator(); 
    // ... 
    list.clear(); 
} 

迭代器指向鏈表中的一個節點。即使清單已被清除，迭代器仍然保持活動狀態，並且由於該節點具有下一個和前一個引用，所有以前在列表中的節點仍處於活動狀態。取消鏈接clear()中的所有節點可以收集這些節點。不過，我認爲這是相當病態的，因爲迭代器很少存儲在字段中。迭代器通常在單個方法中創建，使用和丟棄，通常在一個for循環中。

現在，關於TreeMap。我不認爲爲什麼LinkedList取消鏈接其節點，而TreeMap沒有。有人可能會認爲整個JDK代碼庫都保持一致，所以如果LinkedList解除鏈接其節點是一種很好的做法，那麼也應該完成TreeMap。唉，事實並非如此。最可能發生的事情是，客戶遇到了LinkedList的病態行爲，並且發生了變化，但沒有人觀察到與TreeMap類似的行爲。因此沒有更新TreeMap的動力。