linkedhashmap - LinkedHashMap 的 impl - 使用双链表，而不是单链表；为什么

Question

正如我提到的LinkedHashMap的文档，它说，内部维护了一个双链表（DLL）

我试图理解为什么选择 DLL 而不是 S(ingle)LL 我使用 DLL 获得的最大优势是向后遍历，但我没有看到任何 LinkedHashMap() 利用这一优势的用例，因为没有以前的（ ) 类似 Iterable 接口中的 next() 的操作..

谁能解释为什么是 DLL 而不是 SLL？

score 8 · Accepted Answer

这是因为使用额外的哈希映射，您可以在 O(1) 中实现删除。如果您使用的是单链表，则删除需要 O(n)。

考虑一个用于存储键值对的哈希映射，以及另一个内部哈希映射，其中键指向链表中的节点。删除的时候，如果是双向链表，我可以很方便的找到前一个元素，让它指向下一个元素。这对于单链表是不可能的。

1 回答 1