书接上回，本节讲解数据结构双向链表，链表和顺序表的特点对比，顺便解释了一下什么是CPU缓存和内存碎片。
一，双向链表的维护与实现
0，简单介绍
为了方便找到最后一个节点，双向链表通常是循环的。前面讲到，不循环的链表是以空指针(NULL)为停止信号的，而循环链表怎么知道什么时候遍历完呢，索性创建一个哨兵位作为一个是停止信号吧。现在的目的就很明确啦，我们需要实现一个，双向循环带哨兵位的链表，如下图：
//存储在链表中的数据的类型
typedef int DCLDatatype;
//定义每个节点的结构
typedef struct DCListNode
{
DCLDatatype data; //存放数据
struct DCListNode* prev; //记录前一个节点的地址
struct DCListNode* next; //记录后一个节点的地址
}Node; //给节点typedef一个简单的名字——结构体定义——
注意：与上节单链表不同，本次双向循环链表的维护实现，主要通过节点地址来完成。查找数据返回的是结点指针，指定插入和指定删除的接口也都是节点指针。
名词介绍：
DCListNode：Double Circular List Node 双向循环链表的节点
DCLDatatype：Double Circular List Data Type 双向循环链表的中存放的数据类型
pcur：position current 指向当前节点的指针，通常用来遍历链表
pnew: position new 新生成的节点
prev: position previos 前驱指针，通常是pos的前一个指针
pos：position 指针，通常用于函数传参，需要进行链表操作如（插入，删除……）的指针。
1，准备工作
1）创建头文件和源文件
头文件：DCList.h（存放结构体定义，函数声明）
源文件：DCList.c（实现头文件中的函数接口），test.c（对接口进行测试）
2）定义节点结构体
3）维护双向链表的头文件的包含和函数声明
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//存储在链表中的数据的类型
typedef int DCLDatatype;
//定义每个节点的结构
typedef struct DCListNode
{
DCLDatatype data; //存放数据
struct DCListNode* prev; //记录前一个节点的地址
struct DCListNode* next; //记录后一个节点的地址
}Node; //给节点typedef一个简单的名字
//链表初始化
Node* DCListInit();
//链表销毁
void DCListDistory(Node* phead);
//链表打印
void DCListPrint(Node* phead);
//按下标查找
Node* DCListFindInder(Node* phead, int n);
//指定位置插入
void DCListInsert(Node* pos, DCLDatatype x);
//指定位置删除
void DCListDel(Node* pos);
//头插
void DCListPushFront(Node* phead, DCLDatatype x);
//尾插
void DCListPushBack(Node* phead, DCLDatatype x);
//头删
void DCListDelFront(Node* phead);
//尾删
void DCListDelBack(Node* phead);2，链表初始化
//链表初始化
Node* DCListInit()
返回值：哨兵位的地址创建一个空节点作为哨兵位，让这个哨兵位自己指向自己
开辟空间，并放入数据
Node* BuyNode(DCLDatatype x)
{
申请空间并检查是否申请成功
Node* pnew = (Node*)malloc(sizeof(Node));
if (pnew == NULL)
{
perror("BuyNode::malloc");
exit(1);
}
初始化节点数据和指向
pnew->data = x;
pnew->next = NULL;
pnew->prev = NULL;
返回新节点的地址
return pnew;
}
3，链表销毁
//链表销毁
void DCListDistory(Node* phead);
phead:头指针，指向哨兵位遍历链表，销毁全部节点。
其中有一个要注意的细节，我们来看看，似乎与单链表类似，让一个指针next保存下一个位置的节点，另一个指针del释放当前节点。但我要说的不是这个，是循环停止的条件，假如说我们初始让哨兵位的下一个节点开始遍历，循环停止的条件为del==phead结束，此时哨兵位还没有被释放，已经跳出循环了。那么就需要我们在跳出循环后手动释放哨兵位。如下：
//链表销毁
void DCListDistory(Node* phead)
{
assert(phead);//检查空指针
遍历链表，释放每一个节点
Node* del = phead->next;
Node* next = del;
while (del != phead)
{如果del == phead，则遍历完成
next = next->next; 让next往前走，保存下一个节点的位置
free(del); 释放del节点
del = next; 将下一个节点的值赋给del
}
手动释放哨兵位
free(phead);
phead = NULL;
}那有没有什么办法可以优雅的解决这个问题呢？有的兄弟，有的。我们，我们上来就释放哨兵位，让del和next往后走，本质上的需求是先让他先执行循环再判断条件， do while循环就可以完全解决这个问题，下面来看我操作：
//链表销毁
void DCListDistory(Node* phead)
{
assert(phead);//检查空指针
//遍历链表，释放每一个节点
Node* del = phead;
Node* next = del;
do
{ 上来就释放哨兵位
next = next->next;//让next往前走，保存下一个节点的位置
free(del); //释放del节点
del = next; //将下一个节点的值赋给del
} while (del != phead);
del = next = phead = NULL;
} 我们来看看特殊情况，如果给空链表会不会有问题呢，这时哨兵的下一个节点指向自己(del==phead)，之后进来循环，然后判断条件，del==phead直接跳出循环，不会有问题，完美！
4，链表打印
//链表打印
void DCListPrint(Node* phead);
phead:头指针遍历链表，然后打印，没什么好说的，要是看不懂下面注释的话，可以看看这篇文章[ 单链表 ]，这里就直接给代码了：
//链表打印
void DCListPrint(Node* phead)
{
assert(phead);//检查空指针
//遍历链表，打印数据
Node* pcur = phead->next;//第一个是哨兵位，从第二个开始
while (pcur != phead) //由于链表是成环的
{ //当发现pcur==phead
//说明已经遍历了一圈了
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}5，指定下标获取节点
//按下标查找
Node* DCListFindInder(Node* phead, int n);
phead:头指针
n:下标序数
返回值:下标n节点对应的地址同样是遍历链表，这里要注意越界访问的问题，利用循环检查一遍节点是否走到哨兵位（遍历完链表），如果走到哨兵位了就跳出循环，让下面断言报错，或者说直接返回空指针，这里就直接给代码了：
//按下标查找
Node* DCListFindInder(Node* phead, int n)
{
assert(phead);//检查空指针
assert(n >= 0);//检查下标的合法性
//遍历链表，找到下标为n的节点
Node* pcur = phead->next;//第一个是哨兵位，从第二个开始
for (int j = 0; j < n && pcur != phead; j++)
{//防止二次遍历，增加循环判定条件pcur != phead(遍历一圈跳出循环)
pcur = pcur->next;
}
if (pcur == phead)//如果是因pcur == phead跳出循环
{ //说明给的下标过大，返回空指针
return NULL;
}
//没问题的话，返回下标对应的地址
return pcur;
}6，在pos后插入节点
//指定之后位置插入
void DCListInsert(Node* pos, DCLDatatype x);
pos:指定节点
x:要插入的数据在上节讲到过，插入节点时要先改变新生成节点的指向，这里先让pnew指向前一个节点和后一个节点，如下：在0x9C1F3E5A后插入数据6
这里再教你们一个焚诀，先改变离pos远的节点指针，最后改变pos节点本身的指针，也就是说先改变新生成节点的下一个节点的指向，再改变前一个pos节点的指向，下面看我操作：
当然，如果你非要先改变pos节点也可以，因为pnew节点已经记录前后节点的地址了，所有节点都能找到，如下：
但在这里我要说的是什么呢，先改变离pos远的节点，这是好习惯，这样可以保证节点链接丢失的最小化，你看，如果说按照我说的第一种方法来，就有两种方法找到下一个节点：
//指定之后位置插入
void DCListInsert(Node* pos, DCLDatatype x)
{
assert(pos);//检查空指针
//申请新节点
Node* pnew = BuyNode(x);
//先修改新节点的指向
pnew->next = pos->next;
pnew->prev = pos;
//再修改新节点前后节点的指向
pnew->next->prev = pnew; //pnew->next->prev = pnew;
pos->next = pnew; //pnew->prev->next = pnew;
//仅供参考，只是感觉这样替换便于理解
}7，删除pos位置的节点
//指定位置删除
void DCListDel(Node* pos);
pos:删除节点的地址刚才说什么？这不是来了吗，先改变离pos远的节点指针，再改变pos本身的节点指针。如下：
删除
然后再释放节点就完事了
//指定位置删除
void DCListDel(Node* pos)
{
assert(pos); 检查空指针
assert(pos->next != pos);检查链表是否为空
修改前后指针的指向
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
释放pos节点
free(pos);
pos = NULL;
}8，头部尾部插入删除
直接调用写好的接口，就这样吧
//直接使用之前的接口
//头插
void DCListPushFront(Node* phead, DCLDatatype x)
{
assert(phead);//检查空指针
DCListInsert(phead, x);//在哨兵位后插入，即头插
}
//尾插
void DCListPushBack(Node* phead, DCLDatatype x)
{
assert(phead);//检查空指针
DCListInsert(phead->prev, x);//在哨兵位的前一个节点的后面插入
//即最后一个节点，尾插
}
//头删
void DCListDelFront(Node* phead)
{
assert(phead);//检查空指针
assert(phead->next != phead);//检查链表是否为空
DCListDel(phead->next);//删除第一个节点
}
//尾删
void DCListDelBack(Node* phead)
{
assert(phead);//检查空指针
assert(phead->next != phead);//检查链表是否为空
DCListDel(phead->prev);//删除最后一个节点
}
二，顺序表与链表的对比
对比
| 顺序表 | 链表 | |
| 物理存储 | 元素存放在连续内存中 | 节点分散存储，通过指针连接 |
| 随机访问 | 优势：按下标访问 O(1) | 缺点：需要遍历链表 O(n) |
| 算法兼容 | 优势：支持随机访问的算法(像二分查找，快排，矩阵之类的) | 缺点：不支持需要随机访问的算法 |
| 空间分布 | 一般：可能预留容量造成浪费(比如说你要存放501个数据，却开辟了1000个数据的大小) | 劣势：一个节点同时要放数据和下一个节点的指针，需要3倍甚至5倍的内存大小存一个int类型的数据，拉完了。 |
| 内存需求 | 劣势：需要连续大块内存，扩容可能复制搬迁 | 优势：不需要连续内存，按节点分配，较灵活，但会产生大量内存碎片 |
| 扩容代价 | 劣势：动态扩容可能需要转移整块数据O(n) | 优势：按需求来，想扩多少扩多少，无需转移其他数据，但每扩一个都需要单独申请。 |
| CPU缓存 | 优势：连续访问对 CPU 缓存友好，速度快 | 劣势：节点分散，需要不断读取内存 |
一句话总结：
查询多、改少、需随机访问用顺序表
频繁插入删除、大小变化大、不需随机访问用链表
其实在后面学习和现实生产生活中顺序表会用的多一些
有的宝子可能不知道CPU缓存和内存碎片是什么，我在这里详细解释一下：
什么是CPU缓存
CPU 运算非常快，而主内存相对慢很多。如果 CPU 每次都直接去内存取数据，就会经常等内存，非常浪费时间，这时就需要缓存进行数据的存储。
所以现代 CPU 有多级缓存：
L1 Cache：最小、最快，几十 KB
L2 Cache：稍大、也很快，几百 KB 到几 MB
L3 Cache：更大、一般快，几 MB 到几十 MB，
主内存：很大，很慢
硬盘：超大，超级慢
其实你不用管那么多有的没的，只需记住CPU缓存越快越小。CPU 会尽量把接下来可能用到的数据提前放到可快速读取的缓存里。
CPU怎么知道将来会用哪些数据，难道CPU能预测未来吗，那怎么可能。其实CPU也没有那么聪明啦，他只是把用到的数据附近的一整块内存加载到缓存里，因为这附近的数据有很大概率后面会用到。
但是这个链表他不按套路出牌呀， CPU缓存在这载入了半天白载入了，这一个又一个的节点全是散的呀， CPU刚载入数据使用完，发现下一个节点缓存中没有，找内存重新载入，又使用完，发现下一个节点缓存中又没有，又重新载入……如此循环往复，每次找个节点都在内存中读数据，大大拖慢了整体的遍历时间。
而顺序表就不一样了， 数据是连续存储的，你这载入一次后面的全都是有效数据啊，缓存被有效数据塞满了，每次计算完后面的数据直接找缓存要，这速度不直接起飞。就好比拉屎，一次性全拉出来，整个人都通透了。而链表就跟便秘了一样，一次拉一小坨，一次拉一小坨。好像有点恶心了，但其实挺形象的，你细品。
内存碎片
当在堆区中插入多个分散的数据，内存就变得没那么连续了，可能没办法在连续开辟那么多空间了：
这样分开来的一段一段的，我们形象地把它称为内存碎片。
无端联想：上厕所时，有几个可恶的家伙把坑位占了，你和你的好基友只能分开上，或者等他们上完你们再上。
其实内存碎片这个东西没有想象中的影响那么大，现在内存给的都挺大的，而且现在的编译器也挺智能的，扩容只要别太离谱，就没什么大问题。
下节讲栈和队列，十分轻松，篇幅应该不会太长，由于有顺序表做铺垫，实现部分就一笔带过了，主要还是讲性质。
一些废话：
好羡慕那些管的不严的学校，我们每节课都要清人头。老师还很私人，管得老严了，上个思政，看到我写博客直接把我点起来回答问题，前几次随便说几句话糊弄过去了，后面演都不演了，直接抢我手机。兄弟们，一定要支持我啊，这篇博客是我用学分换来的。
下面上封面：侵删
——她想起了来罗德岛之前的日子——
小红车：@大污师！
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/lei_jiale/article/details/169651121
