单链表，就是通过指针把几个通过动态内存申请的节点连接在一起。
节点由两部分组成，第一部分是要存储的数据，第二部分是指针，指向下一个节点的地址。
节点
节点的定义
typedef int SLDataType;
typedef struct SListNode {
int data;
struct SListNode* next;
}SLTNode;//定义一个节点
注意，这里并不是递归，这里只是简单的通过指针来连接节点。
节点的创建
SListNode* SLBuyNode(SLDataType x) {//创建新的节点
SListNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL) {
perror("malloc fail!\\n");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
在这里我们选择使用malloc申请空间（选择其他的也可以）。需要注意的点就是申请空间并不一定能成功。
链表
链表的打印
链表打印的思路，是先传入链表的头节点，然后再通过节点中的指针一直往下遍历，直到遍历到尾节点的时候停止。这里可以通过while循环来实现
void SLTPrint(SLTNode* phead) {
SListNode* pcur = phead;
while (phead) {
printf("%d", phead->data);
phead = phead->next;
}
}
因为最后一个节点的next指针是NULL，所以循环在遍历到尾节点的时候正好结束。
链表的尾插
链表尾插的思路，首先就是找到链表的尾节点，然后再把尾节点的next指针指
向要插入的新节点。
这里有很重要的一个点，就是给尾插函数传递参数时，一定要传地址！！！
明明我传递一级指针就是节点的地址了，为什么形参用二级指针接收呢？因为如果传过来的链表为空的话，我尾插的节点就是头节点，那我原先传过来的一级指针应该指向新的节点（即现在的头节点），这里就需要改动一级指针的指向了。但是这里我们要通过函数调用实现形参对实参的改变，如果只是传一级指针的话，函数里对一级指针的副本进行操作，对外部的一级指针一点影响都没有，外部的指针还是NULL，因此，我们需要通过二级指针来改变一级指针的指向。
void SLTPushBack(SLTNode**pphead, SLDataType x) {//形参的改变要影响实参 必须要传地址！！！
assert(pphead);
SLTNode* newnode = SLBuyNode(x);
if (*pphead == NULL) {
*pphead = newnode;
}
else{
SListNode* ptail = *pphead;
while (ptail->next) {//找尾
ptail = ptail->next;
}
ptail->next = newnode;}
}
这里为了让代码更加健壮，我们考虑到无法对NULL空指针解引用，因此使用assert断言。
既然涉及到插入节点，那么我们就直接调用创建节点函数，把节点先创建好再插入进去。此时，分链表为空和链表不为空两种情况讨论：如果链表为空，那么要尾插的节点就是头节点；如果链表非空，那么就先找尾节点，然后再把尾节点的next指针指向尾插的节点。
第一个坑：链表打印函数和链表尾插函数的循环条件判断
让我们首先看打印函数的循环条件。
void SLTPrint(SLTNode* phead) {
SListNode* pcur = phead;
while (phead) {
printf("%d", phead->data);
phead = phead->next;
}
}
这里是while(phead)。在循环运行过程中，通过next指针不断向后遍历，在打印完第四个节点的内容时，指针指向空指针，判断条件为假，跳出循环。
再来看看尾插函数的循环条件。
void SLTPushBack(SLTNode**pphead, SLDataType x) {//形参的改变要影响实参 必须要传地址！！！
//找尾
assert(pphead);
SLTNode* newnode = SLBuyNode(x);
if (*pphead == NULL) {
*pphead = newnode;
}
SListNode* ptail = *pphead;
while (ptail->next) {
ptail = ptail->next;
}
ptail->next = newnode;
}
这里的循环结束条件是while(ptail->next)。为什么呢？原因是尾插函数需要将指针停在最后一个节点上，这里循环进行到第三个节点上时，条件为真，将第四个节点的地址赋给ptail指针，下一次循环时，已经不满足判断条件，指针最终停在了第四个节点上。如果采用的是和打印函数一样的while(phead)条件，那么指针最终会停在NULL上，无法进行后续的尾插操作了。
链表的头插
链表头插的思路，就是将要插入的节点中next指针指向原来的头节点，再把新插入的节点作为头节点。
void SLTPushFront(SLTNode**pphead, SLDataType x) {
assert(pphead);
SLTNode* newnode = SLBuyNode(x);
newnode->next = *pphead;
*pphead = newnode;}
链表的尾删
链表尾删的思路，就是先找尾节点，然后通过free函数把尾节点申请的空间释放掉。
第二个坑
在free之后，会出现野指针的问题。那么，就要把ptail指针置为NULL。同时，因为free函数已经把尾节点的操作权限还给了操作系统，那么前面一个节点的next指针就变成了野指针，这里也需要把它置为空指针。那这里就需要再创建一个prev指针来记录ptail在移动前的位置。
第二个坑中坑
如果链表中只有一个节点，那么又踩坑了。只有一个节点，free函数释放完之后，pre指针无法访问其对应的next指针，那这里就不考虑尾节点前面一个节点的next指针是否为野指针了。
void STLPopBack(SLTNode** pphead) {
assert(pphead&&*pphead);//不能传空链表也不能为空
if ((*pphead)->next == NULL) {
free(*pphead);
*pphead = NULL;
}
else {
SLTNode* prev = *pphead;
SLTNode* ptail = *pphead;
while (ptail->next) {
prev = ptail;
ptail = ptail->next;
}
free(ptail);
ptail = NULL;
prev->next = NULL;
}
}
链表的头删
头删的思路，就是用一个指针先存储第二个节点，再把头节点释放掉，最后再把第二个节点作为头节点。
void SLTPopFront(SLTNode** pphead) {
assert(*pphead && *pphead);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
链表元素的查找
查找的思路就是遍历链表来寻找匹配的元素，这里返回值的设置是为了配合后续指定位置增删元素的使用，返回的是元素的位置（节点的位置）。
SLTNode* SLFind(SLTNode* phead, SLDataType x) {
SLTNode* pcur = phead;
while (pcur) {
if (pcur->data == x) {
return pcur;
}
pcur == pcur->next;
}
return NULL;
}
指定位置之前插入节点
指定位置之前插入节点，思路就是先找到指定位置的节点，再配合指定位置之前的节点插入新节点。
void SLInsert(SLTNode** pphead, SLTNode* pos, SLDataType x) {
assert(pphead && *pphead);
assert(pos);
SLTNode* newnode = SLBuyNode(x);
if (pos==*pphead) {
SLTPushFront(pphead, x);
}
else {
SLTNode* prev = *pphead;
while (prev->next != pos) {
prev = prev->next;
}
newnode->next = pos;
prev->next = newnode;
}
}
第三个坑：特殊情况特殊讨论
如果要从头节点之前插入，那么while循环的判断条件一直都没法满足，那这里就会出问题。而在头节点之前插入，不就是要头插吗？那这里直接调用头插的函数就可以了。
在指定位置之后插入节点
void SLInsertAfter(SLTNode* pos, SLDataType x) {
assert(pos);
SLTNode* newnode = SLBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
这里在连接顺序的时候务必谨慎思考。
删除指定位置的节点
删除指定位置的节点的思路，就是先通过遍历来找到指定位置的节点，然后再把指位置前后的节点连接起来，再把指定为值的节点释放掉。
void Erase(SLTNode** pphead, SLTNode* pos) {
assert(pphead && *pphead);
assert(pos);
//pos是头节点//pos不是头节点
if (pos = *pphead) {
SLTPopFront(pphead);//是头节点，直接调用头删函数
}
else {//不是头节点
SLTNode* prev = *pphead;
while (prev->next != pos) {
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
第四个坑：依旧是特殊情况特殊讨论
如果是删除头节点，那么while循环又失效了，这里直接调用头删就行。
删除指定位置之后的节点
这里的思路，是先通过一个临时创建的指针变量把指定位置的后一个节点存储下来，再连接指定位置和指定位置往后第二个节点，最后释放指定位置之后的一个节点。
void SLEraseAfter(SListNode* pos) {
assert(pos);
assert(pos->next);//只有一个节点的链表无法在指定位置之后删除数据
SListNode* ptmp = pos->next;
pos->next = (pos->next)->next;
free(ptmp);
ptmp = NULL;
}
第五个坑：assert断言的条件
这里因为是删除指定位置之后的节点，那么这个链表的长度肯定要>=2个节点。
链表的销毁
既然动态申请了，那么就要销毁。销毁的思路是从头开始销毁，并且在销毁头节点之前要先存放头节点之后的那个节点的地址。最后不要忘了把原来的头节点置为空。
void SListDesTroy(SLTNode** pphead) {
assert(pphead&&*pphead);
SLTNode* pcur = *pphead;
while (pcur) {
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;//头节点也被释放了，避免成为野指针
}
总结
链表这一块的代码，个人的体会是一定要配合画图来写，并且要仔细考虑特殊情况，让代码更加健壮。
、
