知识卡片
反向遍历也需要起点
示例 reverse 先从传入节点沿 Next 走到尾,再沿 Previous 返回。因此有反向链接并不意味着能直接从尾部开始;未保存尾指针时,找到尾仍是 O(n)。它打印逆序并未反转节点链接,函数名不能代替实际行为。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 05.6.1 Go 语言实现双向链表 · 查看原书依据
st.go 中的一样。但是 reverse() 背后的逻辑很有趣。因为没有指向双向链表尾节点的指针,所以我们必须先从头向后访问,直到找到尾节点,之后才能反向遍历所有的节点。
参考来源
- 位置:《精通 Go(Mastering Go 中文版)》05.6.1 Go 语言实现双向链表,spine092(book-sources;extracted/精通 Go(Mastering Go 中文版)/_epub-src/05.6.1.html)。
- 结论依据:逐步追踪 reverse 中两段方向相反的循环。
- 原始内容:st.go 中的一样。但是 reverse() 背后的逻辑很有趣。因为没有指向双向链表尾节点的指针,所以我们必须先从头向后访问,直到找到尾节点,之后才能反向遍历所有的节点。