概述

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

双向循环链表含有一个头节点（哨兵位），含有两个指针域，next，prev，分别指向节点的后继和前驱。需要注意的是，头节点的prev指向尾节点，尾节点的next指向头节点

看着复杂，实际操作起来很简单。

初始化

和单链表初始化差不多，无非就是多了一个prev指针

LTNode* CreateLTNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->val = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}LTNode* LTInit()
{LTNode* phead = CreateLTNode(-1);phead->next = phead;phead->prev = phead;return phead;
}

销毁

遍历链表，并定义一个next 来保存 cur 的下一个节点，在链表都free 完后，再销毁头节点；

注意：应该是从头节点的 next 开始遍历。

void ListNodedestroy(LNode* phead)
{assert(phead);LNode* cur = phead->next;while (cur != phead){LNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;
}

插入

找到 pos 的前驱 prev ；

将前驱，pos，新节点链接起来。

void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* newnode = CreateLTNode(x);// posprev newnode posposPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;
}

删除

找到 pos 的前驱和后继；

链接其前驱，后继；

删除pos。

void LTErase(LTNode* pos)
{assert(pos);LTNode* posNext = pos->next;LTNode* posPrev = pos->prev;posPrev->next = posNext;posNext->prev = posPrev;free(pos);//pos = NULL;
}

遍历打印

void LTPrint(LTNode* phead)
{assert(phead);printf("哨兵位<=>");LTNode* cur = phead->next;while (cur != phead){printf("%d<=>", cur->val);cur = cur->next;}printf("\n");
}