系列文章目录
前言
大家是否记得我们在顺序表中留下的几个问题？
对于顺序表的空间浪费和插入耗时过长，我们的解决方法就是使用新的数据结构——链表。
一、链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现。
我们可以用火车来类比链表，这两者的结构十分相似。
火车的车厢个数会随着乘客人数的变化而变化，淡季减少，旺季增加；增加的车厢可以在整个火车的任何位置插入进去，且每节车厢独立存在，不影响其他车厢。
每个车厢都有两个门，链接前后车厢。假设：每个车厢门都是关闭状态，需要钥匙打开，我们手上每次只能有一把钥匙，要能走遍所有车厢，应该怎么做？
最简单的办法：在每一节车厢中存放下一节车厢的钥匙即可。
那么在链表里，每节“车厢”是什么样的？
与顺序表不同，链表的每节“车厢”都需要独立申请内存空间，我们称为“节点/结点”。
结点主要由两部分组成：当前节点要保存的数据和下一个节点的地址（指针变量）。
我们为什么要在当前节点里保存下一个节点的地址呢？
链表中的每个节点都是独立申请内存空间，我们需要通过指针变量保存下一个节点的地址才能找到下一个节点，相当于我们要在当前车厢存放下一个车厢的钥匙，才能打开下一个车厢的门。
通过上面对于链表的结构分析，我们能给出每个节点的结构体代码：
struct list
{
int val; // 当前节点需要保存的数据
struct list* next; // 保存下个节点的地址
};我们知道写出每个链表节点，接下来就要将它们连接在一起形成链表：
int main()
{
struct list* phead = NULL; // 定义头指针指向第一个节点
struct list* pcur = phead; // 通过该指针将所有节点连接起来
for (int i = 0; i < 3; i++) // 这里创建了3个结点
{
struct list* newnode = (struct list*)malloc(sizeof(struct list));
// 对每个结点独立申请空间
newnode->val = i; // 写入该节点要保存的数据
newnode->next = NULL; // 若该指针为最后一个节点，不让其指向有效地址，防止野指针
if (phead == NULL) // 头指针为空，使其指向第一个节点
pcur = phead = newnode;
else
{
pcur->next = newnode; // 让上一个节点next指向当前节点
pcur = newnode; // 将pcur重新指向当前节点
}
}
return 0;
}接下来，对于一个给定的链表，我们如何实现节点从头到尾的打印呢？
pcur = phead; // 是遍历节点的指针指向第一个节点
while (pcur) // 如果pcur为空，说明没有节点，跳出循环
{
printf("%d ", pcur->val); // 打印当前节点的数据
pcur = pcur->next; // 让pcur指向下一个节点
}打印结果：
我们这里val的类型是int，如果想要保存的数据类型是字符，浮点或者自定义类型，改为该类型即可。
补充说明：
- 链式结构在逻辑上是连续的，在物理结构上不一定连续
- 节点一般是从堆上申请的
- 从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续
二、单链表的实现
我们再清楚了链表的结构后，可以尝试实现以下单链表的增删查改操作。
1. 链表节点结构体代码
typedef int Listdatatype;
typedef struct SListNode
{
Listdatatype data;
struct SListNode* next;
}Listnode;2. 链表的增加
为了方便增加链表节点，我们将申请空间这个操作包装为一个函数：
Listnode* Listapply(Listdatatype x)
{
Listnode* newnode = (Listnode*)malloc(sizeof(Listnode));
if (newnode == NULL) // 如果申请失败，报错并结束程序
{
perror("malloc");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
下面是尾删代码：
// 为了能够修改头指针的内容，需要传址调用，这里传参是二级指针接受
void Listpushback(Listnode** pphead, Listdatatype x)
{
assert(pphead);
Listnode* newnode = Listapply(x);
if (*pphead == NULL) // 头指针为空，令头指针指向新建的第一个节点
{
*pphead = newnode;
}
else
{
Listnode* pcur = *pphead;
while (pcur->next) // 找到链表的最后一个节点
{
pcur = pcur->next;
}
pcur->next = newnode;
}
}再有了尾增代码，接下来的头增代码很容易
void Listpushfront(Listnode** pphead, Listdatatype x)
{
assert(pphead);
Listnode* newnode = Listapply(x);
newnode->next = *pphead;
*pphead = newnode;
}3. 链表的删除
尾删：
void Listpopback(Listnode** pphead)
{
assert(pphead);
assert(*pphead);
Listnode* pcur = *pphead;
if (pcur->next == NULL) // 链表中只有一个节点，删除该节点同时让头指针指向空
{
free(pcur);
pcur = NULL;
*pphead = NULL;
}
else
{
Listnode* prev = *pphead;
while (pcur->next) // 找到最后一个节点，同时让prev指向倒数第二个节点
{
prev = pcur;
pcur = pcur->next;
}
free(pcur);
pcur = NULL;
prev->next = NULL; // 让prev指向的节点的next指向空
}
}头删：
void Listpopfront(Listnode** pphead)
{
assert(pphead);
assert(*pphead);
Listnode* pcur = *pphead;
if (pcur->next == NULL) // 链表中只有一个节点，删除该节点同时让头指针指向空
{
free(pcur);
pcur = NULL;
*pphead = NULL;
}
else
{
pcur = pcur->next;
free(*pphead);
*pphead = pcur; // 修改头指针的指向
}
}最难的增删结束后，我们来看看简单点的查找和修改
Listnode* Listfind(Listnode* phead, Listdatatype x)
{
assert(phead);
Listnode* pcur = phead;
while (pcur)
{
if (pcur->data == x) // 找到该节点，返回该节点地址
return pcur;
pcur = pcur->next;
}
return NULL; // 没有找到返回空
}void Listchange(Listnode* pos, Listdatatype x)
{
assert(pos);
pos->data = x;
}最后就剩下了链表的销毁了
void Listdestory(Listnode** pphead)
{
assert(pphead);
Listnode* pcur = *pphead;
Listnode* next = pcur;
while (pcur)
{
next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}
三、链表的分类
链表的结构非常多样，以下情况组合起来就有8种（2*2*2）链表结构：
链表说明：
1、单向或者双向
2、带头或者不带头
3、循环或者不循环
虽然有这么多的链表的结构，但是我们实际中最常用的还是两种结构：单链表和双向带头循环链表
1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道。
总结
这篇博客讲述了链表的概念和结构，对链表的最简单的结构——单链表，实现了它的增删查改，最后补充了链表的分类，让大家对链表有个整体了解。