个人主页：strive-debug
链表的概念与实现
概念
链表是一种物理存储结构上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现的。单链表的好处是不会浪费空间。
比喻
可以将单链表想象成一节节火车车厢。每个车厢相当于一个节点，通过锁链（指针）连接起来。单链表只能单向遍历，不能往回遍历。在编写代码时需要考虑头结点是否为空。
结构体定义
结合前面学到的结构体知识，我们可以给出每个结点对应的结构体代码。假设当前保存的结点为整型：
struct SListNode {
int data; // 结点数据
struct SListNode* next; // 指针变量用于保存下一个结点的地址
};
当我们想要保存一个整型数据时，实际上是向操作系统申请了一块内存。这个内存不仅要保存整型数据，还需要保存下一个结点的地址。
链表的实现
typedef int SLTDataType;
typedef struct SListNode {
SLTDataType data; // 结点数据
struct SListNode* next; // 指针保存下一个结点的地址
} 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* phead, SLTDataType x);
// 在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);
// 在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
// 删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);
// 销毁链表
void SListDestroy(SLTNode** pphead);
注意事项
1. 单链表传的是二级指针，顺序表是一级指针。
2. 顺序表和链表在数据存储上：顺序表要加“ * ”，而链表不需要。
3. 查找时：顺序表需要 `int` 类型来接收，而链表需要的是指针来接收。
4. 空间申请：
- 顺序表需要 `realloc` 来申请额外的空间，计算的是 `int` 类型的（根据实际来看）。
- 链表需要 `malloc` 来开辟 `struct` 类型的空间，计算的也是 `struct` 的空间。
5. 访问数据时：
- 顺序表需要使用数组的取法（`arr[]`），顺序表的底层就是数组。
- 链表仅需要指针取数据的取法（`ps->data`）。
错误处理
如果遇到报错不要紧张：
1. 检查代码是否有拼写错误。
2. 检查实参和形参类型是否正确。
3. 查看报错信息。如果是访问权限问题，说明前面或现在的代码存在顺序问题或空间开的不对。
4. 快速检测错误的方法：通过注释要测试的代码来看哪个出现错误。注释掉通过了就是哪个。
希望这些信息能帮助您更好地理解和实现链表！