引入
前面我们学习了如何找到和读取单链表中的数据,今天我们继续看看,如何在单链表中插入数据元素。
单链表中插入元素
我们既然知道,元素内存储的是数据域和指针域,一个指着另一个,呈链性存储。那么如果要在这样的链表中插入一个元素该如何处理呢?
其实也就是
- S 结点存储的地址,改成 P 存储的地址
- P 存储的地址改成 S 结点的地址
- S-> next = P->next
- P->next = S
我们看一下图
思考一下
这两句代码的顺序可不可以点到过来?
- S-> next = P->next
- P->next = S
改成
- P->next = S
- S-> next = P->next
也就是先让 p->next 等于 S 的地址
然后在把 S->next 赋值为 P->next
答案肯定是不行的!
因为 p->next 指向的是 p 的下一个元素
如果先让 p->next 指向 S 的地址
那么谁也不知道 p 的下一个元素的地址了
所以顺序一定不要错!先新再旧!
先让插入的等于原来的,再改原来的等于新插入的。
插入数据的算法思路
我们清楚了该如何插入数据之后,我们来看看这个算法
- 指向:声明结点 p 指向链表头结点。
- 遍历:初始化 j 从1开始,当 j<i 时,就遍历链表,让 p 的指针向后移动,不断指向下一个结点,j++。
- 失败:若到链表末尾 p 为空,则说明第 i 个元素不存在。
- 成功: 查找成功,在系统中生成一个空节点 S
- 将数据元素 e 赋值给 s->data
- 将空结点的指针指向上一个结点的 next
- 将上一个结点的 next 指向该空结点的位置
- 返回成功
代码实现
C语言动态生成单链表,然后在第二个元素插入元素,再输出所有元素。
1 |
|
伪代码实现
1 |
|
尾巴
这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。