LinkedHashMap的impl - 使用雙鏈表，而不是單鏈表;爲什麼

我試圖理解爲什麼被選擇了S（英格爾）LL 最大的好處我一個DLL得到一個DLL會遍歷向後，但我沒有看到LinkedHashMap（）利用這個優勢的任何用例，因爲在Iterable接口中沒有像previous（）這樣的先前（）操作。

任何人都可以解釋爲什麼是DLL而不是SLL？

2012-10-27 smc

可能與刪除操作有關。 – bdares

@bdares我相信最佳的遍歷gaurentees最佳刪除了。遍歷明智，我相信SLL是最佳的DLL – smc

這是因爲使用額外的哈希映射，您可以在O（1）中實現刪除。如果您使用的是單向鏈接列表，則刪除將採用O（n）。

考慮用於存儲鍵值對的哈希映射，以及具有指向鏈表中的節點的鍵的另一個內部哈希映射。當刪除時，如果它是一個雙向鏈表，我可以輕鬆地到達前一個元素並使其指向以下元素。單鏈表不可能這樣做。

2013-04-18 21:05:23

回答