我们是否需要链表中的前一个元素?

Question

在HashMap的实现中，链表用于表示bucket中的元素。每个Entry都有下一个Entry的元素。然而，在LinkedList类的实现中，每个元素都有对其前一个元素和下一个元素的引用(参见Ref)。只是想弄清楚为什么previous在一个链表中很重要而在另一个链表中不重要?

Answer 1

Entry (HashMap的内部类)不是通用链表的一部分(LinkedList是)。它的唯一目的是向前迭代查找元素。所以它不需要previous引用。

Answer 2

前面的引用使LinkedList成为双向列表，这使得在列表上反向迭代成为可能。

Answer 3

严格来说，对前一个元素的引用在链表中是不需要的。java.util.LinkedList实际上是一个双链表。这是有效实现以下操作所必需的:

• 添加(E)，它附加在列表的末尾;
• getLast()，它检索列表的最后一个元素;
• ListIterator.previous()，允许反向遍历列表。

上述操作对Map.Entry的链表不起作用。

请注意，虽然getLast()是列表接口的LinkedList添加，但其他两个是上述接口所必需的。

Answer 4

LinkedList是一个通用的实现。你可能想要反向迭代。对于map，当搜索一个bucket时，only向前迭代。因为不需要向后迭代，所以没有实现它。