0.引言
我们在学习过顺序表之后，会发现两点不是很优秀的操作：
1.顺序表的头插和中间的插入，头删和中间的删除：
需要不断的覆盖数据，时间复杂度是O(n)，当我们的顺序表存入100w个数据的时候，花费的时间是非常之多的。
2.动态开辟空间：
a. 一般动态开辟的空间都是以2倍的形式开辟，当我们已经开辟了100个空间，并且存满了，此时我们还需要存放5个数据，那么就又需要开辟200个空间了，我们存放5个数据之后，还剩余了195个空间没有放数据，这也就导致了空间的浪费。
b. 而且我们开辟新空间，拷贝数据，释放旧空间还会有一定的消耗。
注意⚠️⚠️⚠️：
我们在申请空间的时候必须要主动给它释放掉，因为申请空间的时候，是在堆上申请的，这段空间不会随着程序的结束而自然释放掉，所以要在我们程序结束之前，主动释放掉这段空间。
那有没有一种结构会很简便呢？即不需要O(n)的时间复杂度，也解决了空间浪费的缺点，答案肯定是有的，就是我们本次要讲解的链表。
1.链表的概念
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的 。也就是说链表的物理结构不连续，但逻辑结构连续。
上面的是什么意思呢？博主用通俗的语言讲一下：
我们先明确一点，链表的元素叫做节点，这里的链表，首先是一个线性表，需要存入数据的，顺序表是通过什么来找到下一个元素的呢？答案是数组下标，而链表是如果找到下一个节点的呢？是指针，链表是通过指针链接起来的。那我们链表主要的结构就出来了，元素和指向下一个元素的指针。如何将它们组合起来呢？就又用到了我们的结构体了。
我们定义一个结构体来表示链表的节点，结构体内部要包括节点的值和指向下一个节点的指针。
首先先了解如下概念
前驱节点：一个节点前面的节点
后继节点：一个节点后面的节点
链表开始的节点称作：头节点
链表末尾的节点称作：尾结点
其余节点称作：中间节点。
指向头节点的指针：头指针
指向尾结点的指针：尾指针
在知道这些之后，我们继续往下读，去了解链表的逻辑模型和物理模型吧！
2.链表的逻辑模型
下图是链表的逻辑模型，黄色的正方形代表的是链表的节点，节点是由结构体组成的，而结构体里面有本节点的值和指向下一个节点的指针。通过图片就把我们上面说的理论形象化了。
从图中看，链表的逻辑模型一定是连续的，链表通过节点组成，节点之间通过指针链接的，是线性的。
3.链表的物理模型
如图：在物理模型中，我们看到每个节点的地址都不是连续的，所以链表的物理模型不是连续的，不是线性的。我们所说物理上的线性是根据每个节点的物理地址来的，如果物理地址是挨着的就是线性，反之就不是。很显然，链表物理模型并不是线性的。
在学习完链表的逻辑模型和物理模型之后，就让我们一起看看链表具体有哪几种呢？
4.链表的分类
4.1 单向链表
单向链表是最简单的链表结构，但是在实现接口的时候却是最鸡肋的，具体实现会在后面提供源代码。
单向链表顾名思义，链表是单向的，1->2->3->4->5->NULL，缺点是某一个节点找不到它的前驱节点，只能找到后继节点，因为是单向的。
4.2 双向链表
这个双向链表就比单向好很多了，通过一个节点可以找到前驱节点，也可以找到后继节点。
4.3 带头单向链表（带哨兵位）
带头单向链表，这个带头是带一个哨兵位，方便咱们的头插和头删。
哨兵位节点不存放元素。
4.4 带头双向链表（带哨兵位）
4.5 循环单链表
4.6 循环双向链表
4.7 带头循环单链表
4.8 带头循环双向链表
这个结构是链表的最优结构，我们会后面的接口实现也提供了这个链表。
5. 单链表的实现（接口实现代码）
5.1 单链表的定义
我们对单链表的定义是看节点需要什么，因为链表的节点是结构体构成的，节点需要什么就往结构体里存放对应的数据类型。
单链表的每个节点需要该节点的值和指向下一个节点的指针
所以我们定义一个结构体，包括 值和指针 。
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;5.3 单链表的动态申请一个节点空间
这个函数是当我们需要往节点里存放值的时候必须经过的一步，在存放值之前，需要malloc一个节点的空间，开辟空间之后再把值放入，这里不要忘了将节点的next置为空，否则就是野指针。
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;
}5.4 单链表的销毁
销毁这里就看创造了多少个节点的空间，挨个销毁就行。但是我们思考一个问题，当销毁了当前空间，那如何找到下一个节点呢？
如图：
如果我们只是释放phead指向的节点，删除之后是无法找到下一个节点的，也就没办法继续释放后面的节点空间，那这里我们就需要一个指针over来指向phead指向的节点的下一个节点。
这里我们就新建个指针over指向的是phead指向的节点的下一个节点，当释放当前节点之后，让phead指向over，over再指向phead指向节点的下一个节点就OK了。
void SLT_Destroy(SLTNode*phead)//销毁
{
while (phead != NULL)
{
SLTNode *over = phead->next;
free(phead);
phead = over;
}
}5.5 单链表的头插头删
头插：
单链表的头插就比顺序表的头插快多了，不再需要覆盖数据，只需要将我们创建的新节点的next指向现在的头节点，再将指向头节点的指针指向新节点。但是需要注意的是我们改的是指针，如果想更改指针，就需要传入指针的地址，也就是用到了我们的二级指针。
头删：
头删只需要删除当前节点，让下一个节点当新的头节点即可，这里需要用assert断言一下，assert函数在<assert.h>这个头文件里，是用来判断括号里的条件是否成立，成立就继续，不成立就报错。
删除头节点之后，还要更新头节点，也需要一个指针 指向要删除的头节点的下一个节点，再将指向原头节点的指针指向新的头节点，这里也是更改指针，所以传入的也是二级指针。
void SLTPushFront(SLTNode** pphead, SLTDataType x) //头插
{
SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void SLTPopFront(SLTNode** pphead) //头删
{
// 空
assert(*pphead);
// 非空
SLTNode* newhead = (*pphead)->next;
free(*pphead);
*pphead = newhead;
}5.6 单链表的尾插尾删
尾插：
尾插这里要分两种情况：
1.没有节点的尾插：
这里的插入的节点就是头节点，需要更改一下指向头节点的指针phead，更改指针就用到二级指针。
2.有节点的尾插：
对于有节点的尾插，我们首先应该找到链表的尾结点，再将尾结点的next指向新节点。
尾删：
尾删分三种情况：
1.链表为空：
这里就需要用assert断言一下，为空就报错。
2.链表只剩一个节点：
当链表只有一个节点的时候，也就是*pphead->next == NULL。改变的就是头节点，因为我们对头节点进行删除，链表就没有节点了，需要置为空，所以头指针就要等于空指针，更改了指针，就用到了二级指针。
3.链表还有两个及以上的节点：
void SLTPushBack(SLTNode** pphead, SLTDataType x) //尾插
{
SLTNode* newnode = BuySListNode(x);
if (*pphead == NULL)
{
// 改变的结构体的指针，所以要用二级指针
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
// 改变的结构体，用结构体的指针即可
tail->next = newnode;
}
}
void SLTPopBack(SLTNode** pphead) //尾删
{
// 1、空
assert(*pphead);
// 2、一个节点
// 3、一个以上节点
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;
}
}5.7 单链表的在pos位置之前的插入
这里需要判断pos所在位置是否是头节点，如果是头节点就是头插；如果不是就正常的在pos位置之前插入就可以了
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)//pos之前插入
{
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;
}
}5.8 单链表的在pos位置之后的插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)//在pos之后插入
{
assert(pos);
SLTNode* newnode = BuySListNode(x);
pos->next = newnode;
newnode->next = pos->next;
}5.9 单链表的删除pos位置的节点
如果pos是头，就需要头删
如果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 = NULL;
}
}5.10 单链表的删除pos位置之后的节点
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
// 检查pos是否是尾节点
assert(pos->next);
SLTNode* posNext = pos->next;
pos->next = posNext->next;
free(posNext);
posNext = NULL;
}5.11 单链表的查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) //查找
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}6.带头双向循环链表的实现（接口实现代码）
6.1 带头双向循环链表的定义
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* prev; //前驱
LTDataType data;
struct ListNode* next; //后继
}ListNode;6.2 带头双向循环链表的初始化
ListNode* ListInit() //初始化链表
{
ListNode *head = (ListNode*) malloc(sizeof (ListNode));
if(head == NULL)
{
perror("初始化开辟空间失败");
exit(-1);
}
head->data = -1;
head->prev = head;
head->next = head;
return head;
}6.3 带头双向循环链表的销毁
void ListDestory(ListNode* pHead) //销毁
{
int len = ListSize(pHead) + 1;
while (len--)
ListPopFront(pHead);
}6.4 带头双向循环链表的打印
void ListPrint(ListNode* phead) //打印
{
assert(phead);
ListNode *phead_next = phead->next;
printf("phead <-> ");
while(phead_next != phead)
{
printf("%d <-> ",phead_next->data);
phead_next = phead_next->next;
}
printf("phead\n");
}6.5 带头双向链表的增加节点
ListNode* BuyListNode(LTDataType x) //增加节点
{
ListNode *newnode = (ListNode*) malloc(sizeof (ListNode));
if(newnode == NULL)
{
perror("增加节点开辟空间失败");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}6.6 带头双向循环链表的在pos之前插入
void ListInsert(ListNode* pos,LTDataType x)//在pos位置之前插入
{
assert(pos);
ListNode *newnode = BuyListNode(x);
ListNode *pos_prev = pos->prev;
pos_prev->next = newnode;
newnode->prev = pos_prev;
newnode->next = pos;
pos->prev = newnode;
}6.7 带头双向循环链表删除pos位置
void ListErase(ListNode* pos)//删除pos位置的节点
{
assert(pos);
ListNode *pos_next = pos->next;
ListNode *pos_prev = pos->prev;
pos_prev->next = pos_next;
pos_next->prev = pos_prev;
free(pos);
}6.8 带头双向循环链表的尾插尾删
void ListPushBack(ListNode* phead,LTDataType x)//尾插
{
assert(phead);
ListInsert(phead,x);
}
void ListPopBack(ListNode* phead)//尾删
{
assert(phead);
ListErase(phead->prev);
}6.9 带头双向循环链表的头插头删
void ListPushFront(ListNode* phead,LTDataType x)//头插
{
assert(phead);
ListInsert(phead->next,x);
}
void ListPopFront(ListNode* phead)//头删
{
assert(phead);
ListErase(phead->next);
}6.10 带头双向循环链表的长度求解
int ListSize(ListNode* phead)//求链表的长度
{
assert(phead);
int len = 0;
ListNode *phead_next = phead->next;
while(phead != phead_next)
{
len++;
phead_next = phead_next->next;
}
return len;
}6.11 带头双向循环链表的寻找某一节点
ListNode*ListFind(ListNode* phead, LTDataType num)//寻找某一个节点
{
assert(phead);
ListNode *find = phead->next;
while(find != phead)
{
if(find->data == num)
{
return find;
}
find = find->next;
}
return NULL;
}7. 顺序表和链表的区别
| 不同点 | 顺序表 | 链表 |
|---|---|---|
| 存储空间上 |
物理上一定连续 | 逻辑一定连续，物理不一定 |
| 任意位置插入或者删除 元素 |
需要覆盖数据 | 通过指针就能找到 |
| 插入 文章来源：https://www.toymoban.com/news/detail-714999.html |
动态顺序表需要扩容 | 没有容量概念，需要一个给一个 |
| 缓存利用率文章来源地址https://www.toymoban.com/news/detail-714999.html |
高 | 低 |
到了这里，关于数据结构之手撕链表（讲解➕源代码）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
