目录
1.什么是链表
1.问题引入
2. 链表的概念及结构
3. 问题解决
2.单向链表接口的实现
1.接口1，2---头插，尾插
2. 接口3，4---头删，尾删
3. 接口5---查找
4. 接口6，7---插入，删除
5. 接口8---打印
6. 注意事项总结
3.完整代码及效果展示
1.问题引入
上期我们讲解了顺序表的基本概念和实现方法（传送门：）。但是顺序表存在着如下三个问题：
那么这些问题要如何解决呢？通过链表， 我们就可以很轻松的解决以上问题。下面，就让我们感受链表的魅力吧！
2. 链表的概念及结构
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。它的结构如下所示(以单向链表为例)：
我们把date和next形成的结构体称为链表的一个结点，我们可以看到，链表就是由一个个结点链接起来的非连续线性结构，不同结点通过next指针连接的，最后一个结点的next指针指向空。链表也是线性表中的一种。
当然，在实际应用中，链表的结构多种多样，通过以下几种情况组合而成的就有8种链表结构：
1. 单 向 、 双 向
2. 带 头结点 、 不 带 头结点
3. 循 环 、 非 循 环
本期我们讲解的是实际应用中最常用的两种结构之一：单向不带头非循环链表。（另外一种是带头双向循环链表）
3. 问题解决
通过以上链表结构，我们就能很好地解决顺序表的局限：
- 每当我们需要新增数据时，我们只需申请一个新结点用来保存数据，然后用指针将链表与新结点链接起来即可，并不需要进行数据拷贝。
- 由于使用链表存储数据总是处于满载状态，每个结点都是有效数据，需要插入时则申请新结点并与链表连接，因此就不存在空间浪费的问题。
- 链表的结构是线性非连续的，各结点通过指针连接。如果需要在头部或中间插入数据，只需改变结点指针的指向即可，无需再移动数据。
首先，在实现各种接口函数前，我们需要定义一个结构体来代表每一个结点，用date保存结点中的数据，用next保存下一结点的地址。同样的，我们采取typedef的方式将类型重命名方便代码的编写与维护。如下：
由于我们实现的单向链表是不带头结点的，所以我们还需要定义一个指针指向链表的第一个结点(下面称为头指针)。
1.接口1，2---头插，尾插
对于头插，我们只需要创建新结点保存数据，然后将头指针指向新结点，新结点指向原来头指针指向的结点即可，动态效果如下：
具体代码如下：
值得注意的是，函数中我们传入的是头指针的地址。这是由于我们需要修改头指针使其指向新的结点，因此需要采用址传递的方式，用二级指针接收，否则只会修改临时变量造成出错。
对于尾插，我们需要先找到链表的尾结点，然后将尾结点的next指向新结点，动态效果如下：
代码如下：
但是，上述代码是存在问题的。我们知道->相当于是一种解引用，当链表为空时，即tail==NULL时，此时我们进行tail->next操作显然是非法的，所以我们还需对链表为空的情况做出讨论，最终代码如下：
2. 接口3，4---头删，尾删
对于头删，我们只需要将头指针指向下一个位置，然后将原来指向的空间free()掉即可。如果链表为空，我们就让函数直接返回，具体动态效果如下：
在代码实现中，我们需要先创建一个临时变量next来保存下一个结点的地址，这是因为free()后就无法通过->得到下一个结点的地址了。具体代码如下：
对于尾删，我们同样需要找到尾结点。这里和尾插不同的是，我们除了要找到尾结点，还需找到尾结点的前一个结点并使其next置为空，因此我们可以使用两个指针prev和tail进行移动，prev指向tail的上一个结点，具体动图如下：
具体代码如下：
这里和头删一样，当链表为空时直接让函数返回。但是以上代码依旧存在着一个问题，就是当链表只有一个结点时，tail直接指向尾结点，此时prev为NULL，禁止对其进行->操作。所以我们还需要对只有一个结点的情况进行讨论，最终代码如下：
3. 接口5---查找
对于查找，我们只需遍历链表的所有结点即可，故不需要头指针，只需传一级指针即可。当找到需要查找的date时，返回对应结点的指针，若没找到或者链表为空时，返回NULL，代码如下：
4. 接口6，7---插入，删除
对于插入，我们可以实现一个在指定结点前插入一个新结点的接口，而这个指定结点我们可以通过查找接口来获取。相同的，在进行插入操作时我们还需要得到前一个结点的地址，我们用prev来存储，然后将prev->next改为新结点地址，新结点的next为我们传入的结点的地址。动态效果如下：
(嘿嘿，我又来了qwq)，上述的代码其实还是存在bug的，就是当我们传入的指定结点为头结点时，prev->next永远不可能等于pos，prev不断向后更新，最终为NULL导致程序崩溃。动态分析如下：
因此我们需要进行分类讨论，而我们发现如果pos指向头结点，那在其前面插入不就相当于头插吗？所以我们可以直接调用头插接口，改进后的代码如下：
对于删除，我们同样可以实现一个删除指定结点的接口，而这个指定结点我们依旧可以通过查找接口来获取。同样，除了将指定的结点free()掉，还需将其上一个结点的next指向pos的下一结点。与插入一样都需要找到上一个结点的位置，在这过程中可能引发的问题也是一样的，这里就不再赘述了，直接上代码：
5. 接口8---打印
对于打印，只需从头结点开始，向后遍历链表，打印每个结点的date直到走到链表尾即可，此时指针指向NULL。由于不修改头指针指向，因此采用值传递即可，用一级指针接收。代码如下：
6. 注意事项总结
通过上面一个个接口的实现，我们得出以下两个值得注意的地方：
- 当我们需要修改头指针时，如插入删除操作时，需要使用址传递，用二级指针来接收头指针的地址。而如果我们不需要修改头指针时，如打印，查找等，建议使用值传递，用一级指针来接收，避免头指针被意外修改。
- 在实现链表接口时，需要时刻考虑到当链表为空，链表只有一个结点，对头结点进行操作，对尾结点进行操作等特殊情况是否会出现bug。
我们可以采用多文件编写的形式，将上述接口的定义实现放在SList.c文件中，然后将接口的声明和结构体的定义放于SList.h头文件中，以达到封装的效果。这样我们如果需要使用单向链表，就只需要在文件中包含对应的头文件SList.h就可以使用我们上面定义的各种接口。以下为本文实现的单向链表完整代码以及效果展示：
最后， 我们在text.c文件调用单向链表各个接口进行测试，如下：
以下就是测试的最终效果：
以上，就是本期的全部内容。
制作不易，能否点个赞再走呢qwq
到此这篇单向链表数据结构（单向链表结构图）的文章就介绍到这了,更多相关内容请继续浏览下面的相关推荐文章，希望大家都能在编程的领域有一番成就！版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/sjkxydsj/58279.html