单链表上的双向迭代
我目前正在学习数据结构考试，遇到了一个关于迭代的问题。
在单链表上实现双向迭代器是可能的吗？如果是的话，如何实施呢？
我有一个想法，首先向前遍历链表，并存储一个临时链表，该临时链表保存反向的节点。但是遍历这个临时列表将导致一个只允许向后遍历的迭代器。
共有1个答案
此答案假定列表必须始终保持单链接：
您只需要一个指向第一个元素的指针和一个指向当前元素的指针。
当您向前迭代时，增加一些计数器以知道您已经迭代了多少次。（插入可能会使迭代器无效！）。让我们将此变量称为count
现在，如果要从当前元素向后迭代k值，您知道需要从第一个元素count-k次向前迭代。
编辑：我们当然可以提高效率；这个答案是一种蛮力的方法。
正如前面提到的一个注释，您可以在向前迭代时将指针推入堆栈，然后在向后迭代时弹出它们。
如果列表不必总是保持单链接，那么您可以在向前迭代时添加反向链接，然后在向后迭代时删除这些链接（尽管谁知道您为什么要这样做）。
-
本文向大家介绍双向链表和双向循环链表?相关面试题，主要包含被问及双向链表和双向循环链表?时的应答技巧和注意事项，需要的朋友参考一下 双向链表： 包含两个指针，一个prev指向前一个节点，一个next指向后一个节点。 双向循环链表： 最后一个节点的 next 指向head，而 head 的prev指向最后一个节点，构成一个环。
-
我创建了一个单链表函数，我的教授说，为了获得额外的学分，我们可以将其更改为双链表。我读了一些东西，比如添加一个prev_节点函数，比如这样。 然而，我不知道从那里去哪里。我知道我需要像这里一样加上一个尾巴和一个脑袋。 谁能告诉我，（不要为我做这件事），我必须做什么才能把我的链接列表变成一个双重链接列表？我知道我现在必须参考尾巴和头部，但我对如何做到这一点很困惑。
-
主要内容：双向链表的创建目前我们所学到的 链表，无论是动态链表还是 静态链表，表中各节点中都只包含一个指针（游标），且都统一指向直接后继节点，通常称这类链表为 单向链表（或 单链表）。 虽然使用单链表能 100% 解决逻辑关系为 "一对一" 数据的存储问题，但在解决某些特殊问题时，单链表并不是效率最优的存储结构。比如说，如果算法中需要大量地找某指定结点的前趋结点，使用单链表无疑是灾难性的，因为单链表更适合 "从前往后"
-
双向链表 结构体 struct rt_list_node 双向链表节点 更多... 宏定义 #define rt_container_of(ptr, type, member) ((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member))) 获取type结构体中member成员在这个结构体中的偏移 #de
-
双向链表 Linux 内核自己实现了双向链表，可以在 include/linux/list.h 找到定义。我们将会从双向链表数据结构开始内核的数据结构。为什么？因为它在内核里使用的很广泛，你只需要在 free-electrons.com 检索一下就知道了。 首先让我们看一下在 include/linux/types.h 里的主结构体： struct list_head { struct l
-
问题内容： 我想在同步双向链接列表上实现QuickSort算法。我给函数“ partition”添加了左右边界，然后它开始在左侧搜索较低的值，并在右侧搜索较大的值。之所以可行，是因为我的枢轴元素始终是最右侧的元素，并且在此步骤之后它位于中间。 我总是无休止的循环，我不知道为什么？也许错误的中止条件？ 她我的代码： 问题答案： 只是快速浏览一下，您的列表似乎不仅被双重链接，而且在末端连接在一起（因此