目录
一、前言 :
大家好，今天为大家带来的是数据结构与算法中单链表的内容分享，博文内容包括但不限于线性结构介绍，链表介绍，链表相关算法的讲解及演示。（以单链表为例）本篇博文属于《数据结构与算法入门》专栏，主要是为了将来的《数据结构与算法进阶》以及算法题做铺垫。
注意 :①代码中的注释也很重要；②不要眼高手低，自己动手跟着过一遍才能真正有收获；③可以点击文章侧边栏或者文章前面的目录进行跳转。良工不示人以朴，所有文章都会适时补充完善。感谢阅读！
二、线性结构
1.介绍
线性结构，即用一根直线把所有的结点穿起来，使得多个数据呈现有序的排列。
2.分类
常见的线性结构有链表，数组，栈，队列等。
3.数组和链表的区别 :
①从线性结构的角度来看，二者的区别在于——数组是连续存储的线性结构；而链表是离散存储的线性结构。
②数组的优缺点 :
优点 : 存取速度快；改查效率高。
缺点 : 需要一个连续的较大的内存空间；进行元素的增删操作时效率很低。
③链表的优缺点 :
优点 : 插入和删除元素时效率高；不需要一个连续的较大的内存。
缺点 : 查找某个位置的元素时效率低。
三、链表 [离散存储]
1.定义
①多个结点呈离散分配的状态。（不连续）
②每个结点之间通过指针彼此相连。
③每个结点都只有唯一前驱结点，和唯一后继结点。特殊的是，首节点没有前驱结点，尾节点没有后继结点。
④每个结点都分为两部分，一部分是数据域，用于保存数据；另一部分是指针域，用于指向下一个结点。（单链表）
2.相关概念
①首结点 : 存放链表第一个有效数据的结点。
②尾结点 : 存放链表最后一个有效数据的结点。
③头结点 : 首结点前面的结点，是真正意义上的链表的第一个结点，数据类型与首结点一致，但并不存放有效数据。头结点本身无实际意义，添加头结点的原因是为了更好地对链表相关的算法进行操作。（即方便链表的操作）
④头指针 : 存放头结点地址的指针变量。（即指向头结点的指针）
⑤尾指针 : 存放尾结点地址的指针变量。（即指向尾结点的指针）
Δ示意图如下 :
3.如何确定一个链表？
要确定一个链表实际只需要一个参数——头指针。由于头指针保存的头结点的地址，所以通过头指针，我们可以找到头结点；接着，又通过头结点找到首结点；以此类推，直到尾结点，当发现某个结点的指针域为空时，它就是尾结点了。
因此，如果想通过一个函数对链表进行操作，该函数至少需要获取链表的一个参数，那就是头结点。因为我们可以通过头指针递推出链表的其他所有参数。
4.如何表示链表中的一个结点？
可通过定义Node结构体类型来表示结点，（Node就是结点的意思）。如下所示 :
structNode { intdata; //数据域 —— 用于保存数据structNode*pNext; //指针域 —— 用于保存下一个结点的地址（指向下一个结点） };
也可通过typedef关键字进行优化，如下所示 :
typedefstructNode { intdata; structNode*pNext; } NODE, *PNODE; //NODE 和 * PNODE无顺序要求
5.链表的分类
①单链表 : 以上内容均以单链表为例。
②双链表 : 每个结点分为了三部分，除了一个数据域外，还有两个指针域。其中，一个指针域指向前一个结点，另一个指针域指向后一个结点。
③循环链表 : 字面意思，链表通过结点的指针域实现了串联，可以通过任意一个结点找到其他所有的结点。
④非循环链表 : 字面意思，与循环链表相对。
四、链表的相关算法
1.链表的创建和遍历
①准备工作 :
以非循环单链表为例，我们要想创建和遍历链表，首先必须确定链表结点的数据类型；可以定义Node结构体类型配合typedef关键字来确定链表结点的数据类型，如下所示 :
typedefstructNode//定义结点数据类型 { intdata; structNode*pNext; } NODE, *PNODE;
注意，此时NODE 等价于 struct Node类型；PNODE 等价于 struct Node *类型。
此外，我们还需要导入<stdio.h>, <malloc.h>, <stdlib.h>这三个头文件，它们分配包含了"输入输出"，"分配内存"，"退出程序"的函数。 如下所示 :
//包含scanf, printf函数//包含malloc函数//包含exit函数
对于链表的创建和遍历，我们分别使用create_list() 和 traverse_list() 函数来实现。
②创建链表 :
1°定义create_list() 函数进行链表的创建工作，并令其最终返回头结点的地址（返回给头指针）。
2°create_list() 函数中局部变量的定义情况如下 :
intlength; //存放链表中有效长度的个数inti; //循环变量intvalue; //临时存放当前结点的值。
3°除以上三个局部变量外，还需通过malloc函数为头结点分配内存空间，并令头指针和尾指针同时指向头结点。
4°令用户输入length的值，根据length的值定义for循环赋值的次数。在for循环中，先令用户输入value的值；然后通过malloc函数为新结点分配内存空间，并将value的值赋值给新结点的数据域；接着，令上一个结点的指针域指向新结点；令新结点的指针域为NULL；最后令尾指针指向新结点。
③遍历链表 :
1°定义traverse_list() 函数进行链表的遍历操作，需要将链表的头指针传入traverse_list() 函数。
2°首结点是链表中存放第一个有效数据的结点，因此要用从首结点开始遍历。我们可以在traverse_list() 函数中定义一个新的PNODE类型的指针变量p，并为其赋值为pHead->pNext，即令其指向首结点。
3°定义while循环，判断首结点是否为空，为空则不进入while循环，不遍历链表。如果不为空，先打印出当前结点数据域中的值，然后令指针p后移一位，使p指向下一个结点。直到p指针保存的值为尾结点的指针域时，退出while循环，遍历结束。
2. 获取链表的有效长度
1°在前面代码的基础上，定义size_ofList方法来获取链表的有效长度（即链表中有效元素的个数）。
2°在size_ofList方法内部定义局部变量cnt，用于存放链表中有效元素的个数，并使size_ofList方法最终能够返回cnt变量（int类型)。
3°该方法需要传入一个PNODE类型的实参pHead，因为pHead指向的是链表的头结点，不存放有效数据，因此我们还需要在方法内部定义一个临时的PNODE类型变量，假设为p，并令p = pHead->pNext，即令p指向首结点。
4°利用while循环对链表进行遍历，判断条件为p不等于NULL；然后在while语句内令p = p->pNext，同时让cnt自增1。即，相当于先判断首结点是否为空，如果首结点不为空，再依次循环判断后面的每一个结点是否为空，当p指向尾结点的指针域时，循环结束。
3.判断链表是否为空
1°在前面代码的基础上，定义is_empty方法来判断链表是否为空。同样，需要传入要判断链表的头指针pHead。
2°利用if 条件语句进行判断，如果pHead指向的结点的指针域为空，即如果首结点为空，返回true，否则返回false。
3°C语言中，如果想返回true或者false，需要导入# include <stdbool.h>头文件。
4.链表的排序
1°在前面代码的基础上，定义sort_list方法来对链表进行排序。同样，需要传入要排序链表的头指针pHead。
2°从狭义上讲，链表的排序和数组的排序算法是不同的，因为二者存储数的方式不一样，数组是连续的，有下标；而链表是不连续的，没有下标。但是，从广义上讲，链表排序的算法与数组是一致的，因为二者同属于线性结构。因此，链表的排序与数组的排序在原理上是一致的。
3°我们以冒泡算法的排序为例，以往数组的冒泡排序——其大体框架如下 :
//以下代码仅作演示用，无实际意义。inti,j,t; for (i=0; i<length-1; ++i) { for (j=i+1; j<length; ++j) { if (array[i] >array[j]) { t=array[i]; array[i] =array[j]; array[j] =t; } } }
类似于数组的排序，链表的排序要在上面做一些改动。首先最明显地，链表没有索引，所以有索引的地方必须进行替换。我们可以分别定义PNODE类型的变量p和q，并在外层for循环中，将p初始化为p = pHead->pNext；在内层for循环中将q初始化为q = p->pNext，即令p一开始指向首结点，而令q一开始指向首结点后面的结点。
4°因为我们最终要比较的是结点内data的值，所以内层for 循环的if 语句中，进行判断和交换的数据就是p->data和q->data；仍然需要定义临时变量t，用于辅助数据的交换。
5°解决掉索引的问题后，还有一个问题——循环次数的问题 :
可以选择保留i 变量和j 变量分别用于控制外层for循环和内层for循环的次数。即类似于数组的排序，内层每排序一次，j自增1；外层每排序一次，i自增1。当i 变量的值达到链表的长度 - 1时，跳出for循环。大体框架如下 : （注意——初始条件语句和循环控制语句都为2条语句）
//以下代码仅作为演示，无实际意义inti,j,t; for (i=0,p=pHead->pNext; i<len-1; ++i, p=p->pNext) { for (j=i+1,q=p->pNext; j<len; ++j,q=q->pNext) { if (p->data>q->data) { t=p->data; p->data=q->data; q->data=t; } } }
5.链表元素的插入和删除
①插入元素 :
1°在前面代码的基础上，定义insert_list方法进行链表元素的插入，最终希望达到的效果是——可以将一个新的结点插入到指定位置结点的前面（原先该位置处的结点挂载到新结点的后面）。insert_list方法需要传入三个实参——链表的头指针pHead；插入的新结点的位置pos（即position）；插入的新结点的值val。其中，插入新结点的位置必须从1开始（1表示首结点），即最多只能将新的结点插入到首结点的前面。
2°显然，我们要对传入的实参进行真实性和有效性的判断。可利用以下代码进行校验 :
//以下代码仅作为演示，无实际意义inti=0; while (NULL!=p&&i<pos-1) { p=p->pNext; ++i; } if (NULL==p||i>pos-1) { returnfalse; }
解读 :
1>while语句内部，i变量的自增和p指针的后移是同步发生的，而p指针一开始指向的是头结点，第一次进入while循环后，p指向了首结点，而i的值由0自增为1。因此，以此类推，最终i的值是几，p就指向了链表中的第几个结点。（注意，这里的第一个结点从首结点开始，因为首结点是存放链表中第一个有效数据的结点。)
2>当i变量的值= pos - 1时，即p指向了要插入位置的前一个结点。配合if 条件语句，即可过滤掉插入位置为空的错误情况，比如说，假设目前链表中共4个结点（不包含首结点），那我们最最往后，也只能在第5个位置前加入新结点（即插入到了链表的最后）；如果链表中4个结点，你却想在第10个位置插入新结点，显然是不可能的。
3>对于if 条件语句的第二个判断，是为了过滤掉实参pos为0或者负数的情况。pos必须从1开始，即最最往前，也只能插入到首结点的前面。如果pos = 0，那就相当于插入到了头结点的前面，而头结点是链表真正意义上的第一个结点，并且不存放有效数据，这么一来不是乱套了吗？
3°继续，对于为pNew新结点动态分配的新的内存空间，我们要进行判断，如果为空，则退出程序（通过exit语句）。
4°最后就是执行插入的步骤了，我们要先在方法体内定义一个PNODE类型的q变量，然后配合q变量来完成插入操作——先将val值赋值给新结点的val属性；再令q初始化为p的指针域；接着，p结点的pNext属性指向新结点；新结点pNew的pNext属性指向q。
②删除元素 :
1°删除元素的过程同插入元素在原理上类似。同样地，在前面代码的基础上，定义delete_list方法进行链表元素的插入。delete_list方法需要传入三个实参——链表的头指针pHead；要删除的结点在链表中的位置pos（即position）；要删除元素的值的地址值&pVal。
2°对pos实参的校验同上。不一样的是，我们这次要将while 循环的判断语句中的"NULL != p"改为"NULL != p->pNext"，同时将if 条件语句中的"NULL == p"改为"NULL == p->pNext"。（注意，这么改仅仅是更改了要判断的结点，p本身的指针仍然是pos位置的前一个结点，不变）。这么做的目的是因为——原先我们插入元素时，只需要指定插入位置处的前一个结点是否为空；而删除元素时，我们不但需要知道要删除元素的前一个结点是否为空，还需要知道要删除的结点是否为空。
while循环判断条件的更改，可以使我们直接从头结点开始判断，最后一次进入while循环判断的就是pos位置的前一个结点是否为空，即，p最后还是指向的pos位置的前一个结点，但是判断语句相比插入元素时提前了一个结点。if语句判断条件的更改，可以判断要删除的结点是否为空。
3°相比插入元素来看，我们不再需要使用malloc函数来动态分配空间，而是直接执行删除操作即可。先令q指向要删除的结点（即p结点的后一个结点）；然后将要删除的结点的值赋给*pVal；接着，令p指向p结点的后两个元素，即q的下一个元素；最后，利用free函数释放q结点的空间，并令其为NULL。
6.代码演示
代码如下 :
typedefstructNode//定义结点数据类型{ intdata; structNode*pNext; } NODE, *PNODE; //函数声明PNODEcreate_list(void); //链表的创建voidtraverse_list(PNODEpHead); //链表的遍历boolis_empty(PNODEpHead); //判断链表是否为空intsize_ofList(PNODEpHead); //获取链表当前的长度voidsort_list(PNODEpHead); //对链表进行排序boolinsert_list(PNODEpHead, intpos, intval); //在链表指定位置插入指定值的结点booldelete_list(PNODEpHead, intpos, int*pVal); //删除链表指定位置处的结点intmain(void) { PNODEpHead=NULL; //初始化头指针intval_0,val_1; intpos_0,pos_1; pHead=create_list(); //创建链表，并将链表第一个结点的地址返回给头指针。traverse_list(pHead); //遍历链表printf("-------------------------------------------------------------\n"); if (is_empty(pHead)) //判断链表是否为空printf("\n链表为空!\n"); elseprintf("\n链表不为空！\n"); printf("链表中元素的个数 = %d\n", size_ofList(pHead)); //获取链表的长度printf("-------------------------------------------------------------\n"); sort_list(pHead); //对链表进行排序printf("正向排序后的链表: \n"); traverse_list(pHead); printf("-------------------------------------------------------------\n"); printf("请输入你要插入的新结点的值："); scanf("%d", &val_0); printf("你想将新结点插入链表中的哪个位置："); scanf("%d", &pos_0); insert_list(pHead, pos_0, val_0); //在链表中的指定位置处插入指定值的新结点printf("插入元素后的链表：\n"); traverse_list(pHead); printf("-------------------------------------------------------------\n"); printf("请输入你要删除的结点的位置："); scanf("%d", &pos_1); delete_list(pHead, pos_1, &val_1); printf("删除元素后的链表：\n"); traverse_list(pHead); return0; } PNODEcreate_list(void) { intlength; //存放链表中有效长度的个数inti; //循环变量intvalue; //临时存放当前结点的值。/*为头结点分配内存空间，并将其地址值返回给头指针，如下。*/PNODEpHead= (PNODE) malloc(sizeof(NODE)); if (NULL==pHead) { printf("动态分配失败！程序即将终止！"); exit(-1); //0表示正常退出，非0表示非正常退出。 } /*定义尾指针，初始化并使其指向头结点。即此时头指针和尾指针都指向了头结点。如下 : */PNODEpTail=pHead; pTail->pNext=NULL; //使头结点的指针域为空，该步骤也可放在头指针的定义之后。printf("请确定你要创建的链表结点的个数：length = "); scanf("%d", &length); for (i=0; i<length; ++i) { printf("请输入第%d个结点的值：", i+1); scanf("%d", &value); PNODEpNew= (PNODE) malloc(sizeof(NODE)); if (NULL==pNew) { printf("动态分配失败！程序即将终止！"); exit(-1); } pNew->data=value; //将输入的值存入新结点的数据域中。pTail->pNext=pNew; //令前一个结点指向新结点。pNew->pNext=NULL; //令新结点的指针域为空。pTail=pNew; //令尾指针后移，尾指针始终指向当前的尾结点。 } returnpHead; } voidtraverse_list(PNODEpHead) { PNODEp=pHead->pNext; //从首结点开始遍历。printf("\n=========遍历链表：==========\n"); while(NULL!=p) { printf("%d", p->data); p=p->pNext; printf("\t"); } printf("\n=============================\n"); return; } boolis_empty(PNODEpHead) { if (NULL==pHead->pNext) returntrue; elsereturnfalse; } intsize_ofList(PNODEpHead) { PNODEp=pHead->pNext; intcnt=0; //初始化cnt变量。while (NULL!=p) { ++cnt; p=p->pNext; } returncnt; } voidsort_list(PNODEpHead) { intlen=size_ofList(pHead); inti,j,t; PNODEp,q; for (i=0,p=pHead->pNext; i<len-1; ++i, p=p->pNext) { for (j=i+1,q=p->pNext; j<len; ++j,q=q->pNext) { if (p->data>q->data) { t=p->data; p->data=q->data; q->data=t; } } } return; } boolinsert_list(PNODEpHead, intpos, intval) //pos = position{ inti=0; PNODEq,p=pHead; while (NULL!=p&&i<pos-1) //判断要插入位置的前一个结点是否为空 { p=p->pNext; //此处i的自增和p指针的后移同时进行++i; //即i是几，p就指向链表中第几个结点（从首结点开始算第一个) } if (NULL==p||i>pos-1) //后一个条件用于防止pos为负数和0的情况returnfalse; PNODEpNew= (PNODE) malloc(sizeof(NODE)); //为新的结点分配内存空间if (NULL==pNew) { printf("为新结点动态分配内存失败！\n"); exit(-1); } pNew->data=val; q=p->pNext; p->pNext=pNew; pNew->pNext=q; returntrue; } booldelete_list(PNODEpHead, intpos, int*pVal) { inti=0; PNODEq,p=pHead; while (NULL!=p->pNext&&i<pos-1) //判断要删除的结点的前一个结点是否为空 { p=p->pNext; ++i; } if (NULL==p->pNext||i>pos-1) //判断要删除的结点是否为空returnfalse; q=p->pNext; *pVal=q->data; p->pNext=q->pNext; free(q); q=NULL; returntrue; }
运行效果 : (如下GIF图)
五、完结撒❀
🆗，以上就是关于单链表的全部内容了。链表是数据结构与算法中相当有分量的一部分内容。只有掌握了链表才能更好地学习之后的栈和队列，等等。up之后可能也会出一些算法题的讲解，不过目前在写java的博文，有时间后或许会考虑。今天就先到这里，感谢阅读！
