知识卡片

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

插入先保留原后继

理解等级:中级

单链插入先让新节点指向原后继,再让前驱指向新节点,避免先覆盖唯一后继引用而丢失后段。头插没有普通前驱,要用head作为待更新入口;空表头插还要设置tail。

02714/02716中普通位置若原element->next为NULL,新节点成为tail;所有成功分支最后size加1。malloc失败返回-1且未把新节点接入表,数据地址只被保存,不复制目标内容。

结构图:

flowchart TD
 A[取得新节点存储] --> B{分配成功}
 B -->|否| X[返回失败]
 B -->|是| C[保存数据地址和原后继]
 C --> D[更新head或前驱next]
 D --> E[必要时更新tail]
 E --> F[size加1并返回成功]

已知有效插入位置是前提,代码不遍历验证该位置属于此表。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      将新元素的next指针指向它之后的那个元素,然后将新元素位置之前的结点next指针指向新插入的元素(见图5-3)。但是,当从链表头部插入时,新元素之前没有别的结点了。因此,在这种情况下,将新元素的next指针指向当前链表的头部,然后重置头结点指针,使其指向新元素。回顾一下前一节中的接口设计,当传入的

    参考来源

    - 位置:《算法精解:C语言描述》第5章《list_ins_next》(spine1209;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1176.html;u054-ch05-009)。 - 结论依据:54全文、02716两步链接图及52已读02714插入代码,连接顺序、头/尾分支和malloc失败均实际核对。 - 原始内容:将新元素的next指针指向它之后的那个元素,然后将新元素位置之前的结点next指针指向新插入的元素(见图5-3)。但是,当从链表头部插入时,新元素之前没有别的结点了。因此,在这种情况下,将新元素的next指针指向当前链表的头部,然后重置头结点指针,使其指向新元素。回顾一下前一节中的接口设计,当传入的