java - 我们需要链表中的前一个元素吗？

Question

在 的实现中HashMap，链表用于表示桶中的元素。每个条目都有一个指向下一个条目的元素。见：参考。但是，在LinkedList类的实现中，每个元素都有对其前一个元素的引用，而其下一个元素参见Ref。只是想弄清楚为什么previous在一个链表中很重要，而在另一个链表中不重要？

Answer 1

Entry（内部类HashMap）不是通用链表的一部分（原样LinkedList）。它的唯一目的是向前迭代它以寻找一个元素。所以它不需要previous参考。

Answer 2

前面的参考使 LinkedList 成为双向 List，这使得反向迭代 List 成为可能。

Answer 3

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

• add(E)，附加在列表的末尾；
• getLast()，它检索列表的最后一个元素；
• ListIterator.previous()允许以相反的顺序遍历列表。

上述操作对于 Map.Entry 的链表是没有用的。

请注意，虽然getLast()是LinkedList对列表界面的补充，但另外两个是所述界面所必需的。

Answer 4

LinkedList 是一个通用的实现。您可能想向后迭代它。对于地图，在搜索存储桶时，它only会向前迭代。由于不需要向后迭代，因此没有实现。