一、链表的概念
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
二、链表的分类
我们重点需要关注以下两个链表:
1.无头单向非循环链表
结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2.带头双向循环链表
结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。虽然结构复杂，但是使用代码实现，以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了
链表是通过一个个结点链接起来的数据结构，多个结点链接形成下列结构(箭头是不存在，是为了方便理解)
下列图片会简化结点间的链接过程：
【注意】:
- 从图上可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
- 现实中的节点一般都是从堆上申请出来的
- 从堆上申请的空间。是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续
四、实现无头单向非循环链表的相关接口(SLTlist.h)
五、知识铺垫
1.实现部分接口需要通过二级指针接受实参
原因在于我们需要可以修改实参，而是实参为一级指针时(同样是传递地址)，需要使用二级指针进行接受，否则获得临时拷贝，不会影响到实参。修改实参的情况，比如一开始为空，在插入时需将头指针存储在有效结点的的地址上，需要改变实参的值
2.单链表的初始化
这里实现链表，没有必要进行初始化，初始化对于一开始就要开辟的空间有初始化的需求，表是多个节点通过地址链接在一起，那么只需要开辟新节点的时候，初始化下就行了(有哨兵位需要初始化)
3.二级指针断言
二级指针存放的是头节点的地址，头节点的地址为空，那么还有什么意义呢?
当我们有所了解链表的结构，接下来是实现链表的相关接口，比如增删查改
六、正式开始模拟实现单链表
6.1 创建链表中的节点
在插入中需要先创建一块结点空间，再通过上一个结点通过当前结点的地址指向当前结点的位置。这是因为结点是通过地址访问的，结点里面存储着下一个节点的地址，理解为当前结点(通过下一个结点地址)指向下一个结点
SLNode* CreateNode(SLNDataType x) { SLNode* newnode = (SLNode*)malloc(sizeof(SLNode)); if (newnode==NULL) { perror("malloc fail!!!"); return (-1); } newnode->next = NULL; newnode->val = x; return newnode; }
这里需要注意的是:申请到的空间交给什么类型去维护，为结点(结构体)申请空间，就需要交给结构体指针维护，同时需要注意开辟空间可能会失败，比如开辟空间多大，无法提供空间。对新结点设置了指向下一个结点为空
6.2 单链表的插入节点
插入分为三类:头插\尾插\任意位置插入(其中任意位置插入，在实现查找功能先放着)
6.2.1 单链表的尾插
void SLTPushBack(SLNode** phead,SLNDataType x) { assert(phead); SLNode* newnode = CreateNode(x);//值已经有了,创建一个新节点 if (*phead == NULL)//这里需要二级指针去改变了，外的头了 { *phead = newnode; } else { //找尾 SLNode* cur =*phead;//拷贝一份 while (cur->next != NULL) { cur = cur->next; } cur->next = newnode;//newnode已经搞下一次是空了 } }
这里需要注意的是:while语句cur需要到达尾，再进行尾插的操作。同时需要考虑到特殊情况，这里我们通过if判断语句对于* pphead为空的情况，将*pphead存储在第一个结点地址。
6.2.2 单链表的头插
void SLTPushFront(SLNode** pphead, SLNDataType x) { assert(pphead); SLNode* newnode = CreateNode(x); if (*pphead == NULL) { *pphead = newnode; } else { SLNode* cur = *pphead; *pphead = newnode; newnode->next = cur; } }
这里需要注意的是:将*pphead移动到新节点的位置，再 * pphead指向cur(在原来的头节点位置)。同样的需要考虑到特殊情况，这里使用if判断语句对于* pphead为空的情况，将*pphead设为存储第一个结点地址。
6.3 单链表的删除
删除分为三类：头删\尾删\任意位置删除(其中任意位置删除，在实现查找功能先放着)
提前说明:空链表无法进行删除数据，需要在删除操作之前进行断言检查assert(*pphead)
6.3.1 单链表的尾删
void SLTPopBack(SLNode** pphead) { assert(pphead); assert(*pphead);//空的时候 //一个节点和多个节点 //这里不创建一个cur变量，当只有一个节点的时候，直接pphead SLNode* cur = *pphead; if (cur->next == NULL) { *pphead = NULL; free(cur); cur = NULL; } else { while (cur->next->next!= NULL) { cur = cur->next;//上一个节点 } free(cur->next); cur->next = NULL; } }
这里需要注意的是:删除需要分为两种情况存在一个节点和多个节点的处理。需要利用while循环找到删除节点的上一个节点，将上一个节点指向空，最后不要忘记free(cur->next)，释放当前节点空间。
6.3.2 单链表的头删
void SLTPopFront(SLNode** pphead) { assert(pphead); assert(*pphead); SLNode* cur = *pphead; if (cur->next == NULL) { *pphead = NULL; free(cur); cur = NULL; } else { *pphead = cur->next; free(cur); cur = NULL; } }
这里需要注意的是:删除需要分为两种情况存在一个节点和多个节点的处理。cur保存当头节点位置，*pphead移动到下一个节点的位置，再free(cur)
【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）（二）https://developer.aliyun.com/article/1617261
