知识卡片
单链插移接口围绕前驱
list_ins_next(list,element,data)在element之后插入,element为NULL时插到头部;list_rem_next(list,element,&out)移除element之后的节点,NULL时移除头部,并通过真正void*输出变量out交还数据地址。二者成功返回0,失败返回-1。
这组接口操作的是“某节点之后”,不是把element自身删掉。已有正确前驱时,链接更新可按常数步骤完成;寻找前驱或目标的遍历不包含在这个O(1)承诺里。调用方仍要提供属于该表的有效位置,插入的数据在节点存在期间须保持合法。
76讨论把后继数据拷贝进当前节点再删后继的技巧:它改变节点与数据的对应关系,让外部保存的引用语义发生变化,也不能普遍用于没有后继的尾节点。不能只凭O(1)宣称与精确删除当前对象等价;_rem_next和_remove分别表达目标。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 单链插移接口围绕前驱
- · 问与答
原书出处 · 2 处
- · 查看原书依据
element设置为NULL,则新元素插入链表头部。新元素包含一个指向data的指针,因此只要该元素还在链表中,data所引用的内存空间就应该保持合法。管理data所引用的存储空间是调用者的责任。 复杂度 O(1) list_rem_next 返回值 如果移除元素成功则返回0,否则返回-1。 描述
- · 查看原书依据
后继结点的数据拷贝到指定元素中,然后移除后继结点。这貌似良好的O(1)方法导致危险的负面影响:使指向链表的指针失效。对于维护指向该元素的一个指针的开发人员来说,在认为该元素需要删除之后,他会大吃一惊。该方法的缺点是它与双向链表实现的dlist_remove操作不一致。不管如何,都需要由命名约定来修饰
参考来源
- 位置:《算法精解:C语言描述》第5章《单链表接口的定义》(spine1206;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1173.html;u050-ch05-006)。
- 结论依据:50插入/移除两节与02702-02703原型,返回值、NULL特殊含义、数据存活及调用方责任完整核对;输出适配沿第2章已纠正的void**规则。
- 原始内容:element设置为NULL,则新元素插入链表头部。新元素包含一个指向data的指针,因此只要该元素还在链表中,data所引用的内存空间就应该保持合法。管理data所引用的存储空间是调用者的责任。 复杂度 O(1) list_rem_next 返回值 如果移除元素成功则返回0,否则返回-1。 描述
- 位置:《算法精解:C语言描述》第5章《问与答》(spine1229;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1196.html;u076-ch05-006)。
- 结论依据:76讨论把后继数据拷贝进当前节点再删后继的技巧:它改变节点与数据的对应关系,让外部保存的引用语义发生变化,也不能普遍用于没有后继的尾节点。不能只凭O(1)宣称与精确删除当前对象等价;_rem_next和_remove分别表达目标。
- 原始内容:后继结点的数据拷贝到指定元素中,然后移除后继结点。这貌似良好的O(1)方法导致危险的负面影响:使指向链表的指针失效。对于维护指向该元素的一个指针的开发人员来说,在认为该元素需要删除之后,他会大吃一惊。该方法的缺点是它与双向链表实现的dlist_remove操作不一致。不管如何,都需要由命名约定来修饰