java - 单链表的双向迭代

Question

我目前正在学习数据结构考试，遇到了一个关于迭代的问题。

是否可以在单链表上实现双向迭代器？如果是这样，人们将如何实施它？

我有一个想法，首先正向遍历链表并存储一个临时链表，其中包含反向的节点。但是遍历这个临时列表会产生一个只允许向后遍历的迭代器。

Answer 1

此答案假定列表必须始终保持单链接：

您只需要一个指向第一个元素的指针和一个指向当前元素的指针。

当您向前迭代时，增加一些计数器以了解您已经迭代了多少次。（插入可能会使迭代器无效！）。我们称这个变量为count

现在，如果你想从当前元素向后迭代k值，你知道你需要从第一个元素count - k时间开始迭代 FORWARDS。

编辑：当然我们可以提高效率；这个答案是一种蛮力的方法。

正如提到的评论之一，您可以在向前迭代时将指针推入堆栈，然后在向后迭代时将它们弹出。

如果列表不必总是保持单链接，那么您可以在向前迭代时添加向后链接，然后在向后迭代时删除这些链接（尽管谁知道您为什么要这样做）。

Answer 2

您始终可以使用跟踪当前节点的变量。如果您想向前遍历，请照常进行。如果要向后移动，只需从第一个节点开始，然后继续移动，直到下一个节点等于当前节点。

Answer 3

另一种方法是：创建迭代器时，创建一个大小为链表大小的数组，但不要填充它。在迭代器中保留一个索引以及“当前节点”。每次迭代器向前移动时，也要将节点引用放在数组中适当的索引处。要向后移动迭代器，只需减少索引并查看数组以查看您已经访问过的节点。我认为这几乎等同于@DarthVader 提到的“堆栈”。这样做的好处是，如果您希望调用者做很多事情反向遍历；其他人提到的简单解决方案每次反向遍历都需要 O(n)，但使用像数组这样的方法将是 O(1)。当迭代器向前移动时，缺点是需要更多的记账。在现实生活中，必须权衡利弊。对于一个相对较小的列表，它可能不值得。但是假设你有一个带有单链接记录的大磁盘文件，并且你想要一个遍历文件的迭代器；如果你想让迭代器能够倒退，你不想为了找到前一个节点而重新读取整个文件。