​

​📝个人主页：@Sherry的成长之路
🏠学习社区：Sherry的成长之路（个人社区）
📖专栏链接：数据结构
🎯长路漫漫浩浩，万事皆有期待

1.链表

1.1 链表的概念及结构：

链表（linked list）是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

1.2 顺序表的缺陷

在之前的博客中，我们对顺序表有了较深层次的认知，同时我们发现，顺序表在创建和使用时，存在一些问题：

1. 当空间不足时，顺序表需要进行增容，但由于顺序表本质为数组，数据在物理上连续存放，因此在扩容时要付出较大的空间代价。为避免频繁扩容，基本每次都扩容 2 倍，当扩容次数增多时，就很有可能会造成一定程度的空间浪费。
2. 由于顺序表内数据连续存储，我们在向顺序表中位置插入或删除数据时，就需要挪动大量的数据，效率不高。

1.3 链表的意义：

人们针对顺序表的这些缺陷，设计出了链表这个概念来克服这些不足。
而链表克服这些缺陷的方法是，将每一个节点划分为数据与指针两部分，数据部分用于存储数据而指针部分用于指向下一节点。这样做的好处是通过指针指向下一节点，于是数据的物理存储就可以不必连续，于是无论是在扩容，还是在插入与删除数据时，都能快速、方便的实现，并且不会造成很大的空间浪费。

2.链表的分类：

2.1 单向或双向：

2.2 带头或不带头：

2.3 循环或非循环：

（注：虽然有很多种不同的链表结构，但是最常用的链表结构主要是两种：无头单向非循环链表与带头双向循环链表）

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
带头双向循环链表：结构最复杂，一般用在单独存储数据。虽然它结构复杂，但在实际使用中使用代码实现后，会带来很多优势，实现反而更加简单。并且在我们的实际中所使用的链表数据结构，一般都是带头双向循环链表。

3.单链表的实现：

3.1 工程文件：

与顺序表的实现方式类似,使用三个文件进行代码书写：

SeqList.h：存放函数声明、包含其他头文件、定义宏。
SeqList.c：书写函数定义，书写函数实现。
test.c：书写程序整体执行逻辑。

其中，我们的接口实现主要研究的是函数实现文件 SeqList.c 中的内容。

单链表和顺序表的结构略有不同，单链表的主结构为节点。
一个节点由两部分组成：data和next。data为我们存储数据的地方。而next则为下一个节点的地址。

typedef struct SListNode
{int data;struct SListNode* next;
}SLTNode;

上面我们设计的是不带哨兵位的单链表。这种结构设计相对于带哨兵位的链表的缺点就是设计接口函数时需要考虑链表是否为空的情况。

哨兵位也叫哨兵节点，哑节点。该节点并不存储任何数据，只是为了方便操作而引入这个节点。起一个站岗放哨的作用。所以形象的叫它哨兵位。如果一个链表有哨兵位，那么链表的第一个元素应该是链表第二个节点对应的元素。这时链表永不为空，这就可以避免边界问题的处理，简化代码与减少代码出错的可能性。

3.2 接口设计

void SLPrint(SLNode* SLHead);    //打印单链表
SLNode* BuyListNode(SLDataType x);    //申请新节点
void SLPushBack(SLNode** pphead, SLDataType x);    //单链表尾插
void SLPushFront(SLNode** pphead, SLDataType x);    //单链表头插
void SLPopBack(SLNode** pphead);    //单链表尾删
void SLPopFront(SLNode** pphead);    //单链表头删
void SLFind(SLNode* phead, SLDataType x);    //单链表查找
void SLInsertFront(SLNode** pphead, SLNode* pos, SLDataType x);    //单链表前插
void SLInsertAfter(SLNode* pos, SLDataType x);    //单链表后插
void SLErase(SLNode** pphead, SLNode* pos);    //单链表删除
void SLEraseAfter(SLNode** pphead, SLNode* pos);//单链表后删除
void SLDestory(SLNode** pphead);    //单链表销毁

我们发现绝大多数接口的参数都为二级指针，这是为什么？
我们先了解一下平时单链表的测试用例：

void TestList()
{SLTNode* plist = NULL;
}

链表的一开始是空的。所以我们插入数据时，需要让plist指向我们新节点。就相当于改变plist的指向。plist是一级指针，那么要改变plist就要传它的地址&plist，为二级指针，所以也需要用二级指针来接收该参数。

就好比当我们要改变一个int类型的变量时a，我们需要传它的地址&a，那么函数的形参就应该用int* 接收；对于指针也是这样，一个int* 的指针变量p，它也是变量，我们需要改变这个值，就应该传它的地址&p，那么函数参数就应该那int* * 接收。

