4. 接口7 ， 8--插入 ， 删除
对于插入 ， 我们可以实现一个在指定结点前插入一个新结点的接口 ， 而这个指定结点我们可以通过查找接口来获取 。由于我们的链表是双向的 ， 我们就可以很容易的得到新结点的前一个与后一个结点的位置 ， 进而实现插入接口 ， 其时间复杂度为O(1) 。动态效果如下：
//插入void ListInsert(ListNode* phead, ListNode* pos, ListDateType x){assert(pos != NULL); //确保已经初始化ListNode* NewNode = CreatNode(x); //创建新结点ListNode* prev = pos->prev; //前一个结点//进行插入NewNode->next = pos;pos->prev = NewNode;prev->next = NewNode;NewNode->prev = prev;}
对于删除 ， 我们同样可以实现一个删除指定结点的接口 ， 而这个指定结点我们依旧可以通过查找接口来获取 。同样的 ， 由于结构上的优势 ， 我们可以很方便的直接对指定位置进行删除 ， 时间复杂度为O(1) 。具体过程如下：
具体代码如下：
//删除void ListErase(ListNode* phead, ListNode* pos){assert(pos != NULL); //确保已经初始化ListNode* next = pos->next; //后一个结点ListNode* prev = pos->prev; //前一个结点//进行删除prev->next = next;next->prev = prev;free(pos); //释放空间pos = NULL;}
5.接口8---打印
对于打印 ， 很简单 ， 遍历一圈链表即可 ， 当cur等于头结点地址时停止打印 。动图效果如下：
具体代码如下：
//打印void ListPrint(ListNode* phead){assert(phead != NULL); //确保链表已经初始化ListNode* cur = phead->next; //指向有效部分while (cur != phead) //遍历一圈{printf("%d ", cur->date); //打印数据cur = cur->next; //指向下一结点}printf("\n");}
6.接口9--销毁
对于销毁 ， 我们动态内存申请所得到的空间 ， 当我们不需要的时候 ， 需要我们进行手动销毁 。因此 ， 我们还需要一个接口对使用完毕的链表进行free() ， 具体代码如下：
//销毁void ListDestroy(ListNode* phead){assert(phead != NULL); //确保已经初始化ListNode* cur = phead->next; //指向有效部分while (cur != phead) //释放有效结点{ListNode* next = cur->next;free(cur);cur = next;}//释放头结点free(phead);phead = NULL;}
通过上面一个个接口的实现 ， 我们发现：
虽然双向带头循环链表的结构比起单向链表结构复杂太多 ， 但对于各接口的实现反而变得更加方便 ， 并且很多接口时间效率更加地高 。因此 ， 一个好的结构不仅可以简化我们的代码量 ， 也可以提高我们代码的效率 。
4.完整代码及效果展示
我们同样采用多文件编写的形式 ， 将上述接口的定义实现放在List.c文件中 ， 然后将接口的声明和结构体的定义放于List.h头文件中 ， 以达到封装的效果 。这样我们如果需要使用双向链表 ， 就只需要在文件中包含对应的头文件List.h就可以使用我们上面定义的各种接口 。以下为本文实现的带头双向循环链表完整代码以及效果展示：
//List.h文件 ， 用于声明接口函数 ， 定义结构体#pragma once#include#include#includetypedef int ListDateType; //重命名便于维护typedef struct ListNode{ListDateType date;struct ListNode* next; //指向前一个结点struct ListNode* prev; //指向后一个结点}ListNode;//初始化ListNode* InitList();//尾插void ListPushBack(ListNode* phead, ListDateType x);//头插void ListPushFront(ListNode* phead, ListDateType x);//尾删void ListPopBack(ListNode* phead);//头删void ListPopFront(ListNode* phead);//查找ListNode* ListFind(ListNode* phead, ListDateType x);//删除void ListErase(ListNode* phead, ListNode* pos);//插入void ListInsert(ListNode* phead, ListNode* pos, ListDateType x);//打印void ListPrint(ListNode * phead);//销毁void ListDestroy(ListNode* phead);