我已经思考了一段时间有关doubly linkedlist的问题，但仍然无法得到答案。假设N中有doubly linkedlist个元素。如果想在最坏的情况下和平均情况下在doubly linkedlist中获取节点，我们必须访问多少个元素？
凭直觉，我认为最坏的情况是N/2元素，因为我们可以从doubly linkedlist的正面和背面进行遍历。但是，另一种想法是我们不知道节点的位置，因此我们不应该知道应该从哪个方向开始？如果是这样的话，最坏的情况是N。这就是我感到困惑的地方。
我尚不知道正确的结果，可能下周会更新我的问题，因为这是我教程中的问题之一。
最佳答案
没有一个正确的答案。它实际上取决于get(position)方法的实现方式。
如果执行总是沿一个方向（向前或向后）遍历列表，则最坏的情况是N步。
如果根据位置值从一端或另一端遍历列表，则最坏的情况是N / 2步。
但是有一个问题！为了实现“智能”方式，列表实现必须保留列表大小的记录。否则，它必须计算大小...涉及遍历整个列表。
（在我查看的所有Java版本中，Oracle / OpenJDK LinkedList实现都被指定为从两端进行遍历。但是，如果您在谈论标准实现，则无需多说。）
平均情况也不如您想象的那么直接。实际上，它取决于您查找位置的分布函数。如果分布函数是“平坦的”；也就是说，所有职位的可能性均等，那么平均步数是最坏情况的一半。否则...不会。