数据结构：双向循环链表的实现
一.基本功能概述
双向循环链表弥补了单链表的许多不足。
首先，在结构上，它增加了访问前驱的指针prev，这样，访问前一个节点就变得很方便了，其次就是循环链表的头尾是相连的，这样在实现头尾删插的时候，也更加简便了。
双向循环链表的定义与需要实现的功能。
双向循环链表的功能和单链表几乎无异，只是在实现方法上有所不同，头文件的详情如下：
#pragma once #include <stdio.h> #include <assert.h> #include <stdbool.h> #include <stdlib.h> typedef int DoublelistData; typedef struct Doublelist { DoublelistData data; struct Doublelist* next; struct Doublelist* prev; }Dlist; //初始化双链表 Dlist* DlistInit(); //创建新的双链表节点 Dlist* DlistBuyNode(DoublelistData x); //打印双链表 void DlistPrint(Dlist* head); //获取数据x所在的下标 int GetDlistElem(Dlist* head, DoublelistData x); //在下标i处后方插入数据x void DlistInsert(Dlist* head, int i, DoublelistData x); //删除下标为i的位置的节点 void DlistDelete(Dlist* head, int i); //删除第一个数据等于x的节点 void DlistDataDelete(Dlist* head, DoublelistData x); //获取双向链表的有效数据个数 int GetDlistSize(Dlist* head); //销毁双向链表 void DlistDestroy(Dlist** phead); //尾删 void DlistPopBack(Dlist* head); //尾插 void DlistPushBack(Dlist* head, DoublelistData x); //头删 void DlistPopFront(Dlist* head); //头插 void DlistPushFront(Dlist* head, DoublelistData x);二.功能实现
先来说初始化链表。
要初始化链表，首先就需要在堆上创建一个哨兵节点，即我们使用malloc函数，但需要注意的是，对于双向循环链表，即使是单个节点，我们也要使其头尾相连，即：
新节点的prev和next都指向自己。
建立新节点
我们写一个创建新节点的函数方便以后调用。（使用malloc，需要进行返回值检查）
Dlist* DlistBuyNode(DoublelistData x) { Dlist* NewNode = (Dlist*)malloc(sizeof(Dlist)); if (NewNode == NULL) { perror("malloc"); exit(-1); } NewNode->data = x; NewNode->next = NewNode; NewNode->prev = NewNode; return NewNode; }我们在这里约定：哨兵节点的数据部分存储-1。
接下来DlistInit就很好实现了：
初始化链表
Dlist* DlistInit() { Dlist* head = DlistBuyNode(-1); return head; }打印链表
为了后续方便检查和调试，这里我们先把打印链表的功能实现好。
首先，需要知道：循环链表并没有尾部，所以我们不能通过查找尾部NULL来停止打印。这边的方法是通过，判断当前指针是否等于头指针，如果是，就停止打印。
再者，我们的接口传的都是哨兵指针，因此需要断言判空。
需要注意的点就这俩个，具体如下：
void DlistPrint(Dlist* head) { assert(head); Dlist* pcur = head->next; int j = 0; while (pcur != head) { printf("%d[%d]->", pcur->data, j); pcur = pcur->next; j++; } printf("\n"); }这里，为了方便调试，我增加了打印下标的功能。
获取元素下标与节点个数
这两个功能也相对简单，这里不做过多讨论。
int GetDlistElem(Dlist* head, DoublelistData x) { assert(head); Dlist* pcur = head->next; int j = 0; while (pcur != head) { if (pcur->data == x) { return j; } pcur = pcur->next; j++; } printf("节点不存在！\n"); return -1; }int GetDlistSize(Dlist* head) { assert(head); Dlist* pcur = head->next; int size = 0; while (pcur != head) { size++; pcur = pcur->next; } return size; }需要注意的是，我们这里约定-1是无效数据，所以在未找到数据x的情况下将返回值设置为-1,这个可以视情况而调整。
插入数据
这是整个功能的重点，也是难点。在考研408中，关于链表的相关考察经常涉及到节点的插入。
在这里我们定义在i下标位置插入，是插入在其后方。
当然，我们更常见的做法是在前方插入，在下面我们会实现这两种方式。
先来看插入在i后方的代码：
void DlistInsert(Dlist* head, int i, DoublelistData x) { assert(head && i >= -1); Dlist* pcur = head; int j = -1; while (j < i && pcur->next != head) { pcur = pcur->next; j++; } if (j < i) { printf("下标位置超过尾部！\n"); exit(-1); } Dlist* NewNode = DlistBuyNode(x); NewNode->next = pcur->next; NewNode->prev = pcur; pcur->next->prev = NewNode; pcur->next = NewNode; }这里我们使用索引 j 来判断输入的下标 i 是否越界。因为我们将pcur赋值为head---哨兵节点的指针，为保证 j 和pcur的下标对应，我们只能将j初始化为-1。
注意，在上述断言中，我们允许 i = -1 是为了方便后续实现头插功能时，可以直接调用这个接口。
至于while循环的跳出条件是pcur->next != head,而不是pcur == head，是为了后续调用这个接口实现尾插。关于边界情况我们都稍后讨论，先把关键的插入捋清楚。
想要插入数据x，首先先创建这个节点，根据上文，pcur目前下标i位置的节点，而我们要在其后方插入，那第一步先让新节点的后继指向pcur的后一个即：
NewNode->next = pcur->next;再让NewNode的前驱指向位置 i 即pcur：
NewNode->prev = pcur;这时，pcur->next没有被修改，仍然指向pcur的下一个，而非NewNode，所以我们通过pcur->next访问到下一个节点，再将它的前驱prev指向NewNode：
pcur->next->prev = NewNode;最后，我们才能修改pcur的后继，即pcur->next.
再次强调，由于我们访问 i 的下一个节点需要pcur->next，所以它一定是留在最后一个修改的。
当然，如果你事先把i的下一个节点的指针存好了，那就不用考虑这个问题了。
现在我们处理好了一般情况的插入功能，那接下来就要考虑边界情况了，顺便解释一下刚刚没填的坑。
输入错误：i 越界
其实在链表的实际应用中，头尾插入或删除才是常用的，而这些功能一般是实现了一般位置的插入或删除功能后，直接调用这些接口实现的。
比如现在，假如一个链表有4个节点，那么最后一个节点的下标就是 3，我要在尾部插入，按现在的代码直接输入三是没有问题的，j 会在等于 i 时跳出，而pcur自然指向最后一个节点。
但如果，我们输入一个4呢？
虽然双向循环链表的性质会防止越界，但再加上while的循环条件，会直接让这个违规插入操作退化为尾插，使用者不会收到任何错误提醒！所以，我们设置了if判断语句来解决这个问题。
边界情况：尾插
那现在，尾插的代码似乎就很好处理了，我们直接调用之前实现的获取节点个数的接口，获得节点个数size，那么size - 1就是尾部的下标，再输入插入代码中，不就行了吗？
由于 j 被我们初始化为-1，所以即使我们要尾插一个空表，size - 1 = -1，刚好可行！
详情如下：
void DlistPushBack(Dlist* head, DoublelistData x) { assert(head); int size = GetDlistSize(head); DlistInsert(head, size - 1, x); }边界情况：头插
头插的代码就更加显然了。我们直接把-1作为下标传入插入接口，就能实现：
void DlistPushFront(Dlist* head, DoublelistData x) { assert(head); DlistInsert(head, -1, x); }删除节点
删除节点的接口我们定义为删除下标为 i 的节点。
由于链表的所有节点都是通过malloc在堆上创建的，所以删除自然也就是free对应的结构体指针。
这里需要注意的点和刚刚的插入大同小异，也是要注意指向下一个节点的指针不能先被free，否则我们就找不到下一个节点，还会非法访问到已释放内存。
所以我们要么先把pcur->next存起来，要么先让pcur前后的节点连接起来再free，由于大部分考题都是考察后者，故这里我们也采用后者方案。
具体代码如下：
void DlistDelete(Dlist* head, int i) { assert(head && i >= 0); if (head->next == head) { printf("输入空表，删除失败！\n"); exit(-1); } Dlist* pcur = head->next; int j = 0; while (pcur->next != head && j < i) { pcur = pcur->next; j++; } if (j < i) { printf("下标越界，无法执行删除操作！\n"); exit(-1); } pcur->next->prev = pcur->prev; pcur->prev->next = pcur->next; free(pcur); }边界情况：头删与尾删
由于删除功能中，i 越界的情况比较容易处理，这里不做讨论。
我们来看到头删和尾删的实现代码上。这里也是直接调用已有接口，头删就是把参数 i 置为 0 ，尾删便是讲尾部的下标传入，与上述大同小异。
唯一需要注意的就是，我们传入的head实际上是哨兵指针，我们既要assert哨兵本身不能为空，又要assert它是否是指向空链表，即它是否是自循环的。
具体代码如下：
void DlistPopBack(Dlist* head) { assert(head && head->next != head); int size = GetDlistSize(head); DlistDelete(head, size - 1); } void DlistPopFront(Dlist* head) { assert(head); DlistDelete(head, 0); }不过，由于循环链表拥有前驱指针prev，所以要实现尾插，我们也可以直接使用哨兵节点的前驱来访问尾部，从而达到删除效果，这样拥有更高的效率：
void DlistPopBack(Dlist* head) { assert(head && head->next != head); Dlist* del = head->prev; del->prev->next = head; head->prev = del->prev; free(del); }删除x数据节点
我们对这个功能的定义是，删除第一个数据等于x的节点。
刚刚我们实现了获取元素下标的接口，结合删除接口，我们就可以直接实现这个功能：
void DlistDataDelete(Dlist* head, DoublelistData x) { assert(head); int i = GetDlistElem(head, x); DlistDelete(head, i); }销毁链表
这是很多同学会忽略的一个功能。由于链表在堆上建立的，若不进行销毁，就会造成内存泄漏。
销毁链表需要注意的点和删除链表时差不多，我们需要循环遍历每一个节点并free释放它。
但注意：由于哨兵节点也要释放，所以我们需要将参数设置为指向哨兵节点的二级指针，在free完所有节点后，再释放哨兵节点并置空。
再次注意，哨兵指针一定要置空！
void DlistDestroy(Dlist** phead) { assert(phead); Dlist* pcur = (*phead)->next; while (pcur != *phead) { Dlist* next = pcur->next; free(pcur); pcur = next; } free(*phead); *phead = NULL; }总结
链表是非常经典和常用的数据结构，种类多样，经常出现在各种考核中，希望这篇文章能帮助大家学习和巩固相关知识点，也感谢大家积极指正不足之处。