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

Question

正如我提到的 LinkedHashMap 的文档, 它说, 双链表 (DLL) 在内部维护

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

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

Answer 1

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

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

http://www.quora.com/Java-programming-language/Why-is-a-Java-LinkedHashMap-or-LinkedHashSet-backed-by-a-doubly-linked-list