✅作者简介：大家好我是@每天都要敲代码，一位材料转码农的选手，希望一起努力，一起进步！
📃个人主页：@每天都要敲代码的个人主页
💬在我们学习的过程中，肯定需要刷题，巩固所学知识点；给大家推荐一款模拟面试、刷题神器，从基础到大厂面试题👉点击跳转刷题网站
前言：Hello！大家好，我是@每天都要敲代码，上一期给大家带来了线性表之===》顺序表，没有学会的小伙伴可以再去学习一下吧！传送门 接下来我们先分析一下顺序表：
顺序表问题：
问题1：中间/头部的插入删除，都要进行数据的移动，时间复杂度为O(N)。
问题2：增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
问题3：增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
思考：
如何解决以上这种问题呢？下面给出了链表的概念和结构来看看。
概念和结构：
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
结构：
种类：
实际中要实现的链表的结构非常多样，以下情况组合起来就有
1. 单向、双向
2. 带头、不带头
3. 循环、非循环
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都
是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带
来很多优势，实现反而简单了。有了前面这些概念和结构，相信大家对链表已经有了初步的理解和印象，接下来让我们来一起学习无头单向非循环链表：
目录
无头单向非循环链表：
1.创建单链表：SListNode
单链表创建的结构和顺序表是很相似的，这里我们只需要两个参数，一个data用来存储数据；一个next指针，用来指向下一个地址；并且我们用的是无头单向非循环链表，所以我们才开始的头指针plist初始化为NULL！那如果是带头结点的单链表呢？此时的plist就需要初始化成为一个malloc开辟的地址，这个等我们下一期讲到带头双向循环链表就会用到，这里就不在赘述。
2.尾插函数的实现：SListNodePushBack
动态开辟空间的函数：SListNodeCreat
在这里的无论是插入还是删除，我们都可以去画图理解，这样也能防止写错。我们每次的插入都需要malloc动态开辟一个空间，所以不妨直接封装成一个函数SListNodeCreat，便于后面的使用，并且我们在开辟空间时，如果能开辟成功了，就把newnode给赋值上：newnode->data = x newnode->next = NULL，下面看动态开辟空间的函数实现。
具体代码如下：
动态开辟空间成功后，我们就开始尾插，这时就需要我们画图去理解了：
情况1：链表里本身就有很多数据，我们这时只需要找到尾结点(暂定为tail)，把tail->next=NULL改成tail->next = newnode就可以，至于newnode->next=NULL就不需要写了，因为我们开辟空间时就已经让newnode->data=x和newnode->next=NULL了，下面看具体逻辑图：
情况2：像我们现在刚开始使用的的一样，才开始就是一个空链表，我们第一次就进行了尾插，此时的*pphead和tail肯定都为空指针，这时我们只需要把才开辟的空间newnode赋值给*pphead就可以了，具体逻辑图：
所以尾插时我们要考虑这两种情况，具体代码如下：
尾插几个数据我们先打印验证一下，具体打印函数下面就会给出：
3.打印函数的实现：SListNodePrint
打印函数也很简单，这里就不在多说，直接给出代码：
4.头插函数的实现：SListNodePushFront
对于头插函数就很简单了，它不像顺序表那样还需要移动后面的元素，所以无论是空链表还是有元素的链表都是一样的；这里通过指针直接链接，下面看具体逻辑图：
下面看具体代码：
我们不妨头插一个0，进行打印验证：
之后我们也可以屏蔽掉前面尾插的函数，直接对空表进行头插，进行验证：
5.尾删函数的实现：SListNodePopBack
对于尾删函数的实现可能就比较麻烦了，我们还是需要分情况讨论，先从最普通的情况进行画图分析，然后在把哪些特殊的情况单独拿出来分析：
情况1：链表里本身有很多元素，我们进行尾删时怎么办呢？肯定需要找到尾指针tail，因为我们malloc动态创建的，最后不使用了肯定要free释放掉；那还需要知道什么呢？我们还需要把最后一个指针的next置为空啊！我们都已经释放掉尾指针tail怎么找它前面一个指针prev把它的next置位空呢？所以我们还需要一个指针prev记住tail的前一个指针，下面看逻辑图：
情况2：如果是空链表呢？我们直接return退出不就好了，就不需要我们去删除了！
情况3：如果只有1个节点呢？尾结点就是头结点，尾结点tail前面根本没有一个节点prev怎么办呢？我们就直接释放掉当前的节点，然后置空就可以了：
下面看具体代码：
不妨尾删一个数据测试结果：
6.头删函数的实现：SListNodePopFront
对于头删函数我们也是先考虑普通情况，在考虑特殊情况：
情况1：链表里本身有很多元素，我们进行头删：
情况2： 只有一个节点的情况也是包含于情况1的，完全是没问题的；接下来再看一下空链表；空链表就不需要头删，直接return就可以。
下面看具体代码：
我们头删一个数据测试结果：
7.修改函数的实现：SListNodeModeify
查找函数的实现：SListNodeFind
这里我们要明确一点，无论是修改、任意位置插入、任意位置删除，都是需要查找函数SListNodeFind，因为它不像顺序表那样可以直接给出下标去插入、删除。这里必须根据数据去搜索，返回地址，根据地址进行任意插入和删除。既然这样，我们不如封装一个查找函数，并且对于查找函数我们也可以用传值调用，因为它并不需要改变数据；但是这里为了保持统一，我用的都是传址调用。
下面看具体代码：
有了查找函数，我们就可以根据查找返回的pos地址来修改数据了，具体代码如下：
我们不妨就把数据2改成数据200，测试结果：
8.任意位置插入函数的实现：SListNodeInsert
对于任意位置插入，我们也还是要先调用查找函数SListNodeFind；然后调用SListNodeCreat进行动态开辟空间。我们根据查找函数SListNodeFind返回的pos地址，在pos地址进行插入操作，具体如下：
情况1：我们还是先考虑普通情况，特殊情况单独拿出来讨论；首先我们肯定要得到pos的前一个位置prev，然后prev->next = newnode，然后newnode->next = pos就可以啦：
情况2：如果是在第一个节点之前插入呢？它同样是没有pos的前一个节点prev，此时怎么办呢？最简单的办法当然是调用头插函数SListNodePushFront啦！当然我们可以去验证在最后一个节点tail前插入也是没问题的；至于空链表的情况，我们会给出限制条件；根本不会让它调用SListNodeInsert函数：
具体代码如下：
我们不妨在1前面插入100，测试一下：
9.任意位置删除函数的实现：SListNodeDelete
同样的思路，我们先考虑普通情况，在分析特殊情况：
情况1：我们既然要删除pos位置，就要知道pos的前一个位置prev，这样才能使prev->next = pos->next；中间跳过pos，具体逻辑图如下：
情况2：问题又来了，如果还是在pos = *pphead位置删除呢？这样pos又没有前一个地址prev，怎么办呢？最简单的方法还是调用以前的函数，这里调用头删函数SListNodePopFront，具体逻辑图如下：
具体代码如下：
我们删除数据3并测试一下结果：
10.求大小函数的实现：SListNodeSize
对于求大小很简单，我们定义一个计数器count就行，这里就不再多数，直接上代码。
具体代码如下：
11.销毁函数的实现：SListNodeDestory
链表的销毁和顺序表不同，顺序表是连续的空间，free一次就可以；而链表创建的空间是不连续的，我们malloc多少次，就需要free多少次，下面看具体代码：
具体代码如下：
所有具体代码：
总结：对于链表的操作，我的建议是一定要画图分析，特别是接下来的双链表；另外就是我们在写各种各样的函数接口，可以先考虑最普通的情况，把特殊的情况单独拿出来进行分析！！！这里我通过画图和文字分析的形式把基本上所有接口都分析了一遍，希望对各位有所帮助；感兴趣的同学也可以写成项目工程的格式！！！
如果对各位有所帮助，请点赞支持一波，万分感谢！！！
结束语
今天的分享就到这里，想要提升编程思维的，快快去注册牛客网开始刷题吧！各种大厂面试真题在等你哦！
💬刷题神器，从基础到大厂面试题👉点击跳转刷题网站
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/128537.html
