java - 双链表中的 get(x) 操作需要访问多少个元素？

Question

有一个关于双向链表的问题，我思考了一段时间，但仍然无法得到答案。假设双向链表中有 N 个元素。如果我们想要在双向链表中获取一个节点，无论是在最坏情况还是平均情况下，我们必须访问多少个元素？

直观上，我认为最坏的情况是N/2个元素，因为我们可以从双向链表的前后遍历。然而，另一种想法是，我们不知道节点的位置，因此我们不应该知道应该从哪个方向开始？如果是这样的想法，最坏的情况是N。这就是我感到困惑的一点。

我还不知道正确的结果，可能我会在下周更新我的问题，因为这是我的教程中的问题之一。

Answer 1

对此没有唯一的正确答案。它实际上取决于 get(position) 方法的实现方式。

• 如果实现总是沿一个方向(向前或向后)遍历列表，那么最坏的情况是 N 步。

• 如果实现根据位置的值从一端或另一端遍历列表，那么最坏的情况是 N/2 步。

但是有一个问题。为了以“智能”方式做到这一点，列表实现必须保留列表大小的记录。如果没有这个，它必须计算大小......这涉及遍历整个列表。

(在我查看的所有 Java 版本中，Oracle/OpenJDK LinkedList 实现指定为从任一端遍历。但是，您还没有说您是否在谈论标准实现。)

平均情况也并不像您想象的那么简单。它实际上取决于您查找的职位的分布函数。如果分布函数是“平坦”的；即所有位置的概率相同，那么平均步数是最坏情况的一半。否则...不会。