欢迎来到白刘的领域 Miracle_86.-CSDN博客
系列专栏 数据结构与算法
先赞后看，已成习惯
创作不易，多多支持！
一、链表的概念和结构
1.1 链表的概念
在上一篇文章中，我们了解了线性表(linear list)，并且学习了其中一种线性表——顺序表(Sequence List)。链表也是线性表的一种，那么它是一种什么样的结构呢？
链表，顾名思义，带着链子的表。日常生活中，我们知道链子是用来链接两个东西的，那么我们可以很容易理解，顺序表是基于数组实现的，是一个元素一个元素挨着的，那链表我们就可以理解为每个元素用链子连接起来，这样就形成了链表(Linked List)。
1.2 链表的结构
那么我们得到了两个链表的组成的关键元素，一个是每个元素，我们管它叫节点(或结点)，另一个就是那个链子。而在C语言中，我们用结构体来实现节点，用指针来充当链，连接两个节点。
在生活中链表类似于我们的火车的结构，在物理上它是一种存储结构非顺序非连续的结构。
节点的组成主要由两个部分组成：一个是数值域，用来保存当前节点的数据，一个是指针域，用来保存下一个节点的地址(指针变量)。
如图所示，指针变量plist保存的是第一个节点的地址，如果我们想让plist指向第二个节点，我们只需要将plist保存的内容修改为0x0012FFD0。
为什么我们需要指针变量来保存下一个节点的位置？
因为之前我们说了，链表不同于顺序表，它在内存中的地址不一定是连续的，它是独立申请的(对其插入数据时才申请一个节点)。我们需要通过指针才能从当前节点找到下一个节点。
所以我们可以通过一个结构体来实现一个节点，它要有一个节点的数据以及一个指针变量来保存下一个节点的地址，代码如下：
struct SListNode
{
int data; //节点数据
struct SListNode* next; //指针变量⽤保存下⼀个节点的地址
};当然我们也可以用typedef来进行修改，方便我们后续操作。
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data; //节点数据
struct SListNode* next; //指针保存下⼀个节点的地址
}SLTNode;我们如何将链表进行打印呢？
首先我们将节点传到打印函数，然后我们创建了一个指向头结点的结构体指针，利用循环从头遍历到尾，每次打印完成令pcur指向pcur的next节点。这里注意的就是结构体成员的访问的问题，我们用到了->操作符，在前面的博客我们都介绍过。
武器大师——操作符详解（下）-CSDN博客
代码如下：
void SLTPrint(SLTNode* phead){
SLTNode *cur = phead;
while(cur){
printf("%d ",cur->data);
cur = cur->next;
}
printf("\n");
}二、单链表的实现
上面我们知道了什么是链表，那单链表又是什么呢？单链表(Singly Linked List)，一般所指的是“不带头单向不循环链表”。
我们实现的功能无非就四个“增、删、查、改”。
2.1 增
2.1.1 尾插
尾插，顾名思义，在尾部插入，俗称后入(bushi)。
首先我们要申请新的节点，我们可以写一个申请节点的函数。
SLTNode* BuyNode(SLTDataType x) {
SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
if (node == NULL) {
perror("malloc fail!\n");
exit(1);
}
node->data = x;
node->next = NULL;
return node;
}首先我们用malloc函数动态申请一块内存，然后将节点的数据赋进去。
void SLTPushBack(SLTNode** pphead, SLTDataType x) {
assert(pphead);
SLTNode* node = BuyNode(x);
if (*pphead == NULL) {
*pphead = node;
return;
}
//找尾
SLTNode* cur = *pphead;
while (cur->next) {
cur = cur->next;
}
cur->next = node;
}接下来的代码逻辑特别简单，首先我们通过buynode函数创建了一个节点，然后我们判空，如果这个链表是空的，我们直接将指针变量pphead赋为node。如果不是空的，那我们就需要找到链表的尾部，我们可以通过循环来找到尾部，首先为了防止原来数据被破坏，我们创建一个指向第一个节点的指针变量cur，而不是直接遍历pphead。
注意我们如何找尾，通过判断该节点的下一个位置是否为空。
这里还有一个细节就是，我们传入的是二级指针，因为我们要修改一个数据的话，需要传地址，而那个数据如果是指针的话，我们就需要传指针的地址，也就是二级指针。
2.1.2 头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
assert(pphead);
SLTNode* node = BuyNode(x);
node->next = *pphead;
*pphead = node;
}这个代码逻辑也很简单，首先我们assert断言防止访问空指针，之后buynode函数申请节点，然后将结点接到头部，也就是*pphead，之后别忘了将*pphead再指向node，形成新的头。
2.2 删
2.2.1 尾删
尾删也很简单，仔细思考，我们只需要两步就能完成，一个是找尾，一个是删除。
首先我们来看找尾，我们可以用循环，再加上两个指针，
//找尾
// SLTNode *cur = *pphead;
// SLTNode *prev = NULL;
// while(cur->next){
// prev = cur;
// cur = cur->next;
// }
// prev->next = NULL;
// free(cur);
// cur = NULL;首先cur指向头，prev指向空，cur用来找尾，prev用来保存上一个节点的地址。当cur的下一个位置为NULL时循环结束，意味着找到最后一个节点了，我们将它所指的位置free掉(因为是动态开辟出来的)，然后指针置空即可完成删除。
还有一种方法可以用一个指针就解决，
SLTNode* tail = *pphead;
while (tail->next->next)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;我们判断条件改成这样，实际上我们找的tail是倒数第二个节点，所以最后的删除需要改成tail的next为NULL。
2.2.2 头删
头删的逻辑就更加简单了，我们只需要创建一个变量来保存原来的头节点，方便我们后续删除，然后让原头节点移到下一个结点成为新的头结点，然后删掉原来的。如果我们不保存，我们没有办法找到原来的头结点。
代码如下：
void SLTPopFront(SLTNode** pphead) {
assert(pphead);
assert(*pphead);
SLTNode* first = *pphead;
*pphead = (*pphead)->next;
free(first);
first = NULL;
}2.3 查
这个实现也很简单，就是遍历，然后匹配。由于是查找，而不是对数据进行修改，所以传一级指针即可。
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {
assert(phead);
SLTNode* cur = phead;
while (cur) {
if (cur->data == x) {
return cur;
}
cur = cur->next;
}
return NULL;
}2.4 改
2.4.1 在pos前插入
将图画出来我们就清晰明了了。我们如果想把node插入到pos前，我们只需要将node的next指向pos，然后将prev的next指向node，这样就构成了插入操作。
试想一下，1和2的操作可以调换顺序吗？答案是不可以，这是因为如果我们先做2，这个时候我们就找不到pos了，也就不能执行1操作了。有人会问，我创建两个变量来记录这两个点的位置不可以吗？可以，但是没必要。
之后我们来看代码部分，首先我们要创建一个node节点，用buynode函数。正常情况，我们需要找pos的前一个节点prev，利用循环即可。如果只有一个节点怎么办呢？这个时候直接头插就可以了。
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
assert(pphead);
assert(pos);
SLTNode* node = BuyNode(x);
if (*pphead == pos) {
// node->next = pos;
// *pphead = node;
SLTPushFront(pphead, x);
return;
}
//找pos的前一个节点
SLTNode* prev = *pphead;
while (prev->next) {
if (prev->next == pos) {
break;
}
prev = prev->next;
}
node->next = pos;
prev->next = node;
}2.4.2 删除pos
其实逻辑也是很简单的，要删除pos的话，我们需要找到pos前面的节点保存，否则就找不到了。
void SLTErase(SLTNode** pphead, SLTNode* pos) {
assert(pphead);
assert(pos);
if (*pphead == pos) {
// SLTNode *del = *pphead;
// *pphead = (*pphead)->next;
// free(del);
// del = NULL;
SLTPopFront(pphead);
return;
}
//找pos的前一个节点
SLTNode* prev = *pphead;
while (prev->next) {
if (prev->next == pos) {
break;
}
prev = prev->next;
}
prev->next = pos->next;
free(pos);
// pos = NULL;//没有存在的必要
}并且要注意连接好pos后面的节点后再删除，不然也找不到。
2.4.3 在pos后插入
逻辑跟在pos前插入一样，也要注意顺序，只不过在pos之后插入不需要传链表第一个节点了，只需要传pos即可。
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
assert(pos);
SLTNode* node = BuyNode(x);
node->next = pos->next;
pos->next = node;
}2.4.4 删除pos后的节点
void SLTEraseAfter(SLTNode* pos){
assert(pos);
assert(pos->next);
SLTNode *del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}其实看到这你就发现，对链表的操作无非就是保存节点，然后连接，同时画图操作也可以对我们学习数据结构有所帮助。
2.5 链表的销毁
我们将链表每个节点通过循环遍历free掉即可，唯一比较吃操作的就是创建一个用于保存下一个节点的位置的指针。
//销毁链表
void SListDesTroy(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}
