前言
名言：我可以接收失败，但我不能接收放弃
我们知道对于链表来说是有八种类型，但是我们在实际过程中最常用的二种结构：
无头单向非循环链表
带头双向循环链表
其中在上篇博客我们已经了解过无头单向非循环链表是怎么实现的，下面我们继续来实现带头双向循环链表。
一 认识带头双向循环链表
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都
是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带
来很多优势，实现反而简单了，后面我们代码实现了就知道了。
二实现带头双向循环链表
在实现带头双向循环链表过程中，我们要特别注意分文件，完成链表功能的实现。
下面我们分为三个文件实现：
1 SList.h
在该文件中我们完成，单表的类型定义，接口函数的声明，引用的头文件。
2 SList.c
完成双向链表表接口函数的实现
3 Test.c
主函数，测试顺序表各接口的功能
下面我们分文件为大家讲解
三实现List.h
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> //带头的双向+循环的链表 typedef int LTDataType; typedef struct ListNode { LTDataType data; struct ListNode* prev; struct ListNode* next; }LTNode; //初始化链表 LTNode* ListInit(); //尾插 void ListPushBack(LTNode* phead, LTDataType x); //头插 void ListPushFront(LTNode* phead, LTDataType x); //打印 void ListPrint(LTNode* phead); //尾删 void ListPopBack(LTNode* phead); //头删 void ListPopFront(LTNode* phead); //求链表长度 size_t ListSize(LTNode* phead); //查找 LTNode* ListFind(LTNode* phead, LTDataType x); // 双向链表在pos的前面进行插入 void ListInsert(LTNode* pos, LTDataType x); // 双向链表删除pos位置的节点 void ListErase(LTNode* pos); //销毁 void ListDestory(LTNode* phead);
在这个文件，我们要特别注意对双向循环链表结构体的定义，他不同于单链表仅仅只有一个指针。
//带头的双向+循环的链表 typedef int LTDataType; typedef struct ListNode { LTDataType data; struct ListNode* prev; struct ListNode* next; }LTNode;
prev指针指向前一个节点
next指向下个节点
四 实现List.c
在这里我们要完成各类函数功能的实现.
实现我们要先实现对链表的初始化
1 初始化链表
//初始化链表 LTNode* ListInit() { //为哨兵头申请一个空间 LTNode* guard = (LTNode*)malloc(sizeof(LTNode)); //判断申请空间是否成功 if (guard == NULL) { perror("malloc fail"); exit(-1);//申请失败，直接结束程序 } //开始时哨兵头和尾都指向guard guard->next = guard; guard->prev = guard; return guard;
在这里我们注意区于单链表初始化时，我们要实现一个哨兵位的头节点 ，这个节点在初始时指向它自身构成循环。
我们有对链表的初始化，那我们为了能够插入数据还应该能够申请新的节点空间。
2 申请新的节点
LTNode* BuySLTNode(LTDataType x) { LTNode* newNode = (LTNode*)malloc(sizeof(LTNode)); if (newNode == NULL) { perror("maalloc fail"); exit(-1); } newNode->data = x; newNode->next = NULL; newNode->prev = NULL; return newNode; }
对于这个新节点来说，我们要注意的是在下面如何讲链表中节点连接起来构成循环。
下面我们来实现链表的尾插
3 尾插
void ListPushBack(LTNode* phead, LTDataType x) { assert(phead); //申请新的节点 LTNode* newNode = BuySLTNode(x); LTNode* tail = phead->prev;//尾指针 //老节点的尾与和新节的头进行双向连接 tail->next = newNode; newNode->prev = tail; //哨兵位的头与和新节的尾进行双向连接 newNode->next = phead; phead->prev = newNode; }
对于单链表的尾插来说，带头双向循环链的尾插简单许多，因为我们这里就不要在判断链表我否为NULL和找尾这二件事情了。
4 头插
这里的头插和尾插一样简单，实现过程我们来看代码。
//头插 void ListPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; //申请新的节点 LTNode* newNode = BuySLTNode(x); newNode->next = cur; cur->prev = newNode; phead->next = newNode; newNode->prev = phead; }
为了更好从测试头插和尾插，我们还要实现对链表的打印。
//打印 void ListPrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next; printf("phead<=>"); while (cur!= phead) { printf("%d<=>", cur->data); cur = cur->next; } }
在单链表中我们是通过直接遍历链表，从而打印。但是我们怎么就会遇到一个问题，但指针向最后一个节点时，又会回到phead节点处，这样就会出现死循环的情况，那么我们可以从存储数据的第1个节点开始遍历，指向phead时结束。
下面我们来测试函数的功能是否能够实现。
可以看到是实现了的，那么我们就可以继续实现下个函数的功能，要养成每写写完一个函数的功能我们都应该去跑一下，看能否实现，这样我们在代码出现问题的时就能快速定位快速解决。
5 头删和尾插
尾删
//尾删 void ListPopBack(LTNode* phead) { assert(phead); assert(!ListEmpty(phead));//链表不为空 LTNode* tail = phead->prev;//尾指针 LTNode*prev = tail->prev;//指向前一个节点 //重新连接节点之间的关系 prev->next = phead; phead->prev = prev; free(tail); }
这里我们要这注意，在删除时，我们要判断链表是否存有数据，没有就不能删除，避免出现野指针。
//判断链表是否为空 bool ListEmpty(LTNode* phead) { assert(phead); return phead->next == phead; }
这里我们有个函数来实现即可。
头删
//头删 void ListPopFront(LTNode* phead) { assert(phead); assert(!ListEmpty(phead));//链表不为空 LTNode* cur = phead->next; LTNode* tail = cur->next; tail->prev = phead; phead->next = tail; free(cur); }
下面我们继续来测试函数的功能：
6 求链表长度
//求链表长度 size_t ListSize(LTNode* phead) { assert(phead); LTNode* cur = phead->next; size_t len = 0; while (cur != phead) { ++len; cur = cur->next; } return len; }
有时候我们需要知道链表有多长，所以我们写个函数来实现它
测试
7 查找pos,在pos位置实现插入和删除、
查找
//查找 LTNode* ListFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) return cur; cur = cur->next; } return NULL; }
当找到了就返回指向X的指针，没有就返回NULL
在pos之前插入
//在pos之前插入 void ListInsert(LTNode* pos, LTDataType x) { assert(pos); //申请新的节点 LTNode* newNode = BuySLTNode(x); LTNode* first = pos;//指向pos节点 LTNode* second = pos->prev;//指向pos的前一个节点 first->prev = newNode; newNode->next = first; second->next = newNode; newNode->prev = second; }
这里只要注意链接关系就不会有大的问题。
双向链表删除pos位置的节点
void ListErase(LTNode* pos) { assert(pos); LTNode* first = pos->next;//指向pos下个节点 LTNode* second = pos->prev;//指向pos的前一个节点 first->prev = second; second->next = first; free(pos);//删除pos }
其实这里的写法多样，但我推荐用本文中的写法，这样可以避免因为链接顺序有问题而出错。
测试
最后实现链表的销毁
8 销毁链表
//销毁 void ListDestory(LTNode* phead) { assert(phead); LTNode* des = phead->next; while (des != phead) { LTNode* cur = des->next; free(des); des = cur; } free(phead); }
这里我们要注意：这里的销毁头节点的空间，但phead其实仍然是指向这里的，所以我们在销毁后，要手动将链表置空。
测试
五 链表和顺序表的对比
下面我们对链表和顺序表对比一下：
不同点 |
顺序表 |
链表 |
存储空间上 |
物理上一定连续 |
逻辑上连续，但物理上不一定 连续 |
随机访问 |
支持O(1) |
不支持：O(N) |
任意位置插入或者删除 元素 |
可能需要搬移元素，效率低 O(N) |
只需修改指针指向 |
插入 |
动态顺序表，空间不够时需要 扩容 |
没有容量的概念 |
应用场景 |
元素高效存储+频繁访问 |
任意位置插入和删除频繁 |
缓存利用率 |
高 |
低 |
显示详细信息
