《数据结构之美-- 单链表》
引言：
首先由上次我们实现的顺序表聊起，我们在实现顺序表的时候会发现，在每次插入数据时当空间不够时就会涉及到扩容，而顺序表的扩容一般都是呈二倍的形式来进行，因此这就有可能造成空间的浪费，那该如何解决这个问题呢，接下来要学到的链表就可以完美地解决这个缺点。
单链表
一. 初识单链表
1. 概念与结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据结构的逻辑顺序是通过链表中的指针链接次序实现的。
所以说单链表也是线性表的一种
2. 直观感受链表
其实我们可以由上图中的火车来类比链表，火车由火车头与一节一节的车厢链接起来，就组成了火车这个整体，其实链表也是像火车这样，是由一个一个的节点来链接起来的，火车的各节车厢是由挂钩链接的，而链表中的各个节点是由指针来链接的。
3. 链表的形式
（1）画图理解：
（2）代码实现：
二. 手搓单链表
1. 手动实现链表
2. 打印链表实现
（1）声明：--------------------------------------------------------------
（2）逻辑实现：
解析：打印链表，避免不了要遍历链表，所以这里的打印函数要将链表的首节点传过去，不然无法遍历链表，并且这里我们希望后面再找首节点的时候可以直接找到，所以这里在遍历链表时候我们定义了另外一个指针pcur来代替首节点来遍历链表，这里while循环的条件就是利用了链表最后一个节点的指针域为空的特性来实现的遍历，每次循环之后让指针移动到下一个节点，依次完成打印。
（3）测试：
三. 链表各项功能的实现
1. 尾插
（1）声明：
（2）思路整理：
（3）代码实现：
申请新节点
这里我们把申请新节点封装成了一个函数，方便后面我们在插入数据时进行直接调用
尾插实现
注意： 这里需要注意的是因为在逻辑实现中我们会改变指针的指向，因此这里必须为传址操作，因此这里传过去的是二级指针
（4）测试：
通过测试我们可以发现达到了尾插的效果
2. 头插
（1）声明：
（2）思路整理：
（3）代码实现：
写到这里，有同学可能会有一些疑惑：你这不是只写了第二种情况的逻辑吗？为什么说已经写完了呢？ 其实这个逻辑就同时满足了这两种情况，下面我们来看看
通过上图，相信同学们就对头插逻辑实现理解透彻了吧
（4）测试：
通过测试，可以看到我们的头插实现了预期的效果
3. 尾删
（1）声明:
（2）思路整理：
（3）逻辑实现：
（4）测试:
通过测试我们可以看到我们的尾删实现了预期的效果
4. 头删
（1）声明：
（2）思路整理：
（3）代码实现：
（4）测试：
*通过运行结果我们可以看到实现了头删的效果
5. 查找
（1）声明:
（2）思路整理：
（3）代码实现：
（4） 测试：
通过测试我们可以直观地看到我们的查找实现了预期效果
6. 在指定位置之前插入数据
（1）声明：
（2）思路整理：
（3）代码实现：
（4） 测试：
通过测试结果我们可以看到我们预期的结果已经实现了
7. 在指定位置之后插入数据
（1） 声明：
这里要注意这里的参数少了一个，因为在POS之后插入数据的话并不会影响POS之前的节点，就没必要再传原链表的首节点了
（2）思路整理：
但其实这里也会出现尾插的情况，但是也是满足这种逻辑的
（3）代码实现：
（4）测试：
通过测试我们看到特定位置之后插入数据也达到了预期的效果
8. 删除POS节点
（1）声明：
（2）思路整理:
（3）代码实现：
（4）测试：
通过代码运行结果我们可以看到达到了我们预期的效果
9. 删除POS之后的节点
（1） 声明：
这里注意这里的参数就只有一个了，因为要删除的是POS之后的数据，因此就不会用到头结点了
（2）思路整理：
分析完之后可能有同学还会担心会不会出现尾删的情况，其实尾删也可以有上述分析的逻辑来实现
（3） 代码实现:
（4）测试：
通过上面测试我们可以看到实现了删除POS位置之后的数据的效果
10. 链表的销毁
（1）声明：
（2）思路整理：
（3） 代码实现：
（4）测试：
销毁之前：
销毁之后：
关于顺序表和链表的思考
1. 顺序表中中间/头部的插入和删除的时间复杂度为O(n) 而在链表中的时间复杂度为O(1)
2. 顺序表的增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗，但是链表不需要频繁增容
3. 增容一般是呈两倍的形式增长，势必会有一定的空间浪费，而链表中是插入几个数据就申请几个节点的空间，不会存在空间的浪费
4. 但是综上几点也不能证明链表一定优于顺序表，比如在顺序表中的尾插/尾删的时间复杂度都为o(1)，而在链表中的时间复杂度为o(n)
5. 综上所述，顺序表和链表各有千秋，这也是我们为什么两个都要学的原因，所以今后在遇到问题时，用哪个合适就用哪个就可以了
原文地址：https://blog.csdn.net/2401_87465145/article/details/144449986
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！