博客大纲
单链表
定义
顺序表与链表都属于线性表，线性表可以简单理解为一个有限的序列。顺序表在线性表的要求上，要求数据在内存中是连续的，所以我们用动态内存开辟了一个连续的空间来放顺序表。相比于顺序表，链表就没有对内存的要求，只要求是一个有限的序列即可。
链表分为单链表以及双链表，这篇博客讲解单链表。
结构分析
在使用顺序表时，若遇到了内存不足时，一般会选择2倍扩容或者1.5倍扩容，这会导致一定内存的浪费。而对于链表，由于没有对内存的限制，完全可以用添加一个数据开辟一个空间，删除一个数据销毁一个空间。
但是，我们在使用顺序表时，由于所有空间都在一块，我们只需要一个指针就可以访问到整个顺序表。但是链表的内存是分散的，每开辟一个空间，就需要一个指针来访问这个内存。面对多个指针，要如何存储这些指针，并可以通过这些指针按一定顺序访问？
在此我们依然通过一个结构体来完成，每多一个元素就创建一个结构体，结构体内一个成员存储当前节点的数据，另外一个成员存储指向下一个节点的指针。 代码如下：
typedef int LLNDataType; typedef struct LinkListNode { LLNDataType val; struct LinkListNode* next; }LLNode;//重命名链表的节点为LLNode
变量名分析
LinkList：链表
LinkListNode：链表节点，使用重命名缩写为LLNode。其中Node代表节点。
LLNDataType：LinkListDataType 缩写，就是“链表数据类型”。此处使用LLNDataType来代替此链表的存储的数据类型，方便后续修改
val:
此处的val代表value，即当前节点存储的数据值。
next:
next存储的是指向下一个节点的指针，其类型也为struct LinkListNode*，即一个结构体指针。在需要访问下一个元素时，通过此处的next指针。
每个结构体都会指向下一个结构体，那么我们怎么在结构体外部找到这个链表，当链表遇到尾部没有下一个结构体该怎么办？
所以我们对头尾要进行额外的处理。此处我们可以利用一个外部指针phead来存储头节点的指针，而对于尾部的节点，其next指针成员赋值为NULL即可。那么最后链表的结构如下：
那么要如何使用一个这样的链表？
在使用这个链表前，用户需要创建一个结构体指针，来承载首元素指针，后续用户对链表访问时只通过此指针。
在链表没有节点时，将其赋值为NULL，若后续对链表进行了插入操作，返回此链表的首节点地址给用户创建的指针。
//用户创建指针： LLNode* phead = NULL;
创建节点接口
当我们进行插入操作时，就需要创建一个新的节点，并将此节点放到用户指定的位置。也就是说，创建一个节点是所有插入操作的基本，否则就没有空间存放需要插入的数据。
创建节点需要以下操作：
1.开辟一块空间存放此节点
2.对节点的val成员赋值
3.将节点的next指针成员赋值为NULL，避免野指针
我们通过代码分析细节：
//创建新节点 LLNode* CreateNode(LLNDataType x) { //创建空间，并用指针newnode维护此节点 LLNode* newnode = (LLNode*)malloc(sizeof(LLNode)); if (newnode == NULL)//确保开辟成功 { perror("malloc fail!"); exit(-1); } newnode->val = x;//将val赋值为指定元素 newnode->next = NULL;//将此节点的指针置NULL return newnode;//将此节点的指针返回 }
参数与返回值分析：
此接口只有一个参数x，即此节点的值，为何此接口不需要phead头指针？
注意，此处的创建节点不是用户直接操作的接口，因为用户只需要对链表增删查改，创建节点是插入节点的基本，当用户在使用插入节点的接口时，在插入接口调用此函数即可。我们此处的创建节点接口只需要完成创建节点并返回指针给插入接口即可。
空间开辟分析：
此处使用了malloc函数来开辟空间，并把此空间的指针返回给newnode。
malloc开辟空间时有可能失败的，当开辟失败，malloc就会返回NULL，这有可能会对链表结构造成不好的影响，比如此节点插入后，后续所有元素都被丢失了，如下：
此处链表插入一个malloc开辟错误后返回的空指针，此时节点2的next指向的就是一个空指针，而空指针是我们链表结尾的标志，那么此链表从节点3开始的所有数据都会丢失。
所以我们在开辟空间后需要判空，确保不为空了才能返回。
头插接口
想要在链表的最头部插入一个节点，相当于给链表换了一个头节点，那么此时phead必然会发生改变，此时我们就需要将新的节点地址返回给头指针，并将新节点的next指针成员指向原先的头节点。
头插过程如下：
1.创建新节点
2.将phead与新节点的指针修改
头插有两个值得讨论的问题：
传参分析（重点）
我们来分析一下，上述传参过程能不能完成对phead的指针修改。
我们传入的参数phead是一个结构体指针，此指针指向头节点。我们在头插过程中需要将phead重新赋值，此处我们若直进行赋值操作：phead = newnode；请问phead改变了吗？我们画图分析一遍：
红色箭头代表一个代码的执行过程，绿色箭头代表当前指针指向，绿色方框内代表此内存存的数值，方框上方的黑色数据代表此内存本身的地址。
传参前：
我们有一个phead指针，此指针本身存在0x0012ff40地址中，指向了首节点地址0x0012ff80。
传参后：
将phead存的值存入了参数phead中，参数phead得到的是首节点地址0x0012ff80。
赋值后：
此时想让头指针指向新节点newnode，使用phead = newnode，此时改变的是参数phead指向的值，phead本身没有被改变。后续再次访问头节点时，任然是原先的节点0x0012ff80，而不是改变后的节点0x0012ff96。
为什么会这样？回想在指针学习中的传值调用与传址调用，如果我们想改变一个int x，那么传参时参数类型就应该是int*类型，也就是传入x的地址。
而在此处，如果我们想改变LLNode*类型的phead，也应该传入phead的地址，我们就需要一个二级指针类型LLNode**作为参数。
此处要十分注意：并非传了指针就一定能修改想要的值，此处的指针传入后并没有对phead造成修改。
所以正确的传参应该是
void LLTPushFront(LLNode\** pphead, LLNDataType x)
红色细箭头代表传参过程，粗箭头代表修改后的节点指针关系，绿色箭头代表指针指向
在此图中，凡是被绿色指针指向的空间都是可以修改的，因为函数内部拥有它们的地址。
这种二级指针操作，第一次解引用可以访问phead，第二次解引用可以访问头节点，做到了既可以修改phead，又可以修改头节点。
赋值顺序
在链表的结构分析中我们提到，每一个节点的指针都是由前一个节点的next指针成员维护的，也就是说，每个节点的指针都只有前一个节点的next指针成员存储。
在此处如果先将newnode赋值给*pphead，那么此时phead就已经指向了新节点，而原先的头节点就会丢失，导致newnode的next指针成员找不到下一个节点了。
所以正确的赋值顺序应该是：
1.先将pphead的值赋给newnode->next
2.再将newnode的地址赋给pphead
最后的头插代码如下：
//头插 void LLTPushFront(LLNode** pphead, LLNDataType x) { assert(pphead);//确保指针有效性 LLNode* newnode = CreateNode(x);//接收函数创建的节点的指针 newnode->next = *pphead;//先将*pphead的值赋给newnode->next *pphead = newnode; //再将newnode的地址赋给*pphead }
尾插接口
找尾分析：
用户拥有的是一个phead指针，即链表头指针，也就是说我们是无法直接定位链表的尾部的。我们每一个节点的指针都在上一节点的next指针成员中，所以想要找到链表的尾部，就需要遍历此链表。遍历链表就会有一个不断改变的指针变量，假设此变量为tail，当tail->next == NULL时，tail指针指向的空间就是最后一个节点了，此过程称为找尾。图示如下：
特殊情况分析：
有没有一种情况，此链表还是一个空链表时，用户就执行了尾插？那么此时phead还是一个NULL，创建新节点后，要将phead指向新的头节点，说明我们在尾插实现的时候要用if语句判断一下，如果链表为空，就只要对phead修改。此外，我们在头插时分析过，想要修改phead，传参时就要传入LLNode** pphead。
尾插过程如下：
1.创建一个新节点
2.判断pphead是否为NULL，若为NULL则将新节点赋值给pphead
若不为空，执行以下过程：
3.找尾
4.将尾部节点的next指针成员指向新节点
代码如下：
//尾插 void LLTPushBack(LLNode** pphead, LLNDataType x) { assert(pphead);//确保指针有效性 LLNode* newnode = CreateNode(x);//创建节点 if (*pphead == NULL)//此处需要改变phead，所以要传入pphead { *pphead = newnode;//条件成立，修改phead } else { LLNode* tail = *pphead;//创建临时变量 while (tail->next != NULL)//找尾 { tail = tail->next; } tail->next = newnode; //将尾节点的next指针成员指向新节点，此后新节点就是新的尾节点了 } }
头删接口
在删除的接口中，最重要的问题就就是先前讨论的，先将谁赋值给谁的问题。注意，我们在删除接口的时候，需要一个指针维护这个被删除的节点，因为这个节点是需要free的，这个指针可以是创建的临时变量，也可以是上一个节点的next指针成员。所以此处我们有两种思路：
思路1：
我们最终要free的是头节点的地址，但是当头节点被free后，我们就丢失了维护第二个节点的指针。于是我们利用tmp来先保存第二个节点的指针，然后free掉头节点，此时phead还是指向原先的空间，于是再把tmp的值赋给phead。
void LLTPopFront(LLNode** pphead) { assert(pphead); assert(*pphead); LLNode* tmp = (*pphead)->next; free(*pphead); *pphead = tmp; }
思路2：
我们最终要free的是头节点的地址，但是当头节点被free后，我们就丢失了维护第二个节点的指针。于是我们在头节点被free前，先访问其值，赋给phead，此时phead就已经指向了第二个节点，我们就丢失了原先头节点的地址。所以我们要先创建一个临时变量tmp，来存头节点地址，然后当头节点将其下一节点指针交给phead后，通过tmp来free头节点即可。
void LLTPopFront(LLNode** pphead) { assert(pphead); assert(*pphead); LLNode* tmp = *pphead; *pphead = (*pphead)->next; free(tmp); }
尾删接口
尾删思路如下：
1.找尾
2.free掉原先的尾部节点
3.将尾部节点的前一个节点的next指针成员置空
找尾分析
与尾插一样，想要删除，先找尾。但是我们在思路中提到，我们还需要将尾部节点的前一个节点置空，那么我们还要找尾部节点的前一个节点，这该如何是好？
假设我们已经找尾一次，已经有一个tail指针指向了当前的尾部。那么我们再找一次尾，用tail2指针，当tail2->next == tail时，tail2指针是不是就指向了倒数第二个节点？此思路固然可以，但是这个算法需要遍历两遍链表。
在此，当我们需要找链表的头尾以外节点的时候，不妨试试双指针思路：
创建一个tail指针，一个prev指针，每当tail走一步之前，先把prev赋值为tail。这样一来，prev指针指向的就一直是tail前面的一个节点了。这样我们只需要遍历一次数组，我们就会得到两个指针，一个指向尾节点，一个指向尾节点前一个节点。
特殊情况分析
当我们的链表中只有一个节点时，头节点就是尾节点，当我们删除了头节点，就需要对phead置空，所以我们此处传参也要传LLNode** pphead。并单独讨论只有一个节点的情况。只要头节点的next为空，那么就说明此链表只有一个节点。
代码如下：
//尾删 void LLTPopBack(LLNode** pphead) { assert(pphead); assert(*pphead); if ((*pphead)->next == NULL)//当第一个节点的next为空，说明此链表只有一个节点。 {//单独讨论一个元素的作用：当销毁掉第一个元素后，要将phead置空 free(*pphead);//free头节点 (*pphead) = NULL; //置空phead } else { LLNode* tail = *pphead;//最后指向尾部的指针 LLNode* prev = NULL;//最后指向尾节点前一个节点的指针 while (tail->next != NULL) { prev = tail; tail = tail->next; } free(tail);//free掉原先尾节点 tail = NULL;//养成free后置空的习惯，避免野指针。 prev->next = NULL; //将原先存住的倒数第二个节点的next置空 } }
查找节点地址接口
写一个查找接口，找到某个数字，返回其地址，没找到返回空指针：
其实只需要遍历一遍链表，只要目标数字和此节点的val值相同即可。
代码如下：
//查找 LLNode* LLTFinde(LLNode* phead, LLNDataType x) { assert(phead); LLNode* cur = phead; while (cur)//此循环用于遍历链表 { if (cur->val == x)//条件成立，说明找到节点，返回指针 { return cur; } cur = cur->next; } return NULL; }
此接口对后续的与pos位置有关的接口十分重要。
在目标节点前插入的接口
传参分析：
与上方的头插尾插一致，如果对一个空链表插入，就需要修改phead，所以要传入pphead。
而此处我们是要在目标节点插入，那用户要如何获得目标节点？
我们刚刚写了一个接口，用于找到一个数据的地址。比如用户想在val = 3前插入一个节点，那就先用查找接口找到val = 3的地址，再将val = 3的节点地址传入此接口，就可以完成在val = 3节点前插入一个节点的操作。我们将此参数命名为pos，即position。
过程：
1.判断链表是否为空链表，当为空时，直接执行头插接口
不为空执行以下操作：
2.创建新节点
3.将新节点的next指向目标节点
4.将目标位置前一个节点的next指向新节点
通过代码分析细节：
//在pos位置前插入一个节点 void LLTInsert(LLNode** pphead, LLNode* pos, LLNDataType x) {//由于单向链表无法找到上一个元素的地址，所以要再传入一个头指针 assert(pphead); assert( (pos && *pphead) || (!pos && !*pphead));//要么都是空，要么都不是空 if (*pphead == pos) { //if成立，说明为空链表，直接进行头插 LLTPushFront(pphead, x); } else { LLNode* prev = *pphead;//找到目标位置前一个节点 while (prev->next != pos) { prev = prev->next; } LLNode* newnode = CreateNode(x);//此处的赋值顺序先前分析过 prev->next = newnode; newnode->next = pos; } }
assert断言分析：
我们在此分析一下pos，phead，pphead的空指针情况。
pphead
必定不可能为空指针，因为phead就算为空，也会有地址存放phead。若pphead为空了，要不然就算传参错了，要不然就是这个链表根本没有创建出来。
phead与pos
phead是可能为空的，因为phead有可能是空链表，那么此时对phead插入，就是一个头插过程。但是空链表没有元素，在查找时，返回值一定为NULL，也就是说pos一定为NULL。所以说如果phead为NULL，pos也一定为NULL，它们必须同为空，或者同为有效指针才行。此处我们利用一个这样的写法：
assert( (pos && *pphead) || (!pos && !*pphead))就可以完成以上判断。
找尾分析：
我们在此处需要使用前一个节点的next来指向新节点，也就是说我们要找到目标节点pos的前一个位置的节点。创建prev指针，我们只需要遍历一遍链表，当prev->next == pos的时候，prev就指向了pos前一个节点。
此外，我们还有一种不使用头指针的插入写法：想要在pos位置前插入，其实我们可以直接在pos位置后面插入一个节点，然后将pos后的节点的值与pos节点的值交换，这样就相当于完成了在pos位置前插入一个值：
//不使用头指针在pos前插入： void LLTInsert2(LLNode* pos, LLNDataType x) { assert(pos); LLTInsertAfter(pos, x);//在pos后插入 pos->next->val = pos->val;//交换pos与pos后新建节点的数据，相当于在pos前插入 pos->val = x; }
在目标节点后插入的接口
此接口较为简单，只需要将pos–>next指向新节点即可。
代码如下：
//在pos后插入 void LLTInsertAfter(LLNode* pos, LLNDataType x) { assert(pos); LLNode* newnode = CreateNode(x); newnode->next = pos->next; pos->next = newnode; }
在目标节点后删除的接口
想要删除pos后面的节点，首先要确保pos后面有节点，所以要判断pos->next是不是NULL，如果为空，说明pos是最后一个节点，删除就是没有意义的，所以加入一个断言assert(pos->next);。
代码如下：
//在pos后删除 void LLTErasetAfter(LLNode* pos) { assert(pos); assert(pos->next); LLNode* tmp = pos->next->next;//利用tmp存储pos的下下个节点 free(pos->next);//释放pos节点的下一个节点 pos->next = tmp;//将pos->next指向下下个节点 }
此处任然有一个问题，如果pos是倒数第二个位置，pos->next->next这样的操作会不会报错？
答案是不会的，当pos为倒数第二个节点，那么删除的就是尾节点，删除尾部节点后，pos就成了尾节点。而pos->next->next刚好就是NULL，赋给pos后，pos就符合尾节点的要求了。
删除目标位置接口
特殊情况分析：
当我们的pos是第一个节点时，删除此节点，头节点就会发生改变，所以要对phead更改。此处我们直接用if语句判断，如果pos确实是头节点，就调用头删接口。
找尾分析：
我们之前在讲解pos前插入一个节点时分析过，使用一个prev指针，来指向pos前的一个节点。在插入新节点时，将prev存储的节点指向新节点。在此处我们也需要一个prev指针，当pos节点删除后，用prev存着前一个节点的地址，使prev->next指向pos后一个位置。
代码如下：
//删除pos位置 void LLTErase(LLNode** pphead, LLNode* pos) { assert(pphead); assert(*pphead); assert(pos); if (*pphead == pos)//单独讨论只有一个元素情况，防止空指针 { //头删 LLTPopFront(pphead); } else { LLNode* prev = *pphead; while (prev->next != pos)//如果不分开讨论第一个元素，此处prev永远找不到pos，死循环后崩溃 { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } }
销毁链表
销毁链表，就要将所有节点都free掉。但是当我们free掉前一个节点，后一个节点的地址就丢失了，所以我们需要在遍历链表时，使用一个临时变量tmp来存储当前节点的下一个节点，当当前节点被释放后，指针指向tmp存的下一个节点。
代码如下：
//销毁链表 void LLTDestroy(LLNode** pphead) { assert(pphead); LLNode* cur = *pphead; while (cur) { LLNode* tmp = cur->next; free(cur); cur = tmp; } *pphead = NULL; }
单链表代码展示：
LinkList.h：
#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int LLNDataType; typedef struct LinkListNode { LLNDataType val; struct LinkListNode* next; }LLNode;//重命名链表的节点为LLNode //输出链表 void SLTPrint(LLNode* phead); //创建节点 LLNode* CreateNode(LLNDataType x); //头插 void LLTPushFront(LLNode** pphead, LLNDataType x); //尾插 void LLTPushBack(LLNode** pphead, LLNDataType x); //头删 void LLTPopFront(LLNode** pphead); //尾删 void LLTPopBack(LLNode** pphead); //查找 LLNode* LLTFinde(LLNode* phead, LLNDataType x); //在pos位置前插入一个节点 void LLTInsert(LLNode** pphead, LLNode* pos, LLNDataType x); //不使用头指针在pos前插入： void LLTInsert2(LLNode* pos, LLNDataType x); //在pos后插入 void LLTInsertAfter(LLNode* pos, LLNDataType x); //在pos后删除 void LLTErasetAfter(LLNode* pos); //删除pos位置 void LLTErase(LLNode** pphead, LLNode* pos); //销毁链表 void LLTDestroy(LLNode** pphead);
LinkList.c：
#include "LinkList.h" //输出链表 void SLTPrint(LLNode* phead) { //不断言，phead可以为空 LLNode* cur = phead; while (cur != NULL) { printf("%d->", cur->val); cur = cur->next; } printf("NULL\n"); } //创建节点 LLNode* CreateNode(LLNDataType x) { //创建空间，并用指针newnode维护此节点 LLNode* newnode = (LLNode*)malloc(sizeof(LLNode)); if (newnode == NULL)//确保开辟成功 { perror("malloc fail!"); exit(-1); } newnode->val = x;//将val赋值为指定元素 newnode->next = NULL;//将此节点的指针置NULL return newnode;//将此节点的指针返回 } //头插 void LLTPushFront(LLNode** pphead, LLNDataType x) { assert(pphead);//确保指针有效性 LLNode* newnode = CreateNode(x);//接收函数创建的节点的指针 newnode->next = *pphead;//先将*pphead的值赋给newnode->next *pphead = newnode; //再将newnode的地址赋给*pphead } //尾插 void LLTPushBack(LLNode** pphead, LLNDataType x) { assert(pphead);//确保指针有效性 LLNode* newnode = CreateNode(x);//创建节点 if (*pphead == NULL)//此处需要改变phead，所以要传入pphead { *pphead = newnode;//条件成立，修改phead } else { LLNode* tail = *pphead;//创建临时变量 while (tail->next != NULL)//找尾 { tail = tail->next; } tail->next = newnode; //将尾节点的next指针成员指向新节点，此后新节点就是新的尾节点了 } } //头删 void LLTPopFront(LLNode** pphead) { assert(pphead); assert(*pphead); LLNode* tmp = (*pphead)->next; free(*pphead); *pphead = tmp; } //尾删 void LLTPopBack(LLNode** pphead) { assert(pphead); assert(*pphead); if ((*pphead)->next == NULL)//当第一个节点的next为空，说明此链表只有一个节点。 {//单独讨论一个元素的作用：当销毁掉第一个元素后，要将phead置空 free(*pphead);//free头节点 (*pphead) = NULL; //置空phead } else { LLNode* tail = *pphead;//最后指向尾部的指针 LLNode* prev = NULL;//最后指向尾节点前一个节点的指针 while (tail->next != NULL) { prev = tail; tail = tail->next; } free(tail);//free掉原先尾节点 tail = NULL;//养成free后置空的习惯，避免野指针。 prev->next = NULL; //将原先存住的倒数第二个节点的next置空 } } //查找 LLNode* LLTFinde(LLNode* phead, LLNDataType x) { assert(phead); LLNode* cur = phead; while (cur)//此循环用于遍历链表 { if (cur->val == x)//条件成立，说明找到节点，返回指针 { return cur; } cur = cur->next; } return NULL; } //在pos位置前插入一个节点 void LLTInsert(LLNode** pphead, LLNode* pos, LLNDataType x) {//由于单向链表无法找到上一个元素的地址，所以要再传入一个头指针 assert(pphead); assert((pos && *pphead) || (!pos && !*pphead));//要么都是空，要么都不是空 if (*pphead == pos) { //if成立，说明为空链表，直接进行头插 LLTPushFront(pphead, x); } else { LLNode* prev = *pphead;//找到目标位置前一个节点 while (prev->next != pos) { prev = prev->next; } LLNode* newnode = CreateNode(x);//此处的赋值顺序先前分析过 prev->next = newnode; newnode->next = pos; } } //不使用头指针在pos前插入： void LLTInsert2(LLNode* pos, LLNDataType x) { assert(pos); LLTInsertAfter(pos, x);//在pos后插入 pos->next->val = pos->val;//交换pos与pos后新建节点的数据，相当于在pos前插入 pos->val = x; } //在pos后插入 void LLTInsertAfter(LLNode* pos, LLNDataType x) { assert(pos); LLNode* newnode = CreateNode(x); newnode->next = pos->next; pos->next = newnode; } //在pos后删除 void LLTErasetAfter(LLNode* pos) { assert(pos); assert(pos->next); LLNode* tmp = pos->next->next;//利用tmp存储pos的下下个节点 free(pos->next);//释放pos节点的下一个节点 pos->next = tmp;//将pos->next指向下下个节点 } //删除pos位置 void LLTErase(LLNode** pphead, LLNode* pos) { assert(pphead); assert(*pphead); assert(pos); if (*pphead == pos)//单独讨论只有一个元素情况，防止空指针 { //头删 LLTPopFront(pphead); } else { LLNode* prev = *pphead; while (prev->next != pos)//如果不分开讨论第一个元素，此处prev永远找不到pos，死循环后崩溃 { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } } //销毁链表 void LLTDestroy(LLNode** pphead) { assert(pphead); LLNode* cur = *pphead; while (cur) { LLNode* tmp = cur->next; free(cur); cur = tmp; } *pphead = NULL; }
