在他一生中，从来没有人能够像你们这样，以他的视角看待这个世界。
---------《寻找天堂》
目录
文章目录
一、什么是链表？
二、为什么要使用链表？
三、 单链表介绍与使用
3.1 单链表
3.1.1 创建单链表节点
3.1.2 单链表的头插、尾插
单链表的尾插
单链表的头插
3.1.3 单链表的头删、尾删
单链表的尾删编辑
单链表的头删
3.1.4 链表节点的查找
3.1.5 在指定位置插入数据
在指定位置前插入数据
在指定位置之后插入数据
3.1.6 删除pos之后的节点
3.1.7 销毁链表
四、完整代码
SList.h
SList.c
一、什么是链表？
链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构。链表由一系列节点（链表中每一个元素称为节点）组成，节点在运行时动态生成 （malloc），每个节点包括两个部分：
- 一个是存储数据元素的数据域
- 另一个是存储下一个节点地址的指针域
二、为什么要使用链表？
使用链表用于解决动态数量的数据存储。比如说，我们要管理一堆票据，可能有一张，但也可能有一亿张。怎么办呢？申请一个几十G的大数组存储着吗？万一用户只有一百张票据要处理呢？内存较小拒绝运行？可申请少了又不够用啊……
而且，用数组的话，删除然后添加票据，是每次删除让后面五百万张往前移一格呢、还是每次添加从头搜索空闲格子？如何区分空闲格子和值为0的数据？要进行区分的话是多占用空间呢还是占用数据值域？占用了值域会不会使得数据处理变得格外复杂？会不会一不小心就和正常数据混淆？万一拿来区分的字段在某个版本后废弃不用、或者扩充值域了呢？
那么，链表这种东西就是个很有效的数据结构，可以很有效的管理这类不定量的数据。
三、 单链表介绍与使用
3.1 单链表
单链表的每个节点除了存放数据元素外，还要存储指向下一个节点的指针。与顺序表进行对比：
| 优点 | 缺点 | |
| 顺序表 | 可随机存储，存储密度较高 | 要求大片连续空间，改变容量不方便 |
| 单链表 | 不要求大片连续空间，改变容量方便 | 不可随机存取，要耗费一定空间存放指针 |
3.1.1 创建单链表节点
typedef int SLTDataType;
//链表是由节点构成
//逻辑结构：一定连续；物理结构：不一定连续
//不会造成空间的浪费，由独立的节点构成
typedef struct SListNode { //SList : single linked list 单链表
SLTDataType data; // 一个是存储数据元素的数据域
struct SListNode* next; // 另一个是存储下一个节点地址的指针域
}SLTNode;
上面的结构体仅是单链表节点的定义，要创建一新的节点需要对里面的数据进行初始化：插入数值，节点指向的下一个节点为空
//创建一个节点
struct SListNode* SLTBuyNode(SLTDataType x) {
SLTNode* newnode = (struct SListNode*)malloc(sizeof(struct SListNode));
newnode->data = x;
newnode->next = NULL;
return newnode;
}
3.1.2 单链表的头插、尾插
单链表的尾插
这里传递的链表节点的参数，为什么是二级指针呢？
在初始化过程中，需要修改头指针，因此要用到二级指针传递头指针的地址，这样才能修改头指针。这与普通变量类似，当需要修改普通变量的值，需传递其地址。使用二级指针，很方便就修改了传入的结点一级指针的值。 如果用一级指针，则只能通过指针修改指针所指内容，却无法修改指针的值，也就是指针所指的内存块。
//链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) { //一级指针传递的为结构体变量地址的值，二级指针接收的是指向结构体变量的指针的地址
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
//链表为空，新节点作为pphead
if (*pphead == NULL) {
*pphead = newnode;
return;
}
//链表不为空，链表的尾指向新节点
SLTNode* ptail = *pphead;
while (ptail->next) {
ptail = ptail->next;
}
ptail->next = newnode;
}单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
assert(pphead);
//链表为空，新节点指向pphead，pphead再指向新节点；链表不为空，新节点指向pphead，pphead再指向新节点
SLTNode* newnode = SLTBuyNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
插入完数据后，想要打印以一下链表的数据，通过从头开始一个一个节点地访问数据，并打印，便实现了链表数据的打印。然后看看插入的情况；
//打印链表
void SLTPrint(SLTNode* phead) {
SLTNode* pcur = phead;
while (pcur) {
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}尾插部分数据，观察打印的结果是否符合预期结果；发现运行结果与预期相符，所以链表的插入操作是没什么大问题的
3.1.3 单链表的头删、尾删
如果链表为空，不需要删除；如果删除的是第一个结点，则需要将保存链表首地址的指针保存第一个结点的下一个结点的 地址 如果删除的是中间结点，则找到中间结点的前一个结点，让前一个结点的指针域保存这个结 点的后一个结点的地址即可
单链表的尾删
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* pcur = *pphead;
*pphead = pcur->next;
pcur->next = NULL;
free(pcur);
pcur = NULL;
}3.1.4 链表节点的查找
先对比第一个结点的数据域是否是想要的数据，如果是就直接返回，如果不是则继续查找下 一个结点，如果到达最后一个结点的时候都没有匹配的数据，说明要查找数据不存在
//查找
SLTNode* STLFind(SLTNode** pphead, SLTDataType x) {
assert(pphead);
SLTNode* pcur = *pphead;
while (pcur) {
if (pcur->data == x) {
return pcur;
}
pcur = pcur->next;
}
return NULL;
}3.1.5 在指定位置插入数据
在指定位置前插入数据
//在指定位置前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
assert(pphead);
assert(pos);
//头节点不能为空
assert(*pphead);
SLTNode* newnode = SLTBuyNode(x);
//当pos节点指向 头节点时,进行头插
if (*pphead == pos) {
SLTPushFront(pphead, x);
return;
}
//pos pphead不指向同一节点
SLTNode* prev = *pphead;
while (prev->next != pos) { //找到pos节点的前驱
prev = prev->next;
}
newnode->next = pos;
prev->next = newnode;
}在指定位置之后插入数据
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}3.1.6 删除pos之后的节点
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {
assert(pos);
assert(pos->next);//pos后不为空
SLTNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
}3.1.7 销毁链表
重新定义一个指针next，保存pcur指向节点的地址，然后next后移保存下一个节点的地址，然后释放pcur对应的节点，以此类推，直到pcur为NULL为止
//销毁链表,由独立的节点构成，需要一个个销毁
void SListDestroy(SLTNode** pphead) {
assert(pphead);
assert(*pphead);
SLTNode* pcur = *pphead;
while (pcur) {
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}四、完整代码
SList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//顺序表存在的一定的问题：
//1.顺序表的中间/头部的插入需要挪动数据
//2.扩容存在性能的消耗
//3.会有空间的浪费
typedef int SLTDataType;
//链表是由节点构成
//逻辑结构：一定连续；物理结构：不一定连续
//不会造成空间的浪费，由独立的节点构成
typedef struct SListNode { //SList : single linked list 单链表
SLTDataType data;
struct SListNode* next;
}SLTNode;
//链表的头插、尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(struct SListNode** pphead, SLTDataType x);
//链表的头删、尾删
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
//打印链表
void SLTPrint(SLTNode* phead);
//查找
SLTNode* STLFind(SLTNode** phead, SLTDataType x);
//在指定位置前插入数据
void SLTInsert(SLTNode** phead, SLTNode* pos,SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** phead, SLTNode* pos);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDestroy(SLTNode** phead);SList.c
#include"SList.h"
//创建一个节点
struct SListNode* SLTBuyNode(SLTDataType x) {
SLTNode* newnode = (struct SListNode*)malloc(sizeof(struct SListNode));
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//打印链表
void SLTPrint(SLTNode* phead) {
SLTNode* pcur = phead;
while (pcur) {
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
//链表的头插、尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) { //一级指针传递的为结构体变量地址的值，二级指针接收的是指向结构体变量的指针的地址
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
//链表为空，新节点作为pphead
if (*pphead == NULL) {
*pphead = newnode;
return;
}
//链表不为空，链表的尾指向新节点
SLTNode* ptail = *pphead;
while (ptail->next) {
ptail = ptail->next;
}
ptail->next = newnode;
}
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
assert(pphead);
//链表为空，新节点指向pphead，pphead再指向新节点；链表不为空，新节点指向pphead，pphead再指向新节点
SLTNode* newnode = SLTBuyNode(x);
newnode->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* pcur = *pphead;
*pphead = pcur->next;
pcur->next = NULL;
free(pcur);
pcur = NULL;
}
//查找
SLTNode* STLFind(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);
SLTNode* newnode = SLTBuyNode(x);
//当pos节点指向 头节点时,进行头插
if (*pphead == pos) {
SLTPushFront(pphead, x);
return;
}
//pos pphead不指向同一节点
SLTNode* prev = *pphead;
while (prev->next != pos) { //找到pos节点的前驱
prev = prev->next;
}
newnode->next = pos;
prev->next = newnode;
}
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos) {
assert(pphead);
assert(pos);
//当pos节点指向 头节点时,进行头删
if (*pphead == pos) {
SLTPopFront(pphead);
return;
}
//pos pphead不指向同一节点
SLTNode* prev = *pphead;
while (prev->next != pos) { //找到pos节点的前驱
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {
assert(pos);
assert(pos->next);//pos后不为空
SLTNode* del = pos->next;
pos->next = pos->next->next;
//pos->next = del->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;
}
