java - 单链表上的双向迭代

Question

我目前正在准备数据结构考试，并遇到了有关迭代的问题。

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

我有一个想法，首先向前遍历链表并存储一个临时链表，该链表保存反向的节点。但是遍历这个临时列表将产生一个只允许向后遍历的迭代器。

Answer 1

这个答案假设列表必须始终保持单链接:

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

当您向前迭代时，增加一些计数器以了解迭代了多少次。 (插入可能会使迭代器无效!)。我们将此变量称为 count

现在，如果您想从当前元素向后迭代 k 值，您知道需要从第一个元素向前迭代 count - k 次。

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

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

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