知识卡片
反向链接以空间换访问能力
双向链表让每个节点同时保存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