前言
在上一节中我们学习了单链表，但是我们发现单链表有如下缺陷：
1、在尾部插入、删除数据时间复杂度为O(N)，效率低；
2、在pos位置前插入、删除数据时间复杂度为O(N)，效率低；
3、进行插入、删除数据时因为有可能改变头节点，所以需要传递二级指针，不易理解；
基于单链表的这些缺陷，我们设计出了带头双向循环链表，带头循环实现链表能够完美的解决顺序表所存在的缺陷。
一、什么是带头双向循环链表
在单链表部分我们已经介绍了链表的几种结构：
带头/不带头 – 是否具有哨兵位头结点，该节点不用于存储有效数据，对链表进行插入删除操作时也不会影响该节点；
双向/单向 – 链表的节点中是否增加了一个节点指针，该指针存储的是前一个节点的地址；
循环/不循环 – 链表的尾结点是否存储了头结点的地址，链表的头结点是否存储了尾结点的地址 ；
所以带头双向链表是指：具有哨兵位头结点、每个节点中都存储了后一个节点和前一个节点的地址、头结点存储了尾结点的地址、尾结点存储了头结点地址，这样的一种结构的链表。
可以看出，带头双向循环链表是结构最复杂的一种链表，但是它复杂的结构所带来的优势就是它管理数据非常简单，效率非常高；下面我们用C语言实现一个带头双向循环链表，以此来感受它的魅力。
二、带头双向循环链表的实现
1、结构的定义
相比于单链表，双向链表需要增加一个结构体指针prev，用来存放前一个节点的地址。
//结构和符号的定义 typedef int LTDataType; typedef struct ListNode { LTDataType data; //用于存放数据 struct ListNode* prev; //用于存放下一个节点的地址 struct ListNode* next; //用于存放上一个节点的地址 }LTNode;
2、链表的初始化
和单链表不同，由于单链表最开始是没有节点的，所以我们定义一个指向NULL的节点指针即可；但是带头链表不同，我们需要在初始化函数中开辟一个哨兵位头结点，此节点不用于存储有效数据；
另外，由于我们的链表是循环的，所以最开始我们需要让头结点的prev和next指向自己；
最后，为了不使用二级指针，我们把 Init 函数的返回值设置为结构体指针类型
//初始化双链表 LTNode* ListInit() { //创建哨兵位头结点 LTNode* guard = (LTNode*)malloc(sizeof(struct ListNode)); if (guard == NULL) { perror("malloc fail"); return NULL; } //让双链表具有双向循环结构 guard->prev = guard; guard->next = guard; return guard; }
3、开辟新节点
//开辟新节点 LTNode* BuyLTNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(struct ListNode)); if (newnode == NULL) { perror("malloc fail"); return NULL; } newnode->data = x; newnode->prev = NULL; newnode->next = NULL; return newnode; }
4、在头部插入数据
由于我们的链表是带头的，插入数据始终都不会改变头结点，所以这里我们传递一级指针即可；同时，phead 不可能为空，所以这里我们断言一下。
//在头部插入数据 void ListPushFront(LTNode* phead, LTDataType x) { assert(phead); //因为链表是带头的，所以phead不可能为空 LTNode* newnode = BuyLTNode(x); LTNode* first = phead->next; //记录第一个节点 //改变链接关系（当链表中没有节点，即只有一个头时，下面逻辑也正常） phead->next = newnode; newnode->prev = phead; newnode->next = first; first->prev = newnode; }
5、在尾部插入数据
在这里我们双向循环链表的优势就体现出来了，对于单链表来说，它只能通过遍历链表来找到链表的尾，然后把新节点链接在链表的尾部。
而对于我们的双向循环链表来说，我们可以直接通过 phead->prev 找到尾，然后链接新节点，把时间效率提高到了 O(1)。
//在尾部插入数据 void ListPushBack(LTNode* phead, LTDataType x) { LTNode* newnode = BuyLTNode(x); //找尾：头结点的prev指向链表的尾 LTNode* tail = phead->prev; //修改链接关系(当链表中没有节点时逻辑也成立） phead->prev = newnode; newnode->next = phead; newnode->prev = tail; tail->next = newnode; }
6、查找数据
//查找数据 LTNode* ListFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; //遍历链表，找到返回数据所在节点的地址 while (cur != phead) { if (cur->data == x) return cur; cur = cur->next; } //找不到就返回NULL return NULL; }
7、在pos位置之前插入数据
由于我们的链表是双向的，我们可以直接通过 pos->prev 来找到前一个节点，然后把新节点链接到前一个节点的后面，时间复杂度从单链表的O(N)提高到了 O(1)；
同时，我们的头插和尾插函数还可以直接调用 Insert 函数，不需要单独实现，因为在头部插入数据相当于第一个节点前面插入元素，在尾部插入数据相当于头结点前面插入元素。
//在pos位置之前插入数据 void ListInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = BuyLTNode(x); //找pos的前一个节点 LTNode* prev = pos->prev; //修改链接关系（当pos为第一个节点/最后一个节点时逻辑也成立） //ps：头插和尾插可以通过直接调用此函数来完成 prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; }
//在头部插入数据 void ListPushFront(LTNode* phead, LTDataType x) { assert(phead); ListInsert(phead->next, x); //相当于第一个节点前面插入元素 }
//在尾部插入数据 void ListPushBack(LTNode* phead, LTDataType x) { assert(phead); ListInsert(phead, x); //相当于头结点前面插入元素 }
8、判断链表是否为空
//判断链表是否为空 bool IsEmpty(LTNode* phead) { assert(phead); return phead == phead->next; //当链表中只剩下头结点时链表为空，返回true }
9、在头部删除数据
这里我们需要判断链表是否为空，如果为空继续删除元素就报错。
//在头部删除数据 void ListPopFront(LTNode* phead) { assert(phead); assert(!IsEmpty(phead)); //删空时继续删除报错 //记录第一个节点的下一个节点 LTNode* second = phead->next->next; //释放第一个节点 free(phead->next); //修改链接关系 phead->next = second; second->prev = phead; }
10、在尾部删除数据
//在尾部删除数据 void ListPopBack(LTNode* phead) { assert(phead); assert(!IsEmpty(phead)); //删空时继续删除报错 //记录尾结点的上一个节点 LTNode* prev = phead->prev->prev; //释放尾结点 free(phead->prev); //修改链接关系 phead->prev = prev; prev->next = phead; }
