一、链表的一些基础知识
1.节点的结构
1.对于每个数据元素，除了存储其本身信息以外，为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，我们需要存储一个其直接后继的存储位置。我们把存储数据元素信息的域成为数据域，把存储后继位置的域称为指针域，这两部分构成一个节点。
2.n个节点链接成一个链表，即为线性表的链式存储结构。因为每个节点只有一个指针域，所以又将这样的链表称为单链表。
3.图像助解
单链表节点结构
链表示意图
2.节点的实现
链表是由节点构成的，想要实现一个链表就要先要实现一个节点,而节点又是由数据域和指针域构成的，然而我们现在需要把这两种不同类型的数据组装在一起，这时我们就可以想到用一个结构体把这两种不同的数据类型组装在一起。
代码实现
typedef int SLTDataType;//对数据类型进行重命名 typedef struct SListNode { SLTDataType data;//数据域的元素 struct SListNode *next;//指针域的元素 }SLTNode;
节点结构
二、链表的一些基本操作
1.链表的所有操作展示
//动态申请一个节点 SLTNode* BuySLTNode(SLTDataType e); //动态申请n个节点 SLTNode* CreateList(int n); //打印链表 void SLTPrint(SLTNode*phead); //单链表的尾插 void SLTPushBack(SLTNode**pphead,SLTDataType e); //单链表的尾删 void SLTPopBack(SLTNode**phead); //单链表的头插 void SLTPushFront(SLTNode**pphead,SLTDataType e); //单链表的头删 void SLTPopFront(SLTNode** pphead); //单链表的查找 SLTNode* SLTFind(SLTNode* phead,SLTDataType e); //单链表的插入(pos位置后插) void SLTInsertAfter(SLTNode* pos, SLTDataType e); //单链表的插入(pos位置之前插入) void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType e); //单链表的删除(删除pos位置) void SLTDelete(SLTNode**pphead,SLTNode*pos); //单链表的销毁 void SLTDestroy(SLTNode** pphead);
当然上面的操作很多，但也并不是所有单链表是这样的，不同的单链表有不同的函数，但上面的函数足够我们使用了。对于其他人写的单链表可能还会有其他的函数，例如还有一些单链表有：判空函数，返回链表长度等函数。
2.链表的初始化
链表的初始化其实就是向操作系统申请一个节点，并且给它赋上初始值。
链表是一种动态结构，它所占用的大小和位置是不需要提前分配的，可以根据自身的需求即时生成，所以我们在初始化一个链表时要动态分配内存。
代码实现
//初始化，动态申请一个节点 SLTNode* BuySLTNode(SLTDataType e)// e是要初始化的值 { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//动态申请一个节点的大小 if (!newnode)//防止申请失败 { perror("malloc");//申请失败，打印错误信息 exit(-1);//程序错误，退出程序 } newnode->data = e;//初始化数据 newnode->next = NULL;//初始化指针 //返回头指针方便以后我们管理这个链表 return newnode; }
新申请的newnode节点
3.动态申请n个节点
链表的初始化可以帮我们申请一个节点，如果我们现在需要存储100个数据，难道我们要一个一个初始化申请吗？那这效率也太低了吧！所以我们需要实现一个可以帮我们一次性完成的函数。
代码实现
//动态申请n个节点 SLTNode* CreateList(int n) { int i = 0; //分别定义一个头指针，和一个尾指针 SLTNode* phead = NULL,* ptail = NULL; //循环次数即为创建的节点个数 for (int i = 0; i < n; i++) { //调用初始化函数申请一个节点 SLTNode* newnode = BuySLTNode(i); //由于头指针开始是NULL，所以先给头指针赋值第一个节点的位置 if (phead == NULL) { ptail= phead = newnode; } else { //将新申请的节点进行链接 ptail->next = newnode; //让尾指针一直处于结尾位置，方便我们链接新节点 ptail = newnode; } } //返回头指针方便以后我们管理这个链表 return phead; }
当然这种简单的实现方式相当于每个节点中的数据，被赋值为 1，2，3… n。
如果你想赋值为你想要的数据，可以提前定义一个数组，并将数组中的数据赋值为你们想要的，然后改变一下此函数的参数将数组首元素地址传递过去，就可以实现你想要的效果了。
4.打印链表
打印链表的逻辑就很简单了，我们把链表的头指针传过去，然后从头开始遍历整个链表，把每一个数据都打印出来，这不就完成我们的任务了吗？
那么现在我们就讨论，怎么才能够遍历整个数组呢？
我们知道单链表最后一个节点的指针域里面放的是NULL，利用这个特点，只要头指针不为空，就打印该节点的数据，并且把头指针指向下一个节点，以此类推，直到遇到NULL，代表遍历结束，打印结束
代码实现
//打印链表 //phead是头指针，即指向第一个节点的地址的指针 void SLTPrint(SLTNode* phead) { while (phead!=NULL) { printf("%d->", phead->data); //打印完之后指针后移 phead = phead->next; } //这句代码可以不加，只是为了方便展示链表的逻辑结构 printf("NULL\n"); }
5.单链表的尾插
尾插的意思就是：在链表的尾部插入一个新节点，使插入的节点变成新的尾节点。新的节点我们可以通过初始化函数来申请一个新节点，这并不是太大的问题，那剩下的插入问题我们应该怎么去实现它呢？
我们可以先考虑特殊情况：
1.如果链表的头指针phead是NULL怎么办？
如果链表头指针是NULL，说明链表中一个数据也没有，那我们新插入的节点，就要成为头节点，这个时候我们的头指针就要改变指向新插入的节点。
什么？头指针要改变？
没错！头指针要改变！那么我们要好好想一想我们的函数参数要怎么设计了！
我们以前在学习函数传参时有说过值传递的方式。函数传参如果是传数据本身，那么形参是实参的一份临时拷贝，形参在函数内部无论如何改变都不会影响外部的实际参数，并且函数销毁时形参也会销毁！
但是现在我们却想在函数内部让形参头指针发生改变并且函数外面传递的实参头指针也要发生改变，即让实际参数发生改变，那这就要用到址传递了！（如果实际参数不变，那链表还是NULL）
我们知道，如果我们向函数传递实际参数的地址，那么函数的形参通过解引用是可以访问实际参数的，并且如果形参通过解引用的方式改变实际参数是确确实实改变了实参！在函数销毁时，实际参数也被形参改变了，这种传递方式造成的影响是很大的。
这里我们再思考一个问题:看下面一个代码，我们进行址传递，看看它改变了什么类型？
//交换两个变量的值 void Swap(int* pa, int* pb) { int tmp = *pa; *pa = *pb; *pb = tmp; } int main() { int a = 10, b = 20; Swap(&a,&b); printf("%d %d", a, b); }
显而易见，我们传地址过去，形参用int *接收，结果通过解引用在函数内外都改变了int类型里面的值，那如果我们给一个函数传递int **，那结果通过解引用在函数内外能不能改变了int*类型里面的值呢？
答案是可以的！这就是二级指针! 一级指针通过解引用可以改变变量的值，二级指针通过解引用可以改变一级指针的内容！
再回头看看我们的目标 点这里跳转 我们要在函数内外部都要改变头指针，而头指针是int*类型，所以函数的参数要设计为int**类型了
理解了这一步就好办了，只有一个参数显然还是不够的，还要再来一个数据参数，才能让函数变得完整，不然指针数据域里面没有值怎么办？
2.一般情况：
由于函数的头指针不是NULL，我们就能进行解引用操作了！给头指针备份一个新的指针ptail让它遍历整个链表成为链表的尾部，再让新申请的节点链接在ptail的尾部，这样我们就尾插完成了！
代码实现
//链表的尾插 void SLTPushBack(SLTNode** pphead, SLTDataType e)//pphead是头指针的地址，e是新节点中的数据域中的数据 { SLTNode* newnode = BuySLTNode(e);//申请一个新节点，新节点中的数据域中的元素是e SLTNode* ptail = *pphead;//给头指针备份一个新指针，头指针不能移动，否则找不到第一个节点 if (*pphead == NULL)//头指针为NULL要单独处理 { *pphead = newnode;//把新申请的节点地址赋值给phead,要改变phead那么就要使用二级指针pphead } else { while (ptail->next != NULL)//判断有没有到最后一个节点 { ptail = ptail->next;//将下一个节点的地址赋值给ptail } //while循环退出了，说明ptail现在指向最后一个节点 ptail->next = newnode;//将新申请的节点赋值到ptail的尾部，完成尾插 } }
如果这里理解了的话，那下面就很简单了！
6.单链表的尾删
尾删的意思也很简单：就是删除单链表中最后一个节点，那我们怎么去实现它呢？老样子，先讨论特殊情况！由特殊到一般！
1.头指针phead为NULL
好奇怪的情况？没有节点，还要删除数据？（黑人问号.jpg）这种情况直接报错！一个断言就搞定了！
assert(phead);
2.头指针phead只有一个节点
这个时候我们就要删除尾节点，并且让头指针改变成NULL，啊？头指针又要改变，实际参数要改变吗？（思考中…) 要改变！不然的话实际参数指针还是指向以前的尾节点，但是尾节点已经释放了，我们头指针再去访问就要发生错误了，所以为了避免野指针的出现，我们还是要传递二级指针！
3.一般情况
我们还是老思路遍历整个链表，但是这次有所不同。我们要判断当前节点的下一个节点的下一个节点是不是NULL，（有点小绕，但不是很难，仔细理解，看图）如果是NULL说明当前节点是倒数第二个节点！我们就释放下一个节点就行了，当然不要忘了把当前指针的指针域置为NULL，不然会造成野指针！
代码实现
//单链表的尾删 void SLTPopBack(SLTNode** pphead) { //暴力检查，防止头指针phead为NULL assert(*pphead); SLTNode* cur = *pphead;//备份一个头指针,cur代表当前指针位置 //只有一个节点要单独处理，头指针必须改变 if ((*pphead)->next == NULL) { free(*pphead);//释放当前节点 *pphead = NULL;//用二级指针，改变头指针phead } else { //判断当前节点的下一个节点的下一个节点是不是NULL while (cur->next->next != NULL) { //如果不是NULL，cur向后移动一个节点 cur = cur->next; } free(tail->next);//释放掉最后一个节点，完成尾删 tail->next = NULL;//倒数第二个节点别忘记置为NULL，防止野指针的出现 } }
7.单链表的头插
头插，就是在链表的头部插入一个节点，使新插入的节点成为头节点，这显而易见要用二级指针嘛！所以函数的参数肯定要设计一个二级指针，另外一个参数肯定要传递一个数据参数。继续使用由特殊到一般的思想
1.头指针为NULL
我们可以用初始化函数申请一个newnode节点，然后，将头指针链接在newnode的后面，然后将newnode的值赋值给头指针，这样头插就完成了，这对我们来说是非常容易实现的。
这样一想，好像头指针是NULL，也不影响我们把头指针链接在newnode的后面，然后改变头指针赋值为newnode,这说明这种情况并不特殊。
2.一般情况
通过1.头指针为NULL的分析，我们发现没有什么特殊情况，我们直接按照1.头指针为NULL的分析，去实现函数就行了。
代码实现
//单链表的头插 void SLTPushFront(SLTNode**pphead, SLTDataType e)//pphead是头指针的地址，e是新节点中的数据域中的数据 { SLTNode* newnode = BuySLTNode(e);//新申请一个节点 newnode->next = *pphead;//将头节点链接到newnode的尾部,完成链表的链接工作 *pphead = newnode;//用二级指针改变头指针，使头指针指向头部位置，完成头插 }
可以看出单链表的头插是非常高效简单的，这是单链表的一个特性。
8.单链表的头删
头删，就是把头指针指向的节点给删除，然后将头指针指向下一个节点，显而易见，头指针发生了变化，我们当然要用二级指针了。
代码实现
//单链表的头删 void SLTPopFront(SLTNode** pphead) { assert(*pphead);//头指针不能为空指针 SLTNode* tmp = *pphead;//保存头指针的地址，方便释放 *pphead = (*pphead)->next;//头指针指向下一个节点 free(tmp);//释放前一个头节点，防止内存泄漏 }
可以看出单链表的头删是非常高效简单的，这也是单链表的一个特性。
9.单链表的查找
单链表中的元素很多，但是我们想要我们指定的元素，那么我们应该怎么办呢？这个时候，我们就需要用到单链表的查找了。
单链表的查找就是在单链表中找到自己选定的数据，我们可以通过遍历这个链表来找到我们想要的数据，我们的函数参数可以是一个头指针（此时我们不需要传递二级指针，因为我们只是遍历链表，而不是去改变链表的头指针），还有一个要查找的数据。好了，明白了函数的参数后我们就可以动手去实现这个函数了。
代码实现
//单链表的查找 SLTNode* SLTFind(SLTNode* phead,SLTDataType e) { while (phead)//头指针不为空，就继续遍历链表 { if (phead->data == e)//如果数据与我们查找的数据相等就返回该节点的地址; { return phead; } phead = phead->next;//头指针后移 } return NULL;//找不到就返回空指针 }
10.单链表的插入
我们在前面已经实现了，单链表的头插与尾插，但是只有这些是远远不够的，我们还要有更一般性的插入，但是插入有许多形式，我们是在指定位置（pos）之前插入，还是之后插入呢？不妨我们都去实现一下，然后对比那个更简单更高效。
1.在pos之后插入
根据链表的特性，我们链表知道一个节点就可以查找到下一个节点，所以在pos之后插入还是很简单的。
思路：我们可以用单链表的查找来找到指定位置（pos）,然后利用初始化函数创建一个新节点（newnode），让newnode链接到pos的下一个节点，让pos链接newnode,这样我们也就完成了插入。
但是我们有没有可能改变头指针呢？（头指针改变的话要用二级指针）答案是不可能，因为我们要改变头指针，pos必须为空指针，pos为空指针就是查找不到，既然查找不到，我们为什么还要插入呢？所以这种情况是不应该被插入的！
代码实现
//单链表的插入(pos之后插入) void SLTInsertAfter(SLTNode* pos, SLTDataType e) { assert(pos);//pos不能为空指针，不然插入没有意义 SLTNode* newnode = BuySLTNode(e);//创建一个新节点 newnode->next = pos->next;//让新节点链接到pos的下一个节点 pos->next = newnode;//让pos链接新节点，插入就完成了。 }
2.在pos之后插入
我们单链表知道一个节点，查找前一个节点，这是做不到的！所以在pos之前插入还是有些困难的。
思路：虽然是困难的，但是我们可以通过遍历来保存前一个节点，这样我们就可以仿照前面的思路（1.在pos之后插入）来进行实现，只不过这一次相当于pos改成了pos的前一个。
但是这个时候我们就要考虑头指针会不会改变了？如果pos是头指针的位置，我们就要在头指针前面插入一个新节点（newnode）,这个时候我们就要让头指针前移了，这个时候我们就要考虑使用二级指针了！
思路分析完毕我们就要开始去实现我们的代码了。
代码实现
//单链表的插入(pos之前插入) void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType e) { assert(pos);//pos不能为空指针，不然插入没有意义 if (pos == *pphead)//如果pos为头指针，相当于前插 { SLTPushFront(pphead, e);//用前插解决问题 } SLTNode* prev = *pphead;//定义一个前指针，用来保存pos的前一个位置 while (prev->next != pos)//如果prev的下一个不是pos就继续执行 { prev = prev->next;//prev后移 } SLTNode* newnode = BuySLTNode(e);//创建一个新的节点 if (!newnode)//防止申请失败 { perror("malloc");//申请失败就打印错误信息 exit(-1);//退出 } newnode->next = pos;//让新节点链接到pos prev->next = newnode;//让pos的前一个节点链接新节点 }
对比一下我们可以发现，在pos之后插入是比较简单和高效的，我们可以多使用pos之后插入。
11.单链表的删除
最后单链表的“增删查改”,就只剩下了删除了,在单链表中删除某个节点，就是释放该节点的内存，但是释放节点时，我们应该先找到该节点的前一个节点，因为我们要改变它的指向关系。这时我们又要考虑特殊情况了，如果pos是头指针，那么我们就要改变头指针了，所以我们的函数参数可以设计为二级指针
代码实现
//单链表的删除(删除pos位置) void SLTDelete(SLTNode** pphead, SLTNode* pos) { assert(pos);//pos不能为空指针，不然插入没有意义 if (*pphead == pos)//如果pos为头指针要单独处理 { *pphead=pos->next;//头指针指向下一个 free(pos);//释放原来的头指针 return;//结束函数 } SLTNode* prev = *pphead;//定义一个前指针，用来保存pos的前一个位置 while (prev->next!=pos)//如果prev的下一个不是pos就继续执行 { prev = prev->next;//prev后移 } prev->next = pos->next;//pos的前一个节点指向pos的后一个节点 free(pos);//释放pos位置的节点 //使用完此函数后记得在该函数下面加一条 pos=NULL;防止野指针的出现 }
12.单链表的销毁
这是最后一步操作了，当我们使用单链表处理完了我们的数据，我们不再需要该单链表了，要对单链表进行销毁，不然会造成内存泄漏！
思路：我们可以遍历这个链表，挨个挨个进行释放，但是我们在释放时要提前保存下一个节点，否则当前节点释放后，会找不到下一个节点。
代码实现
//单链表的销毁 void SLTDestroy(SLTNode** pphead) { SLTNode* cur = *pphead;//定义一个指针，指向当前位置方便向后遍历 SLTNode* nextnode = *pphead;//定义一个指针，指向当前位置的下一个节点，用来保存节点 while (cur != NULL)//当前指针不为NULL就继续向后遍历 { nextnode=cur->next;//保存下一个节点 free(cur);//释放当前节点 cur=nextnode;//将保存的节点赋值过去 } *pphead = NULL;//将头节点置为NULL，防止出现野指针 }
13.单链表功能汇总
#include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLTDataType;//对数据类型进行重命名 typedef struct SListNode { SLTDataType data;//数据域的元素 struct SListNode *next;//指针域的元素 }SLTNode; //动态申请一个节点 SLTNode* BuySLTNode(SLTDataType e) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//动态申请一个节点的大小 if (!newnode)//防止申请失败 { perror("malloc"); exit(-1); } newnode->data = e;//初始化数据 newnode->next = NULL;//初始化指针 return newnode; } //动态申请n个节点 SLTNode* CreateList(int n) { int i = 0; SLTNode* phead = NULL,* ptail = NULL; for (int i = 0; i < n; i++) { SLTNode* newnode = BuySLTNode(i); if (phead == NULL) { ptail= phead = newnode; } else { ptail->next = newnode; ptail = newnode; } } return phead; } //打印链表 void SLTPrint(SLTNode* phead) { while (phead!=NULL) { printf("%d->", phead->data); phead = phead->next; } printf("NULL\n"); } //链表的尾插 void SLTPushBack(SLTNode** pphead, SLTDataType e) { SLTNode* newnode = BuySLTNode(e); SLTNode* ptail = *pphead; if (*pphead == NULL)//*pphead==NULL要单独处理 { *pphead = newnode; } else { while (ptail->next != NULL) { ptail = ptail->next; } ptail->next = newnode; } } //单链表的尾删 void SLTPopBack(SLTNode** pphead) { //暴力检查 assert(*pphead); SLTNode* tail = *pphead; //只有一个节点要单独处理 tail->next==NULL不能解引用 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } } //单链表的头插 void SLTPushFront(SLTNode**pphead, SLTDataType e) { SLTNode* newnode = BuySLTNode(e);//不必考虑*pphead==NULL newnode->next = *pphead; *pphead = newnode; } //单链表的头删 void SLTPopFront(SLTNode** pphead) { assert(*pphead);//不用考虑单节点 SLTNode* tmp = *pphead; *pphead = (*pphead)->next; free(tmp); } //单链表的查找 SLTNode* SLTFind(SLTNode* phead,SLTDataType e) { while (phead) { if (phead->data == e) { return phead; } phead = phead->next; } return NULL; } //单链表的插入(pos之后插入) void SLTInsertAfter(SLTNode* pos, SLTDataType e) { assert(pos); SLTNode* newnode = BuySLTNode(e); newnode->next = pos->next; pos->next = newnode; } //单链表的插入(pos之前插入) void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType e) { assert(pos); if (pos == *pphead) { SLTPushFront(pphead, e); } SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } SLTNode* newnode = BuySLTNode(e); if (!newnode) { perror("malloc"); exit(-1); } newnode->next = pos; prev->next = newnode; } //单链表的删除(删除pos位置) void SLTDelete(SLTNode** pphead, SLTNode* pos) { assert(pos); if (*pphead == pos) { *pphead=pos->next; free(pos); return; } SLTNode* prev = *pphead; while (prev->next!=pos) { prev = prev->next; } prev->next = pos->next; free(pos); //使用完此函数后记得在该函数下面加一条 free(pos),防止野指针的出现 } //单链表的销毁 void SLTDestroy(SLTNode** pphead) { SLTNode* cur = *pphead; SLTNode* nextnode = *pphead; while (cur != NULL) { nextnode=cur->next; free(cur); cur=nextnode; } *pphead = NULL; }
结束
看到这里，相信你对单链表的认识也提高了不少，单链表掌握以后，后面更加复杂的链表都是在对单链表进行变形罢了，掌握单链表的处理方法后去处理它们也是大同小异，所以一定要好好掌握单链表！
当然如果本篇文章有错误的地方，欢迎评论或私信讨论！那么我们下期见，byebye!
