带头双向循环链表的结构
带头双向循环链表的结构如下图：
可以看到，带头双向循环链表是结构最复杂的链表
但是在实际使用链表结构存储数据时，都是使用带头双向循环链表，虽然这个结构有些复杂，但是这样的结构会给我们带来很多优势，实现代码的时候反而简单了
下面我们来实现一下带头双向循环链表
带头双向循环链表的实现
因为这是一个双向链表，所以要在结构体中定义2个结构体类型指针，用来指向节点的前一个结点和后一个结点
所以带头双向循环链表的结构体如下：
typedef int LTDataType; typedef struct ListNode { struct ListNode* prev; struct ListNode* next; LTDataType data; }LTNode;
建立新节点
这里还是使用malloc去建立一个结点，其余的与单链表中建立新节点类似，这里不多说。
LTNode* BuyNewNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }
初始化函数
因为这个结构是包含头节点的，所以要在初始化函数中把头节点定义出来
LTNode* phead = BuyNewNode(-1); 1
因为此时只有头节点一个结点，又因为结构是循环的，所以头节点的下一个结点和上一个节点都是头节点自己
phead->next = phead; phead->prev = phead; 1 2 所以，初始化的代码为： LTNode* LTInit() { LTNode* phead = BuyNewNode(-1); phead->next = phead; phead->prev = phead; return phead; } 1
打印函数
void LTPrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next; printf("<=>head<=>"); while (cur!= phead) { printf("%d<=>", cur->data); cur = cur->next; } printf("\n"); }
判空函数
当只剩头节点一个节点时，链表就为空了，所以当phead->next == phead时，就说明链表为空了
bool LTEmpty(LTNode* phead) { assert(phead); return phead->next == phead; }
尾插函数
尾插函数第一步就是要找尾，在单链表中，想要找到尾就需要遍历一遍链表，效率低耗时
但是在带头双向循环链表中，找到尾很简单，尾节点就是头节点的前一个节点
然后再依次将结点前后链接上即可
void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyNewNode(x); LTNode* tail = phead->prev; tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
头插函数
在实现单链表时，头节点就是头指针指向的结点
在带头双向循环链表中，头节点就是头节点的下一个结点
void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyNewNode(x); LTNode* nex = phead->next; phead->next = newnode; newnode->prev = phead; newnode->next = nex; nex->prev = newnode; }
尾删函数
在单链表中，我们循环需要找到尾节点以及尾节点前面的节点，十分的麻烦
但是在带头双向循环链表中，就没有这样的问题
头节点的prev就是尾节点tail，尾节点的prev就是尾节点的前一个节点tailprev
然后将tailprev当成尾节点链接起来，最后free掉tail
void LTPopBack(LTNode* phead) { assert(phead); assert(!LTEmpty(phead)); LTNode* tail = phead->prev; LTNode* tailprev = tail->prev; tailprev->next = phead; phead->prev = tailprev; free(tail); tail = NULL; }
头删函数
void LTPopFront(LTNode* phead) { assert(phead); assert(!LTEmpty(phead)); LTNode* del = phead->next; LTNode* nex = del->next; phead->next = nex; nex->prev = phead; free(del); del = NULL; }
头删与尾删类似，不多说
查找函数
在单链表中，查找某个节点的循环条件是什么时候遇到空，什么时候结束循环
在带头双向循环链表中，循环条件则是遇到头节点，就结束循环
LTNode* LTFind(LTNode* phead,LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } —————————
