知识卡片
双向插移直接定位当前节点
dlist_ins_next在element后插入,dlist_ins_prev在element前插入;空表时按约定传NULL,非空表需有效节点。dlist_remove删除element本身,并通过void**输出其数据地址,区别于单链表删除前驱之后的节点。
实际02738-02740实现中三项成功都返回0,失败返回-1;接口表把ins_next成功写1是错误。删除空表或传NULL被拒绝,插入分配失败也返回失败;它们未遍历验证节点归属。
数据地址仍由调用方管理,输出参数应指向真正void*变量。新增prev支持已知节点的固定步骤更新,不包含搜索该节点的成本。
65与02739-02740实际dlist_remove:先输出element.data,头节点分支更新head及新头prev;其他分支更新前驱next,尾节点更新tail,非尾更新后继prev,再释放节点并size–。删除的是当前节点,不释放应用数据;NULL/空表失败返回-1,未验证任意非空地址的归属。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
移除由element所指定的元素。函数返回后,参数data将指向已移除元素中存储的数据域。由调用者负责管理data所引用的存储空间。 复杂度 O(1) dlist_size 返回值 链表中的元素个数。 描述 这是一个宏,用来计算由参数list所指定的双向链表中的元素个数。 复杂度 O(1) dlis
- · 查看原书依据
移除当前指定的元素,而不是移除指定元素之后的那个元素,因为每个元素都有一个指向其前驱元素的指针。 dlist_remove的复杂度为O(1),因为所有的操作步骤都能在恒定的时间内完成。
参考来源
- 位置:《算法精解:C语言描述》第5章《双向链表接口的定义》(spine1214;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1181.html;u059-ch05-014)。
- 结论依据:59所有变更接口与02723-02725原型、65当前节点说明及66完整实现已读;返回状态按实际代码核对,纠正表中1/0差别。
- 原始内容:移除由element所指定的元素。函数返回后,参数data将指向已移除元素中存储的数据域。由调用者负责管理data所引用的存储空间。 复杂度 O(1) dlist_size 返回值 链表中的元素个数。 描述 这是一个宏,用来计算由参数list所指定的双向链表中的元素个数。 复杂度 O(1) dlis
- 位置:《算法精解:C语言描述》第5章《dlist_remove》(spine1219;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1186.html;u065-ch05-014)。
- 结论依据:65与02739-02740实际dlist_remove:先输出element.data,头节点分支更新head及新头prev;其他分支更新前驱next,尾节点更新tail,非尾更新后继prev,再释放节点并size--。删除的是当前节点,不释放应用数据;NULL/空表失败返回-1,未验证任意非空地址的归属。
- 原始内容:移除当前指定的元素,而不是移除指定元素之后的那个元素,因为每个元素都有一个指向其前驱元素的指针。 dlist_remove的复杂度为O(1),因为所有的操作步骤都能在恒定的时间内完成。