概念与结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 逻辑结构：线性 物理结构（存储结构）：不一定是线性的
可以把链表想象成一列火车，车头是哨兵位（可有可无），车厢就是节点。将某节车厢去掉或加上，不会影响其他车厢，每节车厢都是独立存在的。
在链表里，每节'车厢'是什么样的呢？
结点
与顺序表不同的是，链表里的每节'车厢'都是独立申请下来的空间，我们称之为'结点'。结点的组成主要有两个部分：当前结点要保存的数据和保存下一个结点的地址（指针变量）。
链表中每个结点都是独立申请的（即需要插入数据时才去申请一块结点的空间），我们需要通过指针变量来保存下一个结点位置才能从当前结点找到下一个结点。
链表的性质
- 链式机构在逻辑上是连续的，在物理结构上不一定连续。
- 结点一般是从堆上申请的。
- 从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续。
结合前面学到的结构体知识，我们可以给出每个结点对应的结构体代码。假设当前保存的结点为整型：
struct SListNode {
int data; // 结点数据
struct SListNode* next; // 指针变量，用于保存下一个结点的地址
};
当我们想要保存一个整型数据时，实际是向操作系统申请了一块内存，这块内存不仅要保存整型数据，也需要保存下一个结点的地址（当下一个结点为空时保存的地址为空）。当我们想要从第一个结点走到最后一个结点时，只需要在当前结点拿取下一个结点的地址就可以了。
实现单链表
头文件 (SList.h)
这里定义了链表的数据类型、节点结构以及所有操作的函数声明。注意 SLTNode 是 struct SListNode 的别名，方便后续使用。
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// 链表的数据类型
typedef int SLTDataType;
// 链表的结构
typedef struct SListNode {
SLTDataType data;
struct SListNode* next; // 指向下一个节点的地址
} SLTNode;
// 尾插
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);
// 在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
// 删除 pos 结点
void SLTErase(SLTNode** pphead, SLTNode* pos);
// 删除 pos 之后的结点
void SLTEraseAfter(SLTNode* pos);
// 销毁链表
void SListDestroy(SLTNode** pphead);
// 打印链表
void SLTPrint(SLTNode* phead);
源文件 (SList.c)
单链表的打印
遍历链表，输出每个节点的数据，直到遇到空指针。
void SLTPrint(SLTNode* phead) {
SLTNode* pcur = phead;
while (pcur != NULL) {
printf("%d -> ", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
单链表申请新节点内存
这是创建节点的基础函数，负责从堆上分配内存并初始化。
SLTNode* SLTBuyNode(SLTDataType x) {
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL) {
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
这里是申请新节点，并且把对应的数据存入节点中，所以接下来只需要将各个节点连接起来（链表中的指针）。
尾插
在链表尾部添加新节点。如果链表为空，新节点直接成为头结点；否则需要遍历到尾端再连接。
// 尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) {
assert(pphead);
// 申请新节点
SLTNode* newnode = SLTBuyNode(x);
// 链表为空
if (*pphead == NULL) {
*pphead = newnode;
} else {
SLTNode* ptail = *pphead;
while (ptail->next != NULL) {
ptail = ptail->next;
}
// 找到了尾结点 ptail，将新节点接在后面
ptail->next = newnode;
}
}
传址调用，使用
SLTNode** pphead，不然无法修改SLTNode* phead结构体指针。需要做出特殊判断，当链表为空的时候。
头插
在链表头部添加新节点。新节点的 next 指向原头结点，然后更新头指针。
// 头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
// newnode -> *pphead
newnode->next = *pphead;
*pphead = newnode;
}
尾删
删除链表尾部的节点。需要找到倒数第二个节点，将其 next 置为 NULL，并释放原尾节点。注意处理只有一个节点的情况。
// 尾删
void SLTPopBack(SLTNode** pphead) {
// 链表为空不能删除
assert(pphead && *pphead);
// 链表只有一个节点的情况
if ((*pphead)->next == NULL) {
free(*pphead);
*pphead = NULL;
} else {
SLTNode* prev = NULL;
SLTNode* ptail = *pphead;
while (ptail->next) {
prev = ptail;
ptail = ptail->next;
}
// prev -> ptail
prev->next = NULL;
free(ptail);
ptail = NULL;
}
}
处理特殊情况，链表只有一个节点的情况。链表为空不能删除。
头删
删除链表头部的节点。先保存下一个节点地址，释放当前头结点，然后更新头指针。
// 头删
void SLTPopFront(SLTNode** pphead) {
assert(pphead && *pphead);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
查找
遍历链表寻找值为 x 的节点。不需要传二级指针，因为只读不写头指针。
// 查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {
SLTNode* pcur = phead;
while (pcur) {
if (pcur->data == x) {
return pcur;
}
pcur = pcur->next;
}
// 未找到
return NULL;
}
在指定位置之前插入数据
在 pos 节点之前插入新节点。如果 pos 是头结点，则退化为头插操作；否则需要找到 pos 的前驱节点。
// 在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
assert(pphead && pos);
SLTNode* newnode = SLTBuyNode(x);
// pos 指向头结点
if (pos == *pphead) {
SLTPushFront(pphead, x);
} else {
// 找 pos 的前一个节点
SLTNode* prev = *pphead;
while (prev->next != pos) {
prev = prev->next;
}
// prev -> newnode -> pos
prev->next = newnode;
newnode->next = pos;
}
}
pos 不能为空指针。特殊情况，pos 指向头结点。
在指定位置之后插入数据
在 pos 节点之后插入新节点。逻辑相对简单，只需调整指针指向。
// 在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
// pos -> newnode -> pos->next
newnode->next = pos->next;
pos->next = newnode;
}
删除 pos 结点
删除指定的 pos 节点。如果 pos 是头结点，执行头删；否则找到前驱节点，断开连接并释放内存。
// 删除 pos 结点
void SLTErase(SLTNode** pphead, SLTNode* pos) {
assert(pphead && pos);
// pos 刚好就是头结点——头删
if (pos == *pphead) {
SLTPopFront(pphead);
} else {
SLTNode* prev = *pphead;
while (prev->next != pos) {
prev = prev->next;
}
// prev -> pos->next
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
pos 不能为空指针。特殊情况，pos 刚好就是头结点—头删。
删除 pos 之后的结点
删除 pos 节点的下一个节点。需要确保 pos 和 pos->next 都不为空。
// 删除 pos 之后的结点
void SLTEraseAfter(SLTNode* pos) {
assert(pos && pos->next);
// pos -> del -> del->next
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
销毁链表
遍历整个链表，逐个释放节点内存，最后将头指针置空。
// 销毁链表
void SListDestroy(SLTNode** pphead) {
assert(pphead);
SLTNode* pcur = *pphead;
while (pcur) {
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}
链表的分类
链表的结构非常多样，以下情况组合起来就有 8 种（2 x 2 x 2）链表结构：有无头结点、单向/双向、循环/非循环。
虽然有这么多的链表结构，但是我们实际中最常用还是两种结构：
- 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。
在实际开发中，理解单链表是基础，掌握其内存模型和指针操作对于深入理解 C/C++ 至关重要。