手撕数据结构 —— 单链表（C语言讲解）
目录
1.为什么要有链表
2.什么是链表
3.链表的分类
4.无头单向非循环链表的实现
SList.h中接口总览
具体实现
链表节点的定义
打印链表
申请结点
尾插
头插
尾删
头删
查找
在pos位置之前插入
在pos位置之后插入
删除pos位置
删除pos位置之后的值
5.完整代码附录
1.为什么要有链表
如果你学习过顺序表的话，应该清楚顺序表的缺点，如果你并不了解顺序表的话，推荐阅读一下这篇文章——手撕数据结构——顺序表（C语言讲解）
我们先来简单回顾一下顺序表，顺序表是在连续的内存空间上按顺序存储数据元素。
顺序表的优点：
- 顺序表支持下标的随机访问和修改，并且时间复杂度是O(1)，效率高。
- 顺序表在尾部进行插入和删除效率高，时间复杂度是O(1)。
顺序表的缺点：
- 头部和中部进行插入和删除效率都不高，时间复杂度是O(N)。
- 动态顺序表扩容有一定消耗，尤其是动态扩容（需要开辟新空间，拷贝数据，释放旧空间）
- 扩容造成的空间浪费（一般扩容是2倍扩容，假如容量从1000扩容到2000，但是我们只需要插入5个数据，就会浪费995个空间）
针对顺序表的缺点，有人设计出了另一种数据结构 —— 链表。
2.什么是链表
链表是一种利用不连续的内存空间存储数据元素的数据结构，并且元素之间可以不按顺序进行存储。
正是因为链表不按顺序存储，要想找到下一个数据就需要记录下一个数据的地址，因此，链表中的数据是包含在一个结构体中，我们通常称这个结构体变量为结点。最后一个结点没有下一个结点，就指向空。
链表的特点是按需申请和释放。
链表逻辑示意图如下：
需要注意的是：
- 我们申请结点的时候，一般是使用动态内存管理的函数申请内存空间（malloc、realloc），这些函数是从堆上申请空间的。
- 从堆上申请的空间，是按照一定的策略来分配的，这取决于操作系统，因此，两次申请的空间可能连续，也可能不连续。
- 链表在逻辑结构上是连续的，在物理上结构上不一定连续，这取决于系统动态分配内存的位置。
3.链表的分类
链表大致可以分为这几类：单向还是双向、带不带头、循环还是非循环。
单向 or 双向：
带头 or 不带头：
循环 or 非循环：
通过数学知识，我们可以知道 2*2*2 = 8，也就是说，不同的分类可以组合出八种链表。 在众多的链表中，我们重点学习无头单向非循环链表和带头双向循环链表。
无头单向非循环链表：也叫单链表，该链表结构简单，一般不会单独用来存储数据，而是用来作为其他数据结构的子结构。例如：哈希桶、图的邻接表……
带头双向循环链表：该链表是结构最复杂的链表，一般用来单独存储数据，实际中使用的链表，都是带头双向循环链表。
4.单链表的实现
说明一下：
实现链表的时候，主要实现无头单向非循环链表（单链表）和带头双向循环链表，本篇文章中只实现无头单向非循环链表（单链表）；带头双向循环链表的实现在下一篇文章中呈现。
实现链表我们定义两个文件，分别是SList.h和SList.c，SList.h文件用来存放声明，SList.c文件用来存放定义。
SList.h中接口总览
具体实现
链表节点的定义
链表是由一个个动态申请的结点构成的，因此，我们要实现链表的第一件事就是先定义结点。链表的结点有两个成员，分别是数据域和指针域。
- 数据域用来存放数据。
- 指针域用来存放下一个结点的地址。
代码如下所示：
打印链表
打印链表只需要知道链表的起始结点即可，创建一个临时变量作为phead的替身，每次打印完当前结点之后，cur就往后走。直到cur为空，表示没有元素了。
- 注意：指针是可以作为逻辑条件判断的。
申请结点
结点的申请需要使用malloc函数，注意申请的类型是结点的类型，也就是结构体类型。
- 结点申请成功之后，我们将数据域赋值为x，将指针域赋值为NULL。
尾插
尾插数据时，直接链接上去即可，但是，我们要考虑链表是否为空：
- 如果链表为空，我们需要改变的是结构体的指针，需要传递二级指针。
- 如果链表不为空，我们需要增加结点，使用结构体指针即可。（不同的结构体指针可以指向同一个结点，并操控同一个结点）
头插
进行头插操作，我们需要改变的也是结构体的指针，所以也需要传递二级指针。
- 头插对于链表是否为空的情况处理是一样的。
尾删
进行尾部删除时需要考虑三种情况：
- 链表为空：如果链表为空，不能删除。
- 链表只有一个结点：如果链表只有一个结点，我们需要改变结构体指针，这也是为什么传递二级指针的原因。
- 链表有一个以上的结点：此时，我们进行尾删时，只需要改变结构体，使用一级指针即可。
头删
头删需要判断链表是否为空，改变的也是结构体指针，所以也需要传递二级指针。
- 头删只需要释放第一个节点，并改变pphead的值即可。
查找
遍历查找即可，找到返回对应结点的指针，没找到返回NULL。
- 查找并不改变结构体指针，传递一级指针即可。
在pos位置之前插入
在pos位置之前插入需要记录pos的上一个位置。
该接口需要考虑三种情况：
- 首先，链表不能为空，因为我们要在指定位置之前插入，如果链表为空，就不能指定位置了。
- 在第一个结点前插入，这不就是头插吗？复用头插即可。
- 在其他地方插入，链接顺序需要从后往前进行，并且还需要提前保存pos位置的上一个位置。
在pos位置之后插入
在pos位置之后插入，不需要记录上一个位置的情况，并且，也不需要判断pos的位置情况，因为，不管pos在哪里，都是一样的操作。
删除pos位置
删除pos位置和在pos位置之前插入一样，需要记录pos位置的上一个位置，需要分三种情况讨论：
- 删除的时候，链表不能为空，删除位置不能为空。
- 删除位置如果是第一个位置，直接复用头删即可。
- 删除其他位置，需要记录上一个位置。
删除pos位置之后的值
删除pos位置之后的值不需要记录pos的上一个位置，但是需要注意不能删除尾结点，因为尾结点没有下一个结点。
5.完整代码附录
SList.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode //定义结点
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead); //打印链表
SLTNode* BuySListNode(SLTDataType x); //申请结点
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之前插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x); //在pos之后插入x
void SLTErase(SLTNode** pphead, SLTNode* pos); //删除pos位置的元素
void SLTEraseAfter(SLTNode* pos); //删除pos的后一个位置SList.c
#include"SList.h"
// 打印链表
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
//while (cur != NULL)
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
// 申请结点
SLTNode* BuySListNode(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 = BuySListNode(x);
if (*pphead == NULL)
{
// 改变的结构体的指针，所以要用二级指针
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
// 改变的结构体，用结构体的指针即可
tail->next = newnode;
}
}
// 头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
// 尾删
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* tail = *pphead;
while (tail->next->next)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
// 头删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* newhead = (*pphead)->next;
free(*pphead);
*pphead = newhead;
}
// 查找元素
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
//在pos位置之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
// 在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySListNode(x);
pos->next = newnode;
newnode->next = pos->next;
}
// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
// 删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
// 检查pos是否是尾节点
assert(pos->next);
SLTNode* posNext = pos->next;
pos->next = posNext->next;
free(posNext);
posNext = NULL;
}