知识卡片
插入先保留原后继
单链插入先让新节点指向原后继,再让前驱指向新节点,避免先覆盖唯一后继引用而丢失后段。头插没有普通前驱,要用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指针指向当前链表的头部,然后重置头结点指针,使其指向新元素。回顾一下前一节中的接口设计,当传入的