引言
数据结构之路通过了顺序表，就进阶来到了链表 ，本节内容为最简单的链表——单链表（Single Linked List）
顺序表的问题及思考
让我们回顾一下顺序表：
1. 中间/头部的插⼊删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容⼀般是呈2倍的增长，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
思考：如何解决以上问题呢？
链表的概念与结构
概念：链表是⼀种物理存储结构上非 连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
链表的结构跟火车车厢相似，将火车里的某节车厢去掉/加上，不会影响其他车厢，每节车厢都是 独立存在 的。
车厢是独立存在的，且每节车厢都有车门。想象⼀下这样的场景，假设每节车厢的车门都是锁上的状态，需要 不同的钥匙 才能解锁， 每次只能携带⼀把 钥匙的情况下如何从车头走到车尾？
最简单的做法：每节车厢里都放⼀把下⼀节车厢的钥匙。
在链表里，每节“车厢”是怎样的呢？
与 顺序表 不同 的是，链表⾥的每节"车厢"都是 独立申请 下来的空间，我们称之为 “结点/节点”
节点的组成主要有两个部分：当前节点要保存的 数据 和保存下⼀个节点的 地址 （指针变量）。
图中指针变量 plist保存的是第⼀个节点的地址，我们称plist此时“指向”第⼀个节点，如果我们希望plist“指向”第⼆个节点时，只需要修改plist保存的内容为0x0012FFA0。
为什么还需要指针变量来 保存 下⼀个节点的位置？
链表中每个节点都是 独立申请 的 （即需要插入数据时才去申请⼀块节点的空间） ，我们需要 通过指针变量 来保存下⼀个节点位置才能从当前节点 找到下⼀个节点 。
单链表的实现
定义
这里注意，在结构体内嵌套结构体，一定要表明struct，而不能直接使用typedef后的名称（要不然你可能会像我一样，一脸懵得看着n个错误提示 ）
打印
先来看看怎么实现链表的打印，这样更有助于我们理解它的结果
先用cur指针接受头部地址，当cur不为NULL时，则打印当前节点的数据，并将该节点存储的下一节点的地址赋值给cur ，这样cur指针就能一直访问整个链表，直到最后一个节点（该节点存储地址为NULL）
头插
链表插入数据，则要生成一个新节点（malloc动态开辟内存），再将数据放入新节点中，初始地址为NULL。然后再将之前的头部地址赋值给新节点的next指针，最后把新节点的地址赋值给头部地址（也就是外部传进来的链表指针）。
可能很多人有疑惑，为什么要用二级指针呢？请看接下来的测试
与顺序表不同的是，我们不再创建结构体，而是创建结构体指针，初始指向NULL。那么，我们要在函数内改变外部指针指向的地址，就要使用二级指针。
改后版本（后面有介绍原因）
创建新节点
我们发现，进行尾插时，同样要生成新节点，申请空间……一系列操作 ，所以我们可以把它该过程写成一个函数，以增强函数的复用性
尾插
同样，先申请新节点，再用循环一直向后访问，找到最后一个节点的地址，解引用操作将新节点的地址赋值给节点内的next指针变量
易错提醒： 要找的是最后一个节点的地址，而不是节点内部的next中的地址（NULL），所以千万不要写成以下形式，不然不仅链接不上，还会造成内存泄漏！
此时你可能会有疑惑，这里好像也不用二级指针也可以呀？实际上，并不可以。因为没有考虑到空链表的存在（你可以试试直接尾插会发生什么后果）
如果为NULL，则直接将新节点的地址传给外部的链表指针
运行结果
尾删
尾部删除的实现思路，主要是找到倒数第二个节点，解引用将其next指针指向的空间（最后一个节点）释放，再赋值为NULL
方法一
除了tail指针，再创建一个prev指针，每次先将tail中的地址赋值给prev，tail再指向下一个节点。当tail指向最后一个节点时，prev则指向倒数第二个节点
方法二
tail指针解引用当前节点的next后，继续找到下一个节点进行第二层解引用 （相当于探测范围往后移了一个节点），最终停止时，tail也指向倒数第二个节点
有了之前的经验，在调试中我们发现，以上方法只适用于多个节点，但是单个节点与空链表并未处理
对于一个节点，我们直接释放空间，并赋值为NULL；而对于空链表，我们直接断言assert，保证其不为空（暴力检查）
运行结果
这样，我们就实现了特殊到一般的思路，也是正常程序调试和优化的思路
头删
那么此时，我们有了经验，直接按空链表，一个节点和多个节点的思路实现
头部删除的实现思路 ，就是将链表指针的地址改成第二个节点的，并将第一个节点的空间释放
仅靠一个指针无法完成操作，因为链表指针指向第二个节点后，无法对第一个节点操作，所以再创建一个cur指针，记录第一个节点的地址，方便释放
但是此时，我们又发现，其实对多个节点的操作，对一个节点同样有效，所以我们可以简化代码
运行结果
所以，我们不仅要有分类的思想，也要有整合的思想，化一为多，化多为一。
