数据结构：双向循环链表详解
链表分类
链表总共有八种结构，实际中最常用的有这两种结构：单链表和双向带头循环链表（即双链表）。
- 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
- 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。结构虽然复杂，但是使用代码实现以后会发现结构会带来很多优势。
双向链表
概念
这里的 head 充当什么作用呢？ 带头链表里的头结点，实际为'哨兵位'，哨兵位结点不存储任何有效元素，只是站在这里'放哨的'。
结构
根据双链表概念，定义结构两个指针分别指向下一个结点和前一个结点的地址，并且每一个结点都能存储数据 data。
申请结点
LTNode* LTBuyNode(LTDataType x) {
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL) {
perror("malloc fail!");
exit(1);
}
// 申请成功
node->data = x;
node->next = node->prev = node;
return node;
}
创建头节点
根据概念创建一个头结点起到'放哨'的作用，这个结点可随意给值。 为什么用一级指针接收呢？保证哨兵位节点不能被删除（若被删除则不是双链表），节点的地址也不能发生改变，因此传一级最合适。
LTNode* LTInit() {
// 给双向链表创建一个哨兵位
LTNode* phead = LTBuyNode(-1);
return phead;
}
尾插、头插
尾插
首先，通过函数创建一个新节点，并将其数据域设置为输入的值 x，得到新节点的指针 newnode。 设置新结点的指针以插入到尾部。由于这是一个循环链表，尾节点的 next 指向头节点，所以将新节点 newnode 的 prev 指针指向前一个结点。 更新原链表尾节点的指针，使其 next 指针指向新节点 newnode，这样新节点就被正确地链接到链表的末尾。 最后，调整原头节点 phead 的 prev 指针，使其指向新节点 newnode，确保链表的循环特性仍然保持，即尾节点的 next 始终指向头节点。
void LTPushBack(LTNode* phead, LTDataType x) {
assert(phead);
LTNode* newnode = LTBuyNode(x);
newnode->prev = phead->prev;
newnode->next = phead;
phead->prev->next = newnode;
phead->prev = newnode;
}
头插
头插与尾插的方法类似。
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
newnode->prev = phead;
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
}
