一、前文
链表的分类有很多种，只需要将无头单向非循环链表和带头双向循环链表掌握，也就理解了剩下链表构成和实现。带头双向循环链表，结构复杂，一般只用于单独存储数据。但是也由于结构，带来了很多的优势，从而复杂结构，反而简单低实现。
二、实现带头双向循环链表
2.1 认识头节点
头节点(哨兵位)是指链表里面第一个节点，它不存放任何信息或存储任何有效元素，起到"放哨"作用，作用是减少了对一个节点是否为空的判断。
对于之前实现的单链表是不带哨兵位的，但是称第一个节点为头节点是不规范的，但是那样方便学习中称呼。
2.2 链表中节点成员
首先节点的成员:有效带数值，前驱指针，后继指针
- 前驱指针:以当前节点为参照物，向左就是前驱指针
- 后继指针：以当前节点为参照物，向右就是后继指针
typedef int LTDataType;//处理不同的数据类型 typedef struct SLTlistNode { LTDataType val; struct SLTlistNode* next; struct SLTlistNode* prev; }SLNode;
2.3 创建双向循环链表的节点
SLNode* CreatNewNode(LTDataType x) { SLNode* newnode = (SLNode*)malloc(sizeof(SLNode)); if (newnode == NULL) { perror("malloc fail!"); return ; } newnode->next = newnode; newnode->prev = newnode; newnode->val = x; return newnode; }
这里需要注意的是:跟实现单链表的节点，大体相同。但是需要前驱指针，后继指针都指向自己设计为一个闭环，在插入中这样子的设计有很好的优势
2.4 双向循环链表的插入节点
2.4.1 双向循环链表的尾插
void SLTPushBack(SLNode* head, LTDataType x) { assert(head); SLNode* newnode = CreatNewNode(x); SLNode* tail = head->prev;//尾插，需要找到尾 tail->next = newnode; newnode->prev = tail; head->prev = newnode; newnode->next = head; }
这里需要注意的是:由于一开始哨兵位就是循环体，一开始创建指向尾的指针，也是指向自己，这种结构具有很好的优势，维持闭环的状态，在进行插入或删除操作时，提供了便利。当进行尾插时，需要找到尾，再进行尾插操作。
2.4.2 双向循环链表的头插
void SLTPushFront(SLNode* head, LTDataType x)//双向循环链表无空指针 { assert(head); if (head->next==head) { SLTPushBack(head, x); } else { SLNode* newnode = CreatNewNode(x); SLNode* tail = head->prev; head->next = newnode; newnode->prev = head; newnode->next = tail; tail->prev = newnode; } }
这里需要注意的是 : 头插是值第一个有效数据节点前面插入，不是在哨兵位前面进行插入。当只有哨兵位存在时，这里跟尾插操作是一样的，剩下跟单链表的任意位置插入差不多，主要是改变指针的指向
2.5 双向循环链表的删除节点
2.5.1 双向循环链表的尾删
void SLTPopBack(SLNode* head)//哨兵位不删 { assert(head); assert(head->next!=head); SLNode* tail = head->prev; SLNode* tailprev = tail->prev; tailprev->next = head; head->prev = tailprev; free(tail); tail = NULL; }
这里需要注意的是:哨兵位不参与对节点进行操作时，对此不对哨兵位进行删除操作。由于循环体虽然没有空指针，但是可能会出现野指针现象。可以不置空free(tail)，不对tail指向空间进行访问。
2.5.2 双向循环链表的头删
void SLTPopFront(SLNode* head) { assert(head); SLNode* cur = head->next; SLNode* curnext = cur->next; if (head->next == head) { return 1; } else { head->next = curnext; curnext->prev = head; free(cur); cur = NULL; } }
这里需要注意的是:哨兵位不参与对节点进行操作时，对此不对哨兵位进行删除操作。双向循环的优势在此体现出来了，只需在cur和curnext位置上处理。
2.6 双向循环链表的查找
SLNode* SLFind(SLNode* head, LTDataType x) { assert(head); SLNode* cur = head->next; while (cur!=head) { if (cur->val == x) { return cur; } cur = cur->next; } return NULL; }
这里需要注意的是:当cur==head时，说明cur遍历完了链表。如果没有符合的值，则表示不存在；反之返回该位置的指针。
2.7 实现双向循环链表任意位置的插入和删除
2.7.1 任意位置插入
void SLInsert(SLNode* head, SLNode* pos,LTDataType x)//之前插入 { assert(head); SLNode* posprve = pos->prev; if (head->next == head) { SLTPushBack(head,x); } else { SLNode* newnode = CreateLTNode(x); posprve->next = newnode; newnode->prev = posprve; pos->prev = newnode; newnode->next = pos; } }
这里需要注意的是:当不存在有效数据时，默认是尾插操作。具体实现逻辑，知道pos和posprev的地址，再通过改变指针完成链接
2.7.2 任意位置删除
void SLEmpty(SLNode* head, SLNode* pos, LTDataType x) { assert(pos != head); assert(head); SLNode* posprve = pos->prev; SLNode* frist = posprve->prev; if (cur->next == head) { SLTPopBack(head); } else { frist->next = pos; pos->prev = frist; free(posprve); } }
这里需要注意的是:哨兵位不参与对节点进行操作时，对此不对哨兵位进行删除操作。只存在一个有效数据时，只进行尾删操作即可。对于三个指针的位置关系，满足pos在两个指针之间
以上就是双向循环链表的核心接口，接下来实现一些实用小接口，丰富我们的双向循环链表
2.8 双向循环链表的打印
void SLTPrint(SLNode* head) { assert(head); printf("哨兵位<->"); SLNode* cur = head->next; while (cur != head ) { printf("%d<->", cur->val); cur = cur->next; } }
##2.9 双向循环链表的销毁
void SLDestroy(SLNode* head) { assert(head); SLNode* cur = head->next; //结束条件是什么，这里是无死角的-->先销毁哨兵位之外的空间 while (cur!=head) { SLNode* curnext = cur->next; free(cur); cur = curnext; } free(head); }
这里需要注意的是:先将除哨兵位之外的空间释放，最后在释放哨兵位
三、双向循环链表的好处
在实现过程中，我们清晰地知道，如果需要快速搭建一个链表，实现双向循环链表中任意插入、删除是很快的，这里利用到了结构特点。
