0. 前言
同学们大家好！我们之前学会了如何实现顺序表
大家有遗忘的可以再复习上节课的知识，并且多加练习 ！
【数据结构】顺序表实现-CSDN博客
其实，不知道同学们觉不觉得，我们在实现顺序表时，可能会有如下的问题
1. 中间/头部的插入删除，时间复杂度为0(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
那么，是否存在一种数据结构，能够解决以上顺序表表现出来的问题：
1)中间/头部的插入删除，可以一步到位，不需要挪动数据
2)不需要扩容
3)不会造成空间
答案是有的！就是我们本期博客要学习新的数据结构—链表！
1. 链表的概念
概念：链表是⼀种线性数据结构，由⼀系列节点组成，每个节点包含数据和指向下⼀个节点的指针。链表中的元素在内存中不必顺序排列，⽽是通过指针相互连接。
我们可以这样联想：
链表的结构其实跟火车车厢是类似的，火车车厢都拉载着一定量的乘客，但是我们会发现火车的车厢有长有短，这是因为如果在淡季时，⻋次的⻋厢会相应减少，如果在旺季时，⻋次的⻋厢会额外增加⼏节。只需要将火车里的某节⻋厢去掉/加上，不会影响其他⻋厢，每节⻋厢都是独⽴存在的。车厢是独⽴存在的，且每节⻋厢都有车门。
同学们可以想象⼀个这样的场景，
假设每节⻋厢的⻋⻔都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带⼀把钥匙的情况下，如何从车头走到车尾呢？
我们想到的做法，那就是 每节车厢里都放⼀把下⼀节车厢的钥匙。
火车的每节车厢就相当于链表的⼀个节点（结点）。在链表中，每个节点（⻋厢）是什么样的呢？
图中指针变量 plist 保存的是第⼀个节点的地址，我们称 plist 此时“指向”第⼀个节点，
这里的“指向”是我们想象的，其实物理上是存放了第一个节点的地址。
如果我们希望plist“指向”第⼆个节点时，只需要修改plist保存的内容为 0x0012FFA0
有同学会问：为什么还需要指针变量来保存下⼀个节点的位置呢？
链表中每个节点都是独立申请的（即需要插⼊数据时才去申请⼀块节点的空间），
我们就需要通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。
这是可能有同学发问了，如果让我们描述出这样一个链表的这个节点，那我们该怎样描述呢？
2. 链表的分类
链表可以分为单向链表、双向链表和循环链表。
2.1 单向/双向链表
2.2 带头/不带头
这里的 "头"，指的是一个头节点。该节点的next指向链表实际的表头，val中不存放有效数据
实际使用时，带头的head->next相当于不带头的plist指针
2.3 循环或者非循环
链表的结构⾮常多样，以下情况组合起来就有8种（2x2x2）链表结构：
3. 单向链表的实现
下面我们以单向链表为例，详细讲解链表的实现方法。
3.1 节点定义
链表的基本结构由节点组成，每个节点包含数据和指向下⼀个节点的指针。
我们就可以定义这样的一个结构
typedef struct SListNode
{int data;//存储的数据struct SListNode* next;//后继节点
}SLTNode;typedef 关键字在这里用于为结构体 struct Node 定义一个新的类型名 Node ，
这使得在后续的代码中，可以直接使用 Node 来声明该结构体类型的变量，
而无需再使用 struct Node 这种较为繁琐的形式。
3.2 所需文件：
还是像往常一样，我们将其拆分为不同的文件进行设计。
SList.c ：用于存放函数实现
SList.h ：用于声明函数和必要的头文件、结构体定义
test.c ：测试代码
3.3 链表相关的接口声明
//链表打印
void SLTPrint(SLTNode* phead);//头部插⼊删除/尾部插⼊删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x);//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos之后的节点
void SLTEraseAfter(SLTNode * pos);//销毁链表
void SListDesTroy(SLTNode** pphead);3.4 创建结点
想要实现链表，对链表进行数据的增加，结点的创建是必不可少的，
因此我们写一个一个函数来创建结点。将数据传入函数，并返回新开辟空间的地址。
SLTNode* SLTCreateNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!\n");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}对newnode进行判断，若开辟失败其值为空指针，则打印错误信息，程序退出。
若开辟成功，则将数据复制给data，并将其next初始化为NULL。
3.5 尾插
首先，我们先来实现一个尾插的接口，尾插就是在链表的尾部插入一个节点。
具体过程我们画个图来分析一下：
下图这是一个链表，现在想在这个链表尾插一个4节点，怎么做呢？
和顺序表不同的是因为不能根据下标访问元素(即不能随机访问)，当然我们也不知到最后一个结点的位置，所在尾插时，需要遍历找到最后一个结点的位置。 也就是链表的尾节点
我们可以定义一个ptail 变量用来遍历链表找链表的尾，
很显然不断找尾节点，这是一个循环，什么时候循环结束呢？
因为每一个节点包含数据和指向下⼀个节点的指针。
所以我们发现当该节点指向下⼀个节点的地址为NULL时，说明ptail此时指向就是尾节点。
也就是图中的3节点。
找到尾结点之后，在它之后插入一个新的节点名叫newnode，newnode存的数据是4，它 “指向” 的是NULL，而3结点指向的就不是NULL了，“指向”的是newnode，存的是newnode节点的地址。
经过考虑，这还是链表有节点的情况，那如果链表中没有节点呢？
那如果这是一个空链表的话，这个头指针phead的地址就是NULL
如果尾插的话，就直接创建新的节点newnode，然后phead"指向"newnode就可以了。
代码如下：
void SLTPushBack(SLTNode** pphead, SLDataType x)
{assert(pphead); // 传递过来的 一级指针的地址 二级指针 不能为 NULL// 先创建 一个 新节点SLTNode* newNode = STLCreatNode(x);// 1、链表为空if (*pphead == NULL){*pphead = newNode;return;}// 2、链表非空SLTNode* ptail = *pphead; // 因为要找 尾节点：干脆命名为 tail//本质是：找到尾节点的地址，而不是 尾节点的 nextwhile (ptail->next) {ptail = ptail->next;}ptail->next = newNode;
}细心的同学会发现，我们在实现尾插功能时，
形参我们传的是 SLTNode** pphead 是一个二级指针啊，为什么不传一级指针呢？
这是在实现链表时，很多同学容易犯错的点！！
我们发现如果链表为空，在尾插时，需要修改头指针phead，phead的地址发生了修改
因此形参必须为二级指针。
有的同学可能还会很疑惑，这里我们看看如果传的是一级指针，发生什么结果？
void SLTPushBack(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* newnode = SLTBuyNode(x);//链表为空，新节点作为pheadif (phead == NULL) {phead = newnode;return;}//链表不为空，找尾节点SLTNode* ptail = phead;while (ptail->next){ptail = ptail->next;}//ptail就是尾节点ptail->next = newnode;
}
我们测试发现：
如果尾插函数第一个参数是SListNode* phead，当尾插的链表是空链表的时候，这时如果只是单纯的将phead = newnode；这样操作之后，实际上的头结点并没有被改变，因为函数的形参只是实参的一份临时拷贝，尾插函数只是将形参的phead的值改成了newnode并没有将真正的头指针改变，同时函数结束时这个phead局部变量会被销毁。所以这里要用到二级指针来接收头指针的地址，之前C语言的学习中函数章节中提到，函数的传值和传址的区别，想要改变值就要传地址（指针），同样的道理这里要想改变地址，就得传地址的地址，所以形参用到了二级指针。也就是下面正确的代码。
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);//链表为空，新节点作为pheadif (*pphead == NULL) {*pphead = newnode;return;}//链表不为空，找尾节点SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptail就是尾节点ptail->next = newnode;
}
对于指针传参，我们可以通过下图来理解。
3.6 头插
我们画个图来分析一下：
代码如下：
这里涉及改变链表的头指针，所以传的是二级指针。
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);//newnode *ppheadnewnode->next = *pphead;*pphead = newnode;
}
注意：
这里要注意链接的顺序，如果先将头指针指向新结点的头，再将新的结点的尾链接到原来链表的头的话，原来链表的头就找不到了，因为原来链表的头是放在头指针里面的，若先将头指针改了就找不到原来的头了，就链接不上了。
3.7 尾删：
尾删有如下情况：
1.链表为空链表： 当链表为空链表时，就不存在删除数据的情况，因为没有是数据可删，直接结束函数即可。
2.链表只有一个结点：当链表只有一个结点时，tail->next->next;会出现对空指针NULL引用，所以要单独拿出来处理。
3.链表有多个结点 ：就可以按照通常思路找尾，先将尾结点释放掉，再将指向尾结点的指针即倒数第二个结点的指针域置空(NULL)。
在链表的尾部删除结点通常的想法就是把要删除的结点free掉，然后将要删除的结点的前一个结点的指针域置成空，但是如果遍历链表找到尾结点的话，就不能再找到尾的前一个结点。
我们可以用prev指针保留删除的结点的前一个结点，ptail遍历找为节点，找到尾结点之后删除
ptail指向的节点，并把prev指针接收的地址置为NULL，也就是prev->next = NULL;
这就完成了尾删的操作。
代码如下：
这里涉及改变链表的头指针，所以传的是二级指针。
void SLTPopBack(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//链表不为空//链表只有一个节点，有多个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;//销毁尾结点free(ptail);ptail = NULL;
}3.8 头删
经过考虑， 这里要考虑两种情况，链表为空的时，和链表为非空的时。
1.当链表为空的时：
直接结束函数，因为没有可删除的结点。
2. 当链表不为空时：
将链表的头指针释放，再将头指针指向第二个结点。
代码如下：
这里涉及改变链表的头指针，所以传的是二级指针。
void SLTPopFront(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//让第二个节点的地址成为新的头//把旧的头结点释放掉//SLTNode* del = *pphead;//*pphead = (*pphead)->next;//->的优先级高于*//free(del);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}3.9 单链表的查找
查找很简单，我们可以定义一个cur指针从头到尾依次遍历整个链表，
只要找到符合条件的结点，就返回该结点的地址。否则返回NULL
代码如下：
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(pphead);//遍历链表SLTNode* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}
3.10 在指定位置pos之前插入数据
如果pos的位置在头结点，我们直接在头结点头插即可。
如果pos不在头结点，我们先创建一个新的结点，用prev指针找到pos的前一个结点的地址，pos的本质是一个地址，我们用将新节点存储的地址给pos，newnode的地址给到prev指针所指向结点的存储地址。这样我们就将新节点插入到了pos结点的前面
代码如下：
//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//链表能不能为空 //为空！！assert(*pphead);//pos刚好是头结点if (pos == *pphead){//头插SLTPushFront(pphead, x);return;}//pos不是头结点的情况SLTNode* newnode = SLTBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev -> newnode -> posprev->next = newnode;newnode->next = pos;
}3.11 在指定位置pos之后插入数据
在指定位置插入是最麻烦的，原因就在于我们不能立马获取到想要插入位置的信息，我们需要先进行判断，如果指定位置是在最前面，那就可以使用头插，如果是最后就使用尾插。在得知指定位置在链表中间某一位置后，我们就需要先找到这个位置前后的节点的信息，如下图，假如我们要插入的位置是第三个位置，那就需要知道第二个位置和第三个位置的信息，当我们找到了后可以分俩布进行操作（顺序不能更改）：
- 先让节点指向后面的节点
- 再让前面的节点指向插入节点
pos ，newnode， pos->next 正确的指向写法应该是：
newnode->next = pos->next;
pos->next = newnode;
代码如下：
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;pos->next = newnode;}3.12 删除pos结点
删除pos结点：用prev指针找到pos前一个结点的位置，用prev所在的结点的存储地址改为pos->next（pos后一个结点）。之后释放pos结点的空间，最后将pos指针置为NULL
// 从链表中删除指定位置的结点
// 定义函数SLTErase，参数为指向指针的指针pphead和要删除的结点位置pos void SLTErase(SLTNode** pphead, SLTNode* pos)
{ assert(pphead); // 断言pphead不为空 assert(pos); // 断言pos不为空 if (pphead == pos) // 如果要删除的位置是头结点 { SLTPopFront(pphead); // 调用SLTPopFront删除头结点 }else { // 找到pos的前一个位置 SLTNode prev = *pphead; // 定义指针prev指向头结点 while (prev->next != pos) // 当prev的下一个结点不等于pos时 { prev = prev->next; // prev指向下一个结点 }prev->next = pos->next; // 将prev的下一个结点指向pos的下一个结点free(pos); // 释放pos指向的内存}
}3.13 删除pos之后的节点
删除pos之后的结点：用del代表pos的下一个结点，将pos的下下个结点的地址给pos的存储地址，释放del，将del指针置为NULL；
代码如下：
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);// pos pos->next pos->next->nextSLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;}3.13 单链表打印
单链表的打印逻辑很简单,我们定义一个pcur指针，一开始指向头，
顺着头指针向后循环遍历打印整个链表结点的数据域即可,
当结点的指针域为空时,则代表已经遍历打印完链表的所有元素,这时跳出循环即可.
代码如下：
void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}
注意：这里不会改变phead， 所以传一级指针就可以。
我们malloc创建4个节点，并且把他们的数据打印出来
我们运行代码，1->2->3->4->就是一条链表了。
3.14 单链表的销毁
当我们使用完单链表想要退出程序时,就应该将之前动态开辟的内存释放掉,还给操作系统.
即销毁单链表操作.
我们使用free()函数将前面开辟的结点的内存逐一释放,释放完将头指针置为空即可.
代码如下：
//销毁链表
void SListDesTroy(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}4. 完整代码
(上面代码是便于讲解，如果有些许错误，以这里提供的源码为主)
SList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLTDataType;//链表是由节点组成 typedef struct SListNode
{int data;//存储的数据struct SListNode* next;//后继节点
}SLTNode;//typedef struct SListNode SLTNode;//链表打印
void SLTPrint(SLTNode* phead);//头部插⼊删除/尾部插⼊删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x);//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos之后的节点
void SLTEraseAfter(SLTNode * pos);//销毁链表
void SListDesTroy(SLTNode** pphead);SList.c
#define _CRT_SECURE_NO_WARNINGS 1#include "SList.h"void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!\n");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}//头部插⼊删除/尾部插⼊删除
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);//链表为空，新节点作为pheadif (*pphead == NULL) {*pphead = newnode;return;}//链表不为空，找尾节点SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptail就是尾节点ptail->next = newnode;
}void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);//newnode *ppheadnewnode->next = *pphead;*pphead = newnode;
}void SLTPopBack(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//链表不为空//链表只有一个节点，有多个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;//销毁尾结点free(ptail);ptail = NULL;
}void SLTPopFront(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//让第二个节点的地址成为新的头//把旧的头结点释放掉//SLTNode* del = *pphead;//*pphead = (*pphead)->next;//->的优先级高于*//free(del);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(pphead);//遍历链表SLTNode* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//链表能不能为空 //为空！！assert(*pphead);//pos刚好是头结点if (pos == *pphead){//头插SLTPushFront(pphead, x);return;}//pos不是头结点的情况SLTNode* newnode = SLTBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev -> newnode -> posprev->next = newnode;newnode->next = pos;
}//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;pos->next = newnode;}//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//pos刚好是头结点if (pos == *pphead){//头插SLTPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;}//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);// pos pos->next pos->next->nextSLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;}//销毁链表
void SListDesTroy(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "SList.h"void SlistTest02()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist); //1->2->3->4->NULLSLTPushFront(&plist, 5);SLTPrint(plist); //5->1->2->3->4->NULLSLTPushFront(&plist, 6);SLTPrint(plist); //6->5->1->2->3->4->NULLSLTPushFront(&plist, 7);SLTPrint(plist); //7-6->5->1->2->3->4->NULLSLTPopBack(&plist);//SLTPrint(plist);//1->2->3->NULL//SLTPopBack(&plist);//SLTPrint(plist);//1->2->3->NULL//SLTPopBack(&plist);//SLTPrint(plist);//1->2->3->NULL//SLTPopBack(&plist);//SLTPrint(plist);//1->2->3->NULL//SLTPopBack(&plist);//SLTPrint(plist);//1->2->3->NULL
}void SlistTest03()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist); //1->2->3->4->NULL//SLTPopFront(&plist);//SLTPrint(plist); //SLTPopFront(&plist);//SLTPrint(plist); SLTNode* FindRet = SLTFind(&plist, 5);if (FindRet){printf("找到了!\n");}else{printf("未找到!\n");}
}int main()
{//SlistTest01();//SlistTest02();SlistTest03();return 0;
}
🌟🌟温馨提醒：
同学们在练习时，可以写一个模块，测试一下模块，
这样避免出现多种错误，在调试时不方便查出问题
希望这篇单链表的实现详解能对大家有所帮助！喜欢的可以收藏+支持哦~ღ( ´･ᴗ･` )
若有疑问，欢迎朋友们评论区留言或私信与我交流。感谢同学们的支持！！！