2.接口2 ， 3---头插 ， 尾插
对于头插 ， 根据双向循环链表结构图 ， 我们只需将头结点的next指向新结点 ， 新结点的prev指向头结点 ， next指向下一结点 ， 下一结点的prev指向新结点即可完成头插 。具体过程如下：
代码实现如下：
//头插void ListPushFront(ListNode* phead, ListDateType x) //不改变头指针 ， 无需传址{assert(phead != NULL); //保证链表有头结点 ， 即完成了初始化ListNode* NewNode = CreatNode(x); //创建新结点ListNode* frist = phead->next; //找到链表头//进行头插phead->next = NewNode;NewNode->prev = phead;NewNode->next = frist;frist->prev = NewNode;}
对于尾插 ， 由于双向循环链表结构的特殊性 ， 我们不需要向单链表一样遍历链表找到链表尾 ， 直接通过头结点的prev指针就可直接找到链表尾 ， 也不需要再遍历链表找到上一个结点 。代码反而变得更加简单 ， 只需要通过改变结点的prev和next指针即可完成尾插 ， 这就是结构带来的优势 。其时间复杂度为O(1) 。具体过程如下：
具体代码如下：
//尾插void ListPushBack(ListNode* phead, ListDateType x){assert(phead != NULL); //保证链表已经初始化ListNode* NewNode = CreatNode(x); //创建新结点ListNode* tail = phead->prev; //找到链表尾//进行尾插tail->next = NewNode; NewNode->prev = tail;NewNode->next = phead;phead->prev = NewNode;}
需要注意的是 ， 与单链表不同 ， 这里是双向循环链表 ， 所以链表尾并不是指向NULL ， 而是指向头结点 。同时不会出现对NULL解引用的情况 ， 不需要对单向链表一样进行分类讨论 。
3. 接口4 ， 5---头删 ， 尾删
对于头删 ， 我们只需要将头结点指向下一个位置 ， 然后将原来指向的空间free()掉即可 。如果链表为空 ， 我们就让函数直接返回 ， 具体动态效果如下：
代码实现如下：
//头删void ListPopFront(ListNode* phead){assert(phead != NULL); //确保链表初始化if (phead->next == phead){return; //链表为空直接返回 ， 防止把头结点删除}ListNode* frist = phead->next; //找到链表头ListNode* second = frist->next; //找到链表头下一个结点//进行头删phead->next = second;second->prev = phead;free(frist); //释放结点frist = NULL;}
对于尾删 ， 我们同样通过头结点的prev指针直接找到链表尾 ， 然后进行删除操作 ， 过程与头删类似 ， 时间复杂度为O(1) 。具体过程如下：
具体代码如下：
//尾删void ListPopBack(ListNode* phead){assert(phead != NULL); //确保链表已经初始化if (phead->next == phead){return; //链表为空直接返回 ， 防止把头结点删除}ListNode* tail = phead->prev; //找到链表尾ListNode* prev = tail->prev;//找到前驱//进行尾删phead->prev = prev;prev->next = phead;free(tail); //释放空间tail = NULL;}
3. 接口6---查找
对于查找 ， 其方法与单向链表一样 ， 通过遍历链表的所有结点即可 。有一点不同的是我们的双向链表是循环的 ， 因此循环的条件不再是cur！=NULL而是cur！=phead ， 当cur等于头指针时则说明已经成功遍历一遍了 。代码如下：
//查找ListNode* ListFind(ListNode* phead, ListDateType x){assert(phead != NULL); //确保已经初始化ListNode* cur = phead->next; //指向第一个有效结点 ， 准备遍历while (cur != phead) //遍历一圈{if (cur->date == x){return cur; //找到了 ， 返回结点}cur = cur->next; //指向下一结点}//找不到 ， 返回空指针return NULL;}