知识卡片

结构图卡 · 5654.d.1.b.4.l · 生成模型:未记录

反向链接以空间换访问能力

理解等级:中级

双向链表让每个节点同时保存next与prev,可从尾沿prev反向遍历,也能从已知节点直接取得前驱。它以每节点多一个指针以及更多更新责任,换取更灵活的局部访问和移除。

非循环形式的首节点prev与尾节点next为NULL;节点数量不变时,结构仍需保持相邻两侧引用一致。这个边界约定不独立证明节点属于某张表,外部保存的位置也仍可能失效。

60的02734-02735给具体C类型:

结构图:

classDiagram
class DList {
 int size
 match : 比较回调
 destroy : 清理回调
 DListElmt* head
 DListElmt* tail
}
class DListElmt {
 void* data
 DListElmt_* prev
 DListElmt_* next
}
class API["双向公开函数组(非类型)"] {
 dlist_init(DList* list, destroy) void
 dlist_destroy(DList* list) void
 dlist_ins_next(DList* list, DListElmt* element, const void* data) int
 dlist_ins_prev(DList* list, DListElmt* element, const void* data) int
 dlist_remove(DList* list, DListElmt* element, void** data) int
}
DList --> DListElmt : head和tail引用端点
DListElmt --> DListElmt : prev及next引用相邻节点
API ..> DList : 操作容器及其节点

图中API只是C自由函数分组,不是新增类型或结构体成员方法;实际结构标签为DList_/DListElmt_,别名为无下划线的DList/DListElmt。match是int(const void,const void)回调,destroy为void(void*)回调,均与单链表字段分工相似。

63的02736四步图与02738实际dlist_ins_next:先保存new.next=element.next和new.prev=element,原后继存在时将其prev改new,否则更新tail,最后element.next=new。空表分支建立head/tail并把两向链接置NULL。每个方向都要从同一邻接关系出发更新,不能只完成正向遍历。

64描述前插维护prev/next,但66的02739实际非空分支只显式设置new_element->prev,缺少new_element->next=element。不能因为概述声称维护双向关系就把该代码当完整正确实现;具体遗漏另在66记录问题与修复方向,未执行。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 4 处

    • · 查看原书依据

      每个元素还包含一个指向其前驱元素的指针,称为prev指针。双向链表的组成是这样的:将一些元素链接在一起使得每个元素的next指针都指向其后继的元素,而每个元素的prev指针都指向其前驱元素。为了标识链表的头和尾,将第一个元素的prev指针和最后一个元素的next指针设置为NULL。 要反向遍历整个双

    • · 查看原书依据

      DListElmt代表双向链表中的元素(见示例5-4)。如你所料,这个结构体拥有前文描述过的3个成员。数据结构DList代表双向链表数据结构(见示例5-4),该结构的成员同前面介绍的单链表相似。 示例5-4:双向链表抽象数据类型的头文件

    • · 查看原书依据

      还必须管理prev指针,以保证链表的反向链接关系正确(见图5-6)。 图 5-6 将新元素插入双向链表中 dlist_ins_next的复杂度为O(1),因为插入操作的所有步骤均能够在恒定的时间内完成。

    • · 查看原书依据

      dlist_ins_prev操作用来将新元素插入双向链表中由参数element所指定的元素之前(见示例5-5)。双向链表中的插入操作与单链表类似。和dlist_ins_next一样,最大的不同在于除了要管理next指针的指向外,还必须管理prev指针,以保证链表的反向链接关系正确。dlist_ins

    参考来源

    - 位置:《算法精解:C语言描述》第5章《双向链表介绍》(spine1213;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1180.html;u058-ch05-013)。 - 结论依据:58全文直接定义三部分节点、首尾NULL、反向遍历及空间/访问取舍;没有把双向链表简化为所有操作都快。 - 原始内容:每个元素还包含一个指向其前驱元素的指针,称为prev指针。双向链表的组成是这样的:将一些元素链接在一起使得每个元素的next指针都指向其后继的元素,而每个元素的prev指针都指向其前驱元素。为了标识链表的头和尾,将第一个元素的prev指针和最后一个元素的next指针设置为NULL。 要反向遍历整个双 - 位置:《算法精解:C语言描述》第5章《双向链表的实现与分析》(spine1215;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1182.html;u060-ch05-013)。 - 结论依据:60的02734-02735给具体C类型: **结构图**: ```mermaid classDiagram class DList { int size match : 比较回调 destroy : 清理回调 DListElmt* head DListElmt* tail } class DListElmt { void* data DListElmt_* prev DListElmt_* next } class API["双向公开函数组(非类型)"] { dlist_init(DList* list, destroy) void dlist_destroy(DList* list) void dlist_ins_next(DList* list, DListElmt* element, const void* data) int dlist_ins_prev(DList* list, DListElmt* element, const void* data) int dlist_remove(DList* list, DListElmt* element, void** data) int } DList --> DListElmt : head和tail引用端点 DListElmt --> DListElmt : prev及next引用相邻节点 API ..> DList : 操作容器及其节点 ``` 图中API只是C自由函数分组,不是新增类型或结构体成员方法;实际结构标签为DList_/DListElmt_,别名为无下划线的DList/DListElmt。match是int(const void*,const void*)回调,destroy为void(void*)回调,均与单链表字段分工相似。 - 原始内容:DListElmt代表双向链表中的元素(见示例5-4)。如你所料,这个结构体拥有前文描述过的3个成员。数据结构DList代表双向链表数据结构(见示例5-4),该结构的成员同前面介绍的单链表相似。 示例5-4:双向链表抽象数据类型的头文件 - 位置:《算法精解:C语言描述》第5章《dlist_ins_next》(spine1217;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1184.html;u063-ch05-013)。 - 结论依据:63的02736四步图与02738实际dlist_ins_next:先保存new.next=element.next和new.prev=element,原后继存在时将其prev改new,否则更新tail,最后element.next=new。空表分支建立head/tail并把两向链接置NULL。每个方向都要从同一邻接关系出发更新,不能只完成正向遍历。 - 原始内容:还必须管理prev指针,以保证链表的反向链接关系正确(见图5-6)。 图 5-6 将新元素插入双向链表中 dlist_ins_next的复杂度为O(1),因为插入操作的所有步骤均能够在恒定的时间内完成。 - 位置:《算法精解:C语言描述》第5章《dlist_ins_prev》(spine1218;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1185.html;u064-ch05-013)。 - 结论依据:64描述前插维护prev/next,但66的02739实际非空分支只显式设置new_element->prev,缺少new_element->next=element。不能因为概述声称维护双向关系就把该代码当完整正确实现;具体遗漏另在66记录问题与修复方向,未执行。 - 原始内容:dlist_ins_prev操作用来将新元素插入双向链表中由参数element所指定的元素之前(见示例5-5)。双向链表中的插入操作与单链表类似。和dlist_ins_next一样,最大的不同在于除了要管理next指针的指向外,还必须管理prev指针,以保证链表的反向链接关系正确。dlist_ins