双向循环链表接口
1.链表定义
双向链表就在这里可以体现，也就是双指针，next和prev
typedef int LTDataType; typedef struct ListNode { LTDataType data; struct ListNode* next; struct ListNode* prev; }ListNode;
2.链表初始化
链表初始化，这里可以体现循环这一特点以及头结点的建立。
ListNode* ListInit() { ListNode* phead = BuyListNode(-1);//头结点 phead->next = phead;//循环 phead->prev = phead; return phead; }
3.链表的销毁
这里对于链表销毁，无非就是链表遍历，但主要是我们要明白如何遍历：
这里我们会选择从头结点的下一个结点（cur）开始遍历，直到回到头结点,完成一次遍历，每遍历一个元素，就释放一个元素，所以我们为了方便一般好会有个（next）指针指向cur下一个位置
void ListDestroy(ListNode* phead) { assert(phead);//什么时候断言：当phead不可能为空的时候断言 ListNode* cur = phead->next; ListNode* next = cur->next; while (cur != phead) { free(cur);//销毁cur指向的结点 cur = next; next = cur->next; } free(phead); phead = NULL; }
4.链表的打印
同样的道理，遍历打印即可。
void ListPrint(ListNode* phead) { assert(phead); ListNode* cur = phead->next; printf("phead<=>"); while (cur!=phead) { printf("%d<=>", cur->data); cur = cur->next; } printf("\n"); }
5.链表的查找
遍历对比即可。
ListNode* ListFind(ListNode* phead, LTDataType x) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { if (x == cur->data) { return cur; } } return NULL; }
6.链表的插入
链表任意位置插入，需要结合上述接口，链表的查找，找到pos位置，然后在pos前后插入，这里是pos前插入。
void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* node = BuyListNode(x); ListNode* cur = pos->prev;//优化插入过程 //pos前结点与新节点建立联系 cur->next = node; node->prev = cur; //新节点与pos建立联系 pos->prev = node; node->next = pos; }
我们来思考一下，如果我们没有ListNode* cur = pos->prev;//优化插入过程这串代码，会有什么麻烦。
- 麻烦在于我们必须考虑连接的先后顺序，不可以先改变pos位置指针与前一个结点的关系，不然会增大找到上一个结点的难度（只能遍历寻找）。
- 只能先建立前一个结点与newnode结点的关系 。
7.链表的删除
这里思路也更加简单，记录pos位置前后，然后释放pos，在直接用指针链接前后关系。
void ListErase(ListNode* pos) { assert(pos); ListNode* prev = pos->prev; ListNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); pos = NULL; }
8.判断链表是否为空
注意带库声明，其余都比较简单
bool ListEmpty(ListNode* phead) { assert(phead); return phead->next == phead; }
9.获取链表元素个数
遍历并且带着一个count记录即可。
int ListsSize(ListNode* phead) { assert(phead); ListNode* cur = phead->next; int count = 0; while (cur != phead) { count++; cur = cur->next; } return count; }
2.总结：
带头双向循环链表在我们学习了单链表以后显得十分简单，因为带头结点，插入也不需要二级指针。具体原因如下：
插入过程中并没有改变头节点的位置，因此无需通过二级指针来更新头节点的指向。只需要通过头指针即可访问到头节点，并进行相应的操作。phead并未改变。
