前言
对于初学者来说，单链表相比较于顺序表难度其实还是蛮大的，因为顺序表的实现无非是对数组进行操作，而数组大部分人都应该比较熟悉了。单链表却在本质上与顺序表有较大差异，不过不用担心，本篇文章将会使用非常详细的图文来帮助大家理解单链表是如何实现的。
文章结尾附带源码。
一、什么是单链表
我们知道，顺序表是指数据在内存中是连续存储的一个线性结构，单链表则是指数据在内存中是无需连续存储的一个线性结构。
啊？我没听错吧，不连续存储，那我如何找到呢？每个元素存放在内存中随机的位置，似乎需要借助指向元素的指针才能找到，莫非每存在一个元素，我们就要将其地址保存起来？是的，只有这样才能访问到其他的元素，关键是这个地址保存在哪，单链表是个线性结构，每个元素只与上一个元素和下一个元素相关，因此，解决办法则是——将元素的地址与上一个元素的数据存放在一起，组成一个结构体，这样就能解决单链表的链式访问了。
链表也分许多种类的，带头结点或者不带头结点的，单向的或者双向的，循环的或者不循环的，总共可以有 23 种组合，其中最常见的就属不带头结点的单向不循环链表和带头结点的双向循环链表了，我们本次介绍的单链表就是不带头结点的单向不循环链表。
二、单链表头文件的编写
为了使代码可读性高，分工明确，我们将一些库函数头文件，定义等放在一个文件里面。我们首先创建一个叫做 “SList.h” 的头文件。
1.引入库函数头文件
#include<stdio.h> #include<stdlib.h> #include<assert.h>
对上面的库函数头文件不清楚的可以查阅一下。
2.定义单链表结构体
// 宏定义单链表储存的数据的数据类型 typedef int SLNDataType; // 单链表结构体 typedef struct SListNode { // 单链表的数据域 SLNDataType val; // 单链表的指针域 struct SListNode* next; }SLNode;
由于单链表并非只会存储 int 类型的数据，也有可能存储其他类型的数据，例如 char 类型，但是改动的时候若是将每个 int 都去改写成 char 未免也太麻烦了，所以我们在这里采用宏定义的方法，将数据类型重命名为 SLNDataType 类型，以后改变数据类型就会方便很多。
在上文我们已经知道，单链表实际上是由一个存储数据的数据域和一个存储下一个元素的地址的指针域的结构体构成，所以我们创建一个结构体，包含数据域和指针域。其中，指针域的指针因为是指向下一个结构体的地址的，所以指针的类型为 struct SListNode* ，意为指向结构体的指针类型。并在最后将结构体重命名为 SLNode 。
注意，是先有的结构体的指针域，后有的结构体重命名，所以不能在结构体内的指针域写成 “SLNode* next”。
3. 声明单链表的功能函数
// 打印 void SLTPrint(SLNode* phead); // 创建新结点 SLNode* CreateNode(SLNDataType x); // 尾插 void SLTPushBack(SLNode** pphead, SLNDataType x); // 头插 void SLTPushFront(SLNode** pphead, SLNDataType x); // 尾删 void SLTPopBack(SLNode** pphead); // 头删 void SLTPopFront(SLNode** pphead); // 查找 SLNode* SLTFind(SLNode* phead, SLNDataType x); // 在任意结点前插入 void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x); // 删除任意结点 void SLTEarse(SLNode** pphead, SLNode* pos); // 销毁链表 void SLTDestroy(SLNode** pphead);
我们要实现的单链表是没有头结点的，链表没有有效数据就不存在链表，所以没有头结点的单链表是不需要初始化的。
这里有一个非常重要的细节，我们在进行对单链表的操作时，单链表一定是存在的吗？这当然不是，所以我们不能够通过创建结构体，然后把结构体的地址传给功能函数执行操作(万一根本没有链表就会出大问题了)。于是，我们在创建链表的时候，一般是创建一个指向首元结点的指针(开始时是指向 NULL 的)，头指针。对于那些可能改变头指针的操作，则需要传入头指针的地址，也就是二级指针来改变头指针的。所以在所有可能对头指针操作的函数，我们传入的参数都是 SLNode** pphead ，意为指向头指针的地址，其中，pp 就是二级指针的意思。
三、单链表主函数文件的编写
为了方便测试，我们将测试函数与主函数放在一起，在主函数里面调用不同的测试函数。我们创建一个叫做 “test.c” 的源文件
1.包含头文件
#include"SList.h"
2.编写测试用例
void test() { // 创建一个头指针plist并赋值为空 SLNode* plist = NULL; // 尾插操作 SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); // 打印 SLTPrint(plist); // 头删操作 SLTPopFront(&plist); SLTPopFront(&plist); // 打印 SLTPrint(plist); // 找到数据为3的结点并将其地址传递给pos SLNode* pos = SLTFind(plist, 3); // 在结点pos前面插入数据为6的一个结点 SLTInsert(&plist, pos, 6); // 打印 SLTPrint(plist); // 销毁链表 SLTDestroy(&plist); }
对于可能改变头指针的操作，传参都需要传入头指针的地址。对于不需要改变头指针的操作，传参无需传入头指针的地址，直接传头指针即可。
以上测试用例为我随意编写，读者可自己创建测试用例来验证结果。
3.主函数的编写
int main() { // 调用测试函数 test(); return 0; }
四、单链表功能函数文件的编写
同样的，我们将单链表的各个功能函数打包在一个文件夹里。我们创建一个叫做 “SList.c” 的源文件。
1.包含头文件
#include"SList.h"
2.打印函数的编写
// 打印函数不需要改变plist，所以传入plist即可，这里命名为phead void SLTPrint(SLNode* phead) { // 创建一个与头指针相同的，指向首元结点的指针 SLNode* cur = phead; // 遍历到链表最后 while (cur != NULL) { // 打印每个结点的数据域 printf("%d->", cur->val); // 指针通过指针域找到下一个结点的位置 cur = cur->next; } // 换行 printf("NULL\n"); }
3.创建新结点函数的编写
// 只需要传入新结点的值 SLNode* CreateNode(SLNDataType x) { // 通过malloc函数为新结点开辟空间，并创建一个指向新结点的结构体指针 SLNode* newNode = (SLNode*)malloc(sizeof(SLNode)); // 空间开辟失败 if (newNode == NULL) { // 打印错误并退出 printf("malloc fail"); exit(-1); } // 将x的值赋值给新结点的数据域 newNode->val = x; // 使新结点的指针域指向空 newNode->next = NULL; // 返回新结点的地址 return newNode; }
我们需要先用 malloc 函数为新结点开辟空间，不能直接创建结构体，因为创建的结构体是局部变量，出了作用域就会被销毁。而 malloc 函数开辟的空间出了作用域是不会销毁的。 malloc 函数从内存中开辟一个大小为 SLNode 字节的空间，并将其空间转换成 SLNode* 类型的指针传递给 newNode 指针。空间是有概率开辟失败的，因此开辟空间失败需要给出反馈并终止函数进行。将新结点创建成功后，我们再将 x 赋值给新结点的数据域，将 NULL 赋值给新结点的指针域，新结点的属性就设置好了，最后将新结点的地址返回即可。
4.尾插函数的编写
// 当链表无数据时，尾插会改变头指针，所以要传入头指针的地址 void SLTPushBack(SLNode** pphead, SLNDataType x) { // 头指针已被创建，头指针一定存在，所以指向头指针的pphead一定不可能为空，为空说明传参错误 assert(pphead); // 创建新结点 SLNode* newNode = CreateNode(x); // 当链表中还没有结点时，需要改变头指针 if (*pphead == NULL) { // 指向头指针的指针解引用就是头指针，让头指针指向新结点 *pphead = newNode; } // 当链表中最少有一个结点时 else { // *pphead指向首元结点，创建一个指向首元结点的指针 SLNode* begin = *pphead; // begin指针不断往后遍历，直到遍历到尾结点的位置 while (begin->next != NULL) { begin = begin->next; } // 改变尾结点的指针域，使其指向新结点 begin->next = newNode; } }
尾插函数最需要注意的就是判断链表是否为空，为不为空需要使用两种不同的方法来实现。因此传参需要传头指针的地址
头指针为空时需要让头指针指向新结点，头指针不为空需要让尾结点的指针域指向新结点。怎么去找尾结点呢？从首元结点开始，通过每一个结点的指针域找到下一个结点，让下一个结点的地址传给用来遍历的指针。如何判断到了尾结点呢？尾结点是链表的最后一个结点，其指针域没有指向任何存在的空间，尾结点的指针域指向 NULL (尾结点的指针域为 NULL )，当用来遍历的指针发现它指向的结点的指针域为空的话，说明到达了尾结点。到达了尾结点就可以改变尾结点的指针域，让尾结点的指针域指向新结点，使新结点成为新的尾结点。
头指针为空：
头指针不为空：
5.头插函数的编写
// 头插函数跟尾插函数一样，有可能改变头指针，所以也要传入头指针的地址 void SLTPushFront(SLNode** pphead, SLNDataType x) { // 头指针一定存在，所以头指针的地址一定不为空 assert(pphead); // 创建新结点 SLNode* newNode = CreateNode(x); // 让新结点的指针域指向原来的首元结点 newNode->next = *pphead; // 让头指针指向新结点，使新结点成为新的首元结点 *pphead = newNode; }
头插函数是一定会改变头指针的，所以要传递头指针的地址。
在创建新结点后，改变几个指针的指向的顺序必须要捋清楚，如果没有创建临时指针记录的话，倘若先让头指针指向新结点，再让新结点指向头指针指向的结点就会出现大问题，因为原本的首元结点的地址已经丢失，无法找到了，头指针已经指向新结点了。所以需要先让新结点的指针域指向头指针目前所指向的地址，再改变头指针的指向。
6.尾删函数的编写
// 尾删函数也有可能改变头指针，所以要传头指针的地址 void SLTPopBack(SLNode** pphead) { // 头指针一定存在，pphead一定不为空 assert(pphead); // 头指针必须不为空才可以执行删除操作 assert(*pphead); // 创建一个指向首元结点的指针 SLNode* begin = *pphead; // 如果链表只包含一个结点 if (begin->next == NULL) { // begin目前指向第一个且最后一个结点，释放掉最后一个结点的空间 free(begin); // 使指针begin指向空 begin = NULL; // 此时链表为空，让头指针指向空 *pphead = NULL; } // 当链表不止一个结点时 else { // begin指针遍历到倒数第二个指针 while (begin->next->next != NULL) { // begin指针不断往后走 begin = begin->next; } // begin指向倒数第二个结点，begin->next指向最后一个结点，释放掉最后一个结点的空间 free(begin->next); // 让原本倒数第二个结点的指针域指向空 begin->next = NULL; } }
有关删除的函数必须建立在链表存在结点的情况下才能正常执行，所以要在函数开头断言一下链表是否为空的情况。当链表只包含一个结点的时候，首元结点同时也是尾结点，要删除掉最后一个结点就是删除首元结点，这会改变头指针的指向，而链表不止一个结点的时候，尾删操作并不会改变头指针的指向，这两种情况需要分情况讨论。
当只有一个结点时，可以直接释放头指针所指向的空间，并让头指针赋值为 NULL 即可。
当链表不止一个结点时，我们创建一个用来遍历的链表的指针，由于单链表只能找到下一个结点，无法找到上一个结点，当用来遍历的指针指向最后一个结点的时候，释放最后一个结点的空间，此时用来遍历的指针已经无法找到原本的倒数第二个结点并修改其指针域为 NULL ，所以需要让用来遍历的指针遍历到倒数第二个结点，使用倒数第二个结点的指针域来找到并释放尾结点的空间，此时用来遍历的指针还指向的时是原来的倒数第二个结点，此时可以修改该结点的指针域为 NULL 。
链表只含有一个结点的时候：
链表不止一个结点的时候：
7.头删函数的编写
// 头删函数一定会改变头指针，要传头指针的地址 void SLTPopFront(SLNode** pphead) { // 头指针一定存在，pphead一定不为空 assert(pphead); // 链表不为空才允许指向删除操作 assert(*pphead); // 创建一个指向首元结点的指针 SLNode* begin = *pphead; // 让头指针指向首元结点的指针域所指向的空间 *pphead = begin->next; // begin目前指向原首元结点，释放掉原首元结点的空间 free(begin); // begin指针置空 begin = NULL; }
链表最擅长的就是对头部的操作，头删算是链表中最简单的操作了。只需让头指针指向首元结点的指针域所指向的空间就可以了，无论是下一个结点还是空值，都不需要另加判断。
8.查找函数的编写
// 查找函数不会改变头指针，但是要返回结点指针 SLNode* SLTFind(SLNode* phead, SLNDataType x) { // 空链表也属于找不到的一种，允许链表为空 // 创建一个指向首元结点的指针 SLNode* begin = phead; // 遍历链表 while (begin != NULL) { // 找到数据域与x相等的结点 if (begin->val == x) { // 返回结点地址 return begin; } // 指针根据指针域找到下一个结点 begin = begin->next; } // 找不到返回空 return NULL; }
查找函数与打印函数一样，遍历链表即可，打印是遍历到链表结尾，打印数据域，查找函数是遍历到与传入的参数x的值相同的数据域的结点，并返回结点地址。
9.在任意结点前插入函数的编写
// 在任意位置插入也可能改变头指针 void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x) { //pphead不可能为空，若为空则说明传参错误 assert(pphead); // 存在结点才能在指定结点前面插入 assert(*pphead); // 被查找的结点必须存在，不存在不能插入 assert(pos); // 创建新结点 SLNode* newNode = CreateNode(x); // 创建一个指向首元结点的指针 SLNode* begin = *pphead; // 首元结点就与指定结点相同，属于头插操作 if (begin == pos) { // 新结点的指针域指向原首元结点 newNode->next = *pphead; // 头指针指向新结点 *pphead = newNode; } // 指定结点不是首元结点 else { // 遍历到倒数第二个结点 while (begin->next != NULL) { // 如果遍历到的结点的下一个结点是指定的结点 if (begin->next == pos) { // 使新结点指向指定结点 newNode->next = begin->next; // 使遍历到的结点指向新结点 begin->next = newNode; // 退出函数 return; } // 遍历到的结点的下一个结点不是指定结点 else { // 指针指向下一个结点 begin = begin->next; } } // 执行到这说明没有找到指定结点pos，释放掉刚刚开辟的新结点的空间 free(newNode); // 弹出反馈 perror("not find"); // 终止程序 exit(-1); } }
在任意结点前插入函数也分为两种情况，在第一个结点前插入，即头插，和不在第一个结点前插入。后者由于是在指定结点前插入，需要改变指定结点的上一个结点的指针域，所以用来遍历的指针需要指向指定节点的上一个结点，通过上一个结点的指针域再找到指定结点，否者无法改变指定结点的上一个结点的指针域。倘若在查找后又对链表进行了其他操作而导致插入或者删除函数没能找到指定结点，我们需要对此反馈错误所在。
10.删除任意位置结点函数的编写
// 在任意位置删除也可能改变头指针 void SLTEarse(SLNode** pphead, SLNode* pos) { //pphead不可能为空，若为空则说明传参错误 assert(pphead); // 链表为空不能删除 assert(*pphead); // 指定结点必须存在 assert(pos); // 创建一个指向首元结点的指针 SLNode* begin = *pphead; // 首元结点就是指定节点pos if (begin == pos) { // 头删操作，零头指针指向首元结点的指针域所指向的空间 *pphead = begin->next; // 释放原首元结点的空间 free(begin); // 指针置空 begin = NULL; } // 首元结点不是指定结点pos else { // 遍历到倒数第二个结点 while (begin->next != NULL) { // 如果遍历到的结点的下一个结点是指定结点pos if (begin->next == pos) { // 创建临时指针变量指向指定结点 SLNode* tmp = begin->next; // 令遍历到的结点的指针域指向指定结点的下一个结点 begin->next = begin->next->next; // 释放指定结点的空间 free(tmp); // 指针置空 tmp = NULL; } // 遍历到的结点的下一个结点不是指定结点pos else { // 指针找到下一个结点 begin = begin->next; } } // 当没有找到时，反馈错误信息 perror("not find"); // 终止程序 exit(-1); } }
同样的，删除任意位置的结点函数也分为两种情况，删除首元结点就是头删操作，不是删除首元结点的操作比较复杂，要删除指定结点，肯定要修改指定结点的上一个结点的指针域，所以必须要保存着上一个结点的信息，遍历到的结点到指定结点的上一个结点就应该停止了。
指定结点里存放着指定结点的下一个结点的地址，先销毁指定结点的空间就无法找到下一个结点，先让遍历到的结点指向指定结点的下一个结点就无法通过遍历到的结点找到指定结点，这貌似是个死胡同，所以我们得创建一个临时变量，存放指定结点的空间，最后销毁即可。
11.销毁函数的编写
// 销毁函数是会改变头指针的，最后头指针一定为NULL void SLTDestroy(SLNode** pphead) { // pphead不可能为空 assert(pphead); // 创建一个指向首元结点的指针 SLNode* begin = *pphead; // 循环到链表没有结点为止 while (begin != NULL) { // 循环头删，令头指针指向第二个结点 *pphead = begin->next; // 释放原首元结点的空间 free(begin); // 指针指向新的首元结点 begin = *pphead; } }
销毁链表函数本质上就是不断地执行头删操作，每次删除就让指针指向新的首元结点，直到链表为空就不再头删。
五、代码整合及结果演示
1.代码整合
若在整合后出现某些函数不安全的错误，请在头文件里面加上下面这行代码。
#define _CRT_SECURE_NO_WARNINGS 1
1.头文件 SList.h 部分
#include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLNDataType; typedef struct SListNode { SLNDataType val; struct SListNode* next; }SLNode; //打印 void SLTPrint(SLNode* phead); //创建新节点 SLNode* CreateNode(SLNDataType x); //尾插 void SLTPushBack(SLNode** pphead, SLNDataType x); //头插 void SLTPushFront(SLNode** pphead, SLNDataType x); //尾删 void SLTPopBack(SLNode** pphead); //头删 void SLTPopFront(SLNode** pphead); //查找 SLNode* SLTFind(SLNode* phead, SLNDataType x); //在指定位置前插入 void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x); //在指定位置删除 void SLTEarse(SLNode** pphead, SLNode* pos); //销毁链表 void SLTDestroy(SLNode** pphead);
2.源文件 SList.c 部分
#include"SList.h" void SLTPrint(SLNode* phead) { SLNode* cur = phead; while (cur != NULL) { printf("%d->", cur->val); cur = cur->next; } printf("NULL\n"); } SLNode* CreateNode(SLNDataType x) { SLNode* newNode = (SLNode*)malloc(sizeof(SLNode)); if (newNode == NULL) { printf("malloc fail"); exit(-1); } newNode->val = x; newNode->next = NULL; return newNode; } void SLTPushBack(SLNode** pphead, SLNDataType x) { assert(pphead); SLNode* newNode = CreateNode(x); if (*pphead == NULL) { *pphead = newNode; } else { SLNode* begin = *pphead; while (begin->next != NULL) { begin = begin->next; } begin->next = newNode; } } void SLTPushFront(SLNode** pphead, SLNDataType x) { assert(pphead); SLNode* newNode = CreateNode(x); newNode->next = *pphead; *pphead = newNode; } void SLTPopBack(SLNode** pphead) { assert(pphead); assert(*pphead); SLNode* begin = *pphead; if (begin->next == NULL) { free(begin); begin = NULL; *pphead = NULL; } else { while (begin->next->next != NULL) { begin = begin->next; } free(begin->next); begin->next = NULL; } } void SLTPopFront(SLNode** pphead) { assert(pphead); assert(*pphead); SLNode* begin = *pphead; *pphead = begin->next; free(begin); begin = NULL; } SLNode* SLTFind(SLNode* phead, SLNDataType x) { //空链表允许被查找 SLNode* begin = phead; while (begin != NULL) { if (begin->val == x) { return begin; } begin = begin->next; } return NULL; } void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x) { //pphead不可能为空，若为空则说明传参错误 assert(pphead); assert(*pphead); assert(pos); SLNode* newNode = CreateNode(x); SLNode* begin = *pphead; if (begin == pos) { newNode->next = *pphead; *pphead = newNode; } else { while (begin->next != NULL) { if (begin->next == pos) { newNode->next = begin->next; begin->next = newNode; return; } else { begin = begin->next; } } free(newNode); perror("not find"); exit(-1); } } void SLTEarse(SLNode** pphead, SLNode* pos) { //pphead不可能为空，若为空则说明传参错误 assert(pphead); assert(*pphead); assert(pos); SLNode* begin = *pphead; if (begin->val == pos->val) { *pphead = begin->next; free(begin); begin = NULL; } else { while (begin->next != NULL) { if (begin->next == pos) { SLNode* tmp = begin->next; begin->next = begin->next->next; free(tmp); tmp = NULL; } else { begin = begin->next; } } perror("not find"); exit(-1); } } void SLTDestroy(SLNode** pphead) { assert(pphead); SLNode* begin = *pphead; while (begin != NULL) { *pphead = begin->next; free(begin); begin = *pphead; } }
3.源文件 test.c 部分
#include"SList.h" void test() { SLNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPrint(plist); SLTPopFront(&plist); SLTPopFront(&plist); SLTPrint(plist); SLNode* pos = SLTFind(plist, 3); SLTInsert(&plist, pos, 6); SLTPrint(plist); SLTDestroy(&plist); } int main() { test(); return 0; }
2.结果演示
我没有编写菜单函数，想要菜单的人可以自己编写一下。
总结
作为最最基础的链式结构，难度对于初学者还是蛮大的，不过单链表对思维的锻炼是非常强的，如果自己能够对单链表的操作了如指掌，那么学习进阶一点的链式结构上手也会非常快。学好单链表还是比较重要的。
本篇文章篇幅较长，难免会有错误，如果发现了错误，欢迎大家指正。如果觉得这篇文章对你有所帮助，别忘了三连博主哦，你们的鼓励是我最大的动力，谢谢。
