单链表的双向迭代

Question

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

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

我有一个想法，首先向前遍历链表，然后存储一个临时链表，该链表将节点保持在相反的方向。但是遍历此临时列表将导致迭代器仅允许向后遍历。

Answer 1

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

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

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

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

编辑：当然，我们可以提高效率；这个答案有点蛮力。

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

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