前言：Hello！大家好，我是@每天都要敲代码，上一期给大家带来了线性表之===》顺序表，没有学会的小伙伴可以再去学习一下吧！传送门 接下来我们先分析一下顺序表：

顺序表问题：

问题1：中间/头部的插入删除，都要进行数据的移动，时间复杂度为O(N)。

问题2：增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

问题3：增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考：

如何解决以上这种问题呢？下面给出了链表的概念和结构来看看。

概念和结构：

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

结构：

种类：

实际中要实现的链表的结构非常多样，以下情况组合起来就有 =8种链表结构：

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怎么办呢？我们就直接释放掉当前的节点，然后置空就可以了：

下面看具体代码：

不妨尾删一个数据测试结果：