目录
引言
在前面的学习中，我们深入了解了顺序表，通过其增删查改的操作，我们发现了顺序表在某些情况下的劣势。尤其是在头插头删或者中间位置的插入删除操作时，由于需要挪动数据，顺序表的效率显著降低。另外，顺序表在满容时需要进行扩容，而这一过程不仅带来一定的性能开销，而且扩容过多可能导致空间浪费，扩容过少则可能频繁触发扩容操作。为了克服这些问题，引入了链表这一数据结构。链表的灵活性使其能够更高效地处理插入和删除操作，为解决顺序表的局限性提供了一种优秀的选择。
链表介绍
链表是一种基础的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。在链表中，节点之间通过指针相互连接，而非像数组那样在内存中紧密排列。
这里以单向带头链表为例，第一个节点是哨兵位节点，它不存放有效数据，只存放一个指向链表头节点的指针，除哨兵位外，链表中的每个节点都存放一个有效数据以及指向下一个节点的指针。链表通过这些指针相互链接，形成一个动态的数据结构。需要注意的是，链表的节点空间都是在堆上申请的，因此节点之间的地址在物理空间上是不连续的。然而，我们可以将它在逻辑上视为连续的结构，通过指针的连接实现节点之间的逻辑关联。
关于链表的结构在《带头双向循环链表》这一文中有介绍，这里就不过多阐述了。本文重点介绍无头单向非循环链表（下文皆简称为单向链表）的基本接口实现。
单向链表的接口实现
结构
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType; // 定义整型数据类型 STDataType
typedef struct SListNode // 定义链表节点结构 SListNode
{
STDataType val; // 节点存储的数据值
struct SListNode* next; // 指向下一个节点的指针
} SListNode;
e;创建节点
// CreateNode: 创建一个包含给定数据的新链表节点
// val: 新节点要存储的数据值
// 返回值: 返回指向新节点的指针
SListNode* CreateNode(STDataType val)
{
// 使用malloc分配新节点的内存空间
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
// 检查内存分配是否成功
if (newnode == NULL)
{
perror("malloc fail");
exit(-1); // 内存分配失败，输出错误信息并终止程序
}
// 初始化新节点的数据和指针成员
newnode->val = val;
newnode->next = NULL;
return newnode; // 返回指向新节点的指针
}
首先，通过 malloc 分配了一块内存来存储新的节点。接着，通过条件判断确保内存分配成功，如果分配失败则输出错误信息，并通过 exit 终止程序。然后，将节点的数据成员 val 设置为传入的参数 val，表示节点存储的有效数据。最后，将节点的指针成员 next 初始化为 NULL，表示该节点暂时没有下一个节点。最终，函数返回创建的新节点。这段代码的主要作用是为链表创建新的节点，并初始化节点的数据和指针。
头插
// SListPushFront: 在链表头部插入新节点
// pphead: 指向头指针的指针，传入二级指针是因为可能需要修改头指针
// val: 新节点要存储的数据值
void SListPushFront(SListNode** pphead, STDataType val)
{
// 确保头指针的有效性
assert(pphead);
// 创建新节点
SListNode* newnode = CreateNode(val);
// 将新节点的下一个节点指向当前的头节点
newnode->next = *pphead;
// 更新头指针，使其指向新插入的节点
*pphead = newnode;
}
链表的头插非常方便，只需要让新节点的next指针指向当前的头节点，然后更新头节点即可。值得注意的是，这里传入的是二级指针，因为如果头节点原本是空的话，我们就要把头节点更新为新创建的newnode 节点，如果我们传递的是一级指针，我们只能修改头节点所指向的数据，而无法修改头指针本身。通过使用二级指针，我们可以在需要时修改头指针，确保链表的头正确指向新插入的节点。
尾插
void SListPushBack(SListNode** pphead, STDataType val)
{
// 断言确保头指针的有效性
assert(pphead);
// 创建新节点并初始化
SListNode* newnode = CreateNode(val);
// 如果链表为空，将头指针指向新节点
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
// 否则，遍历到链表末尾
SListNode* cur = *pphead;
while (cur->next)
{
cur = cur->next;
}
// 将新节点链接到末尾
cur->next = newnode;
}
}
首先，通过断言确保头指针的有效性。然后，创建一个新节点并初始化其值。接着，判断链表是否为空，如果是，直接将头指针指向新节点；否则，遍历链表到末尾，并将新节点链接到末尾。这里也再一次证明了为什么要传二级指针，当链表为空时，它也涉及到了修改头指针。
头删
void SListPopFront(SListNode** pphead)
{
// 断言确保头指针的有效性和链表非空
assert(pphead);
assert(*pphead);
// 临时指针指向头节点的下一个节点
SListNode* tmp = (*pphead)->next;
// 释放原头节点的内存
free(*pphead);
// 更新头指针为下一个节点
*pphead = tmp;
}
首先，通过两个断言确保头指针的有效性和链表非空。然后，使用临时指针 tmp 指向头结点的下一个节点。接着，释放原头结点的内存，最后，更新头指针为下一个节点。这里关键点在于释放头节点内存前，要先保存下一个节点，如果上来就释放的话，下一个节点就找不到了。
尾删
void SListPopBack(SListNode** pphead)
{
// 断言确保头指针的有效性和链表非空
assert(pphead);
assert(*pphead);
// 如果链表只有一个节点，直接释放头结点并将头指针置为NULL
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
// 否则，遍历链表到倒数第二个节点
SListNode* cur = *pphead;
while (cur->next->next)
{
cur = cur->next;
}
// 释放尾节点的内存并将倒数第二个节点的next置为NULL
free(cur->next);
cur->next = NULL;
}
}
首先，通过两个断言确保头指针的有效性和链表非空。然后，判断链表是否只有一个节点，如果是，直接释放头结点并将头指针置为NULL。否则，遍历链表到倒数第二个节点，释放尾节点的内存，并将倒数第二个节点的next置为NULL，避免野指针问题。
打印
void SListPrint(SListNode** pphead)
{
// 断言确保头指针的有效性
assert(pphead);
// 初始化当前节点指针为头指针
SListNode* cur = *pphead;
// 遍历链表，打印每个节点的值
while (cur)
{
printf("%d ", cur->val);
cur = cur->next;
}
// 打印换行，表示输出结束
printf("\n");
}
首先，通过断言确保头指针的有效性。然后，初始化当前节点指针为头指针，使用循环遍历链表，打印每个节点的值。这里可以只传一级指针，因为不会涉及头指针的修改，为了统一我都传了二级指针。
节点查找
SListNode* SListFind(SListNode** pphead, STDataType val)
{
// 断言确保头指针的有效性
assert(pphead);
// 初始化当前节点指针为头指针
SListNode* cur = *pphead;
// 遍历链表，查找节点值等于给定值的节点
while (cur)
{
if (cur->val == val)
return cur;
cur = cur->next;
}
// 如果未找到匹配节点，返回NULL
return NULL;
}
首先，通过断言确保头指针的有效性。然后，初始化当前节点指针为头指针，使用循环遍历链表，查找节点值等于给定值的节点。如果找到匹配节点，则返回指向该节点的指针；如果未找到匹配节点，返回NULL。这个函数用来配合接下来的两个函数，进行具体节点位置的插入或删除。
节点前插入
void SListInsert(SListNode** pphead, SListNode* pos, STDataType val)
{
// 断言确保头指针和目标位置指针的有效性
assert(pphead);
assert(*pphead);
assert(pos);
// 初始化当前节点指针为头指针
SListNode* cur = *pphead;
// 如果目标位置是头结点
if (cur == pos)
{
// 创建新节点，将新节点插入到头结点之前
SListNode* newnode = CreateNode(val);
newnode->next = cur;
*pphead = newnode;
}
else
{
// 否则，遍历链表找到目标位置之前的节点
while (cur && cur->next != pos)
{
cur = cur->next;
}
// 如果找到目标位置之前的节点，插入新节点
if (cur)
{
SListNode* newnode = CreateNode(val);
newnode->next = pos;
cur->next = newnode;
}
}
}
首先，通过断言确保头指针和目标位置指针的有效性。然后，初始化当前节点指针为头指针。如果目标位置是头结点，创建新节点并将其插入到头结点之前，其实就是头插；否则，遍历链表找到目标位置之前的节点，然后插入新节点。这里也可以不断言pos和头节点，但是这样没意义，因为如果pos为空直接尾插就好了嘛，没必要来调用这个函数。
节点删除
void SListErase(SListNode** pphead, SListNode* pos)
{
// 断言确保头指针和目标位置指针的有效性
assert(pphead);
assert(*pphead);
assert(pos);
// 初始化当前节点指针为头指针
SListNode* cur = *pphead;
// 如果目标位置是头结点
if (cur == pos)
{
// 更新头指针为下一个节点，释放原头结点的内存
*pphead = (*pphead)->next;
free(pos);
}
else
{
// 否则，遍历链表找到目标位置之前的节点
while (cur && cur->next != pos)
{
cur = cur->next;
}
// 如果找到目标位置之前的节点，删除目标节点，释放内存
if (cur)
{
cur->next = pos->next;
free(pos);
}
}
}
首先，通过断言确保头指针和目标位置指针的有效性。然后，初始化当前节点指针为头指针。如果目标位置是头结点，更新头指针为下一个节点，释放原头结点的内存，这里也可以直接调用前面的头删函数；否则，遍历链表找到目标位置之前的节点，然后删除目标节点，释放内存。
内存释放
void SListDestroy(SListNode** pphead)
{
// 断言确保头指针的有效性
assert(pphead);
// 初始化当前节点指针为头指针
SListNode* cur = *pphead;
// 遍历链表，释放所有节点的内存
while (cur)
{
// 保存下一个节点的指针，以便后续访问
SListNode* tmp = cur->next;
// 释放当前节点的内存
free(cur);
// 将当前节点指针更新为下一个节点
cur = tmp;
}
// 将头指针置为NULL，表示链表已销毁
*pphead = NULL;
}
首先，通过断言确保头指针的有效性。然后，初始化当前节点指针为头指针。通过循环遍历链表，释放每个节点的内存。在释放每个节点之前，保存下一个节点的指针以便后续访问。最后不要忘了将头指针置为NULL，防止出现野指针问题，在释放内存后，手动将指针置空是一个好习惯哦。
总结
在本博客中，我们深入探讨了单向链表这一数据结构的核心概念和实现。从链表的基本介绍开始，我们详细介绍了单向链表的接口实现，包括节点的创建、头插法、尾插法、头删法、尾删法、打印链表、节点查找、节点前插入、节点删除以及内存释放这些关键操作。通过这些接口实现，读者能够全面了解单向链表的结构和各种基本操作的实现方式。总的来说，本博客为初学者提供了一个全面而易懂的单向链表学习指南，使其能够在实际应用中更加灵活地操作和理解这一重要的数据结构。想要更好地掌握链式结构的话，还需要读者自己实现一下这些接口，还可以通过刷一些链表的题目来加深对链式结构的理解，链式结构在往后的学习中还有非常大的用处。
![【算法每日一练]-图论（保姆级教程篇12 tarjan篇）#POJ3352道路建设 #POJ2553图的底部 #POJ1236校园网络 #缩点](https://img-blog.csdnimg.cn/f68d05a84ef541f595c0886ca4d6a348.png)