而对于一些接口就不需要传二级指针，就拿打印来说吧，因为我并不需要改变plist，我只需要通过结构体指针访问结构内的next成员，并迭代到下一个节点，然后打印出数据就可以，所以不需要传二级指针。

3.3 重点接口实现：

这里是本文的重点，即 SeqList.c 文件中的接口具体实现：

①.创建新节点：

在各项操作前，需动态创建新节点，再对新创建的节点进行操作。

SLNode* BuyListNode(SLDataType x)
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));if (newnode == NULL){perror("newnode:>");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}

②.打印单链表：

执行操作前无需进行断言，原因是循环条件为空指针，则条件不满足并停止循环，不会出现死循环。
根据指针循环操作，打印数据后使指针指向节点内存放下一节点地址的指针 next。

void SListPrint(SLNode* SLHead)
{SLNode* cur = SLHead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\\n");
}

③.单链表尾插：

1. 如果此时头节点为空指针，说明此时单链表内没有节点，此时只需要将申请来的新节点作为头节点即可。
2. 若头节点不为空，则应当首先找到尾节点，使尾结点指针指向申请来的新节点后，再使新节点指针指向空即可。

void SLPushBack(SLNode** pphead, SLDataType x)
{SLNode* newnode = BuyListNode(x);if (*pphead == NULL){*pphead = newnode;}else{//找到尾结点SLNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

测试接口：

④.单链表头插：

头插实现非常简单，首先申请新节点，先使新节点的指针指向原来的头节点，再使链表头指向新节点即可。
这里不需要考虑空节点的原因是，就算链表内没有内容，即首节点为空，新节点指针指向空也没有问题（申请新节点时原本就指向空）。

void SLPushFront(SLNode** pphead, SLDataType x)
{SLNode* newnode = BuyListNode(x);newnode->next = *pphead;*pphead = newnode;
}

测试接口：

⑤.单链表尾删：

执行操作前需要进行非空判断，防止传入空指针。

• 若链表内只有一个节点，则直接释放并置空即可。
• 若有一个以上节点，则当执行下面三个步骤：

1. 首先寻找尾节点，找到后将其释放并置空。
2. 但在释放前，必须将倒数第二个节点的指针指向空，否则将在指向最后一个被释放的节点时，变成野指针。
3. 单向链表无法回溯，于是我们应当定义另一个指针，在每次移动尾节点指针前保存当前节点的位置。

void SLPopBack(SLNode** pphead)
{//判断链表是否为空：if (*pphead == NULL){return;}//若只有一个节点，直接释放并置空即可：if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//若有多个节点则执行多步尾删：else{SLNode* tail = *pphead;SLNode* prev = NULL;//找到尾节点：while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}
}

测试接口：

⑥.单链表头删：

执行操作前判断指针非空，防止对空指针进行操作。
使链表头指向第二个节点，接着将第一个节点释放并置空即可。

void SLPopFront(SLNode** pphead)
{if (*pphead == NULL){return;}else{SLNode* next = (*pphead)->next;free(*pphead);*pphead = next;}
}

测试接口：

⑦.单链表查找：

采用遍历思想，依次对每一个节点的数据进行判断，符合条件即进行打印，不符合条件则继续向后遍历，直至指向 NULL，并且因此无需进行非空判断。

void SLFind(SLNode* phead, SLDataType x)
{SLNode* cur = phead;int count = 1;while (cur){if (cur->data == x){printf("第%d个节点：%p -> %d\\n", count++, cur, x);}cur = cur->next;}
}

测试接口：

⑧.单链表插入：

单链表在插入新节点时有两种插入方式，一种是在目标节点前方插入，另一种是在目标节点后方插入，因此需要分别进行实现：

Ⅰ、单链表前插：

前插有两种情况:

1. 在首节点处插入，此时即相当于头插操作。
2. 在非首节点前插入，此时首先申请新节点，接着遍历单链表，找到插入位置后，使新节点指向目标节点后插入其前方。

void SLInsertFront(SLNode** pphead, SLNode* pos, SLDataType x)
{//首先申请新节点SLNode* newnod = BuyListNode(x);//头插if (*pphead == pos){newnod->next = *pphead;*pphead = newnod;}else{//找到目标节点 pos 的前一个节点：SLNode* PostPrev = *pphead;while (PostPrev->next != pos){PostPrev = PostPrev->next;}//找到后插入新节点：PostPrev->next = newnod;newnod->next = pos;}
}

测试接口：
同下图

Ⅱ、单链表后插：

在前插操作时，我们需要遍历整个链表来查找插入位置，因此效率较为低下，于是我们通常使用后插的方式插入新节点。后插直接申请节点，插入目标位置后即可。

void SLInsertAfter(SLNode* pos, SLDataType x)
{SLNode* newnode = BuyListNode(x);newnode->next = pos->next;pos->next = newnode;
}

测试接口：

⑨.单链表删除：

I、删除pos位置的节点

分为两种情况进行处理:

1. 一种情况是整个链表中只有一个节点，则删除节点相当于释放整个数组并置空。
2. 另一种情况是含有一个以上节点，此时只需要让目标节点的前一个节点指针指向后一个节点，再释放目标节点并置空即可。

void SLErase(SLNode** pphead, SLNode* pos)
{//头删if (*pphead == pos){*pphead = pos->next;free(pos);pos = NULL;}else{	//找到目标节点 pos 的前一个节点：SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}

测试接口：
同下图

II、删除pos位置之后的节点

和在pos位置之前插入一样，我们发现删除pos位置的节点，也很麻烦。因为需要找pos的前一个位置，所以这种设计也比较麻烦。
所以有时我们会删除pos位置之后的节点，这样就很方便了。
既然要删除pos位置之后的节点，那么我就需要将pos位置的节点pos位置的 next 的 next 链接起来。那么我们首先用next拷贝记录一下pos->next ，然后，再将pos->next赋值为next->next，也就是pos往后的两个节点。最后释放next位置的节点即可。
注意:pos位置的下一个节点不能是尾结点后面的节点

// 删除指定pos位置后的一个节点
void SLEraseAfter(SLNode** pphead, SLNode* pos)
{assert(pos);assert(pos->next);// 删除的不能是尾结点后面的位置SLNode* next = pos->next;// 拷贝pos的下一个节点pos->next = next->next;// 将pos的next变为下一个节点的nextfree(next);// 释放之前pos的下一个节点next = NULL;
}

测试接口：

⑩.单链表销毁：

遍历整个单链表，将每一个节点都进行释放并置空即可。
注意:记得把*pphead置空，防止野指针问题出现

void SListDestory(SLNode** pphead)
{if (*pphead == NULL){return;}SLNode* cur = *pphead;while (cur){SLNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;
}

测试接口：

4.链表实现全部源码：

4.1 SList.h：

#pragma once#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>
typedef int SLDataType;//单链表节点结构：
typedef struct SListNode
{SLDataType data;struct SListNode* next;
}SLNode;void SLPrint(SLNode* SLHead);    //打印单链表
SLNode* BuyListNode(SLDataType x);    //申请新节点
void SLPushBack(SLNode** pphead, SLDataType x);    //单链表尾插
void SLPushFront(SLNode** pphead, SLDataType x);    //单链表头插
void SLPopBack(SLNode** pphead);    //单链表尾删
void SLPopFront(SLNode** pphead);    //单链表头删
void SLFind(SLNode* phead, SLDataType x);    //单链表查找
void SLInsertFront(SLNode** pphead, SLNode* pos, SLDataType x);    //单链表前插
void SLInsertAfter(SLNode* pos, SLDataType x);    //单链表后插
void SLErase(SLNode** pphead, SLNode* pos);    //单链表删除
void SLEraseAfter(SLNode** pphead, SLNode* pos);//单链表后删除
void SLDestory(SLNode** pphead);    //单链表销毁

4.2 SList.c：

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"	
//打印单链表：
void SLPrint(SLNode* SLHead)
{SLNode* cur = SLHead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\\n");
}//申请节点：
SLNode* BuyListNode(SLDataType x)
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));if (newnode == NULL){perror("newnode:>");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}//单链表尾插：
void SLPushBack(SLNode** pphead, SLDataType x)
{SLNode* newnode = BuyListNode(x);if (*pphead == NULL){*pphead = newnode;}else{//找到尾结点SLNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}//单链表头插：
void SLPushFront(SLNode** pphead, SLDataType x)
{SLNode* newnode = BuyListNode(x);newnode->next = *pphead;*pphead = newnode;
}//单链表尾删：
void SLPopBack(SLNode** pphead)
{//判断链表是否为空：if (*pphead == NULL){return;}//若只有一个节点，直接释放并置空即可：if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//若有多个节点则执行多步尾删：else{SLNode* tail = *pphead;SLNode* prev = NULL;//找到尾节点：while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}
}//单链表头删
void SLPopFront(SLNode** pphead)
{if (*pphead == NULL){return;}else{SLNode* next = (*pphead)->next;free(*pphead);*pphead = next;}
}//单链表查找
void SLFind(SLNode* phead, SLDataType x)
{SLNode* cur = phead;int count = 1;while (cur){if (cur->data == x){printf("第%d个节点：%p -> %d\\n", count++, cur, x);}cur = cur->next;}
}//单链表前插：
void SLInsertFront(SLNode** pphead, SLNode* pos, SLDataType x)
{//首先申请新节点SLNode* newnod = BuyListNode(x);if (*pphead == pos){newnod->next = *pphead;*pphead = newnod;}else{//找到目标节点 pos 的前一个节点：SLNode* PostPrev = *pphead;while (PostPrev->next != pos){PostPrev = PostPrev->next;}//找到后插入新节点：PostPrev->next = newnod;newnod->next = pos;}
}//单链表后插：
void SLInsertAfter(SLNode* pos, SLDataType x)
{SLNode* newnode = BuyListNode(x);newnode->next = pos->next;pos->next = newnode;
}//单链表删除：
void SLErase(SLNode** pphead, SLNode* pos)
{if (*pphead == pos){*pphead = pos->next;free(pos);pos = NULL;}else{SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}
// 删除指定pos位置后的一个节点
void SLEraseAfter(SLNode** pphead, SLNode* pos)
{assert(pos);assert(pos->next);// 删除的不能是尾结点后面的位置SLNode* next = pos->next;// 拷贝pos的下一个节点pos->next = next->next;// 将pos的next变为下一个节点的nextfree(next);// 释放之前pos的下一个节点next = NULL;
} 
//单链表销毁：
void SLDestory(SLNode** pphead)
{if (*pphead == NULL){return;}SLNode* cur = *pphead;while (cur){SLNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;
}

4.3 test.c：

#define _CRT_SECURE_NO_WARNINGS 1 #include "SList.h"// 测试尾插、带节点的头插
void TestList1()
{SLNode* plist = NULL;//SLPushBack(&plist, 1);//SLPushBack(&plist, 2);//SLPushBack(&plist, 3);//SLPushBack(&plist, 4);//SLPrint(plist);//SLPushBack(&plist, 5);//SLPrint(plist);SLPushFront(&plist, 1);SLPushFront(&plist, 2);SLPushFront(&plist, 3);SLPushFront(&plist, 4);SLPrint(plist);SLPushFront(&plist, 5);SLPrint(plist);}// 测试头插、尾删
void TestList2()
{SLNode* plist = NULL;SLPushFront(&plist, 1);SLPushFront(&plist, 2);SLPushFront(&plist, 3);SLPushFront(&plist, 4);SLPushFront(&plist, 5);SLPrint(plist);SLPopBack(&plist);SLPopBack(&plist);SLPopBack(&plist);SLPopBack(&plist);SLPrint(plist);SLPopBack(&plist);SLPrint(plist);}// 测试头删
void TestList3()
{SLNode* plist = NULL;SLPushFront(&plist, 1);SLPushFront(&plist, 2);SLPushFront(&plist, 3);SLPushFront(&plist, 4);SLPushFront(&plist, 5);SLPrint(plist);SLPopFront(&plist);SLPrint(plist);SLPopFront(&plist);SLPrint(plist);SLPopFront(&plist);SLPrint(plist);SLPopFront(&plist);SLPrint(plist);SLPopFront(&plist);SLPrint(plist);}void TestList4()
{SLNode* plist = NULL;SLPushFront(&plist, 1);SLPushFront(&plist, 2);SLPushFront(&plist, 3);SLPushFront(&plist, 2);SLPushFront(&plist, 5);SLNode* pos = SLFind(plist, 2);int i = 1;while (pos){printf("第%d个pos节点：%p->%d\\n", i++, pos, pos->data);pos = SLFind(pos->next, 2);}// 修改 3->30pos = SLFind(plist, 3);if (pos){pos->data = 30;}SLPrint(plist);
}void TestList5()
{SLNode* plist = NULL;SLPushFront(&plist, 1);SLPushFront(&plist, 2);SLPushFront(&plist, 3);SLPushFront(&plist, 2);SLPushFront(&plist, 5);// 3前面插入一个30SLNode* pos = SLFind(plist, 3);if (pos){SLInsertFront(&plist, pos, 30);}SLPrint(plist);// 5后面插入一个10pos = SLFind(plist, 5);if (pos){SLInsertAfter( pos, 10);}SLPrint(plist);
}
void TestList6()
{SLNode* plist = NULL;SLPushFront(&plist, 1);SLPushFront(&plist, 2);SLPushFront(&plist, 3);SLPushFront(&plist, 2);SLPushFront(&plist, 5);SLPrint(plist);// 删除3位置节点SLNode* pos = SLFind(plist, 3);if (pos){SLErase(&plist, pos);}SLPrint(plist);// 删除4位置之后节点pos = SLFind(plist, 5);if (pos){SLEraseAfter(&plist, pos);}SLPrint(plist);SLDestory(&plist);SLPrint(plist);}int main()
{//TestList1();//TestList2();//TestList3();//TestList4();//TestList5();TestList6();return 0;
}

5.总结：

今天我们认识并学习了单向无头链表的相关概念、结构与接口实现，并且针对每个常用的功能接口都进行了实现分解，并对各个接口的各项注意点都进行了强调说明，希望我的文章和讲解能对大家的学习提供一些帮助。

当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~