目录
1.单向链表的劣势
2.带头双向循环链表
1.逻辑结构
2.结点的代码实现
3.双向链表接口的实现
1.接口1---初始化
2.接口2 ， 3---头插 ， 尾插
3. 接口4 ， 5---头删 ， 尾删
3. 接口6---查找
4. 接口7 ， 8--插入 ， 删除
5.接口8---打印
6.接口9--销毁
4.完整代码及效果展示
1.单向链表的劣势
上期我们讲解了链表8种结构中最为常用的两种结构之一的单向不带头不循环链表的基本概念和实现方法（传送门：动图详解单向链表） 。但是在实现时我们发现了以下局限性：
由于单链表是单向的 ， 当我们想进行插入或者删除时 ， 由于无法直接找到前驱结点 ， 导致我们还需再使用一个指针遍历链表找到前一个结点的位置 。这就导致了进行插入和删除的时间复杂度为O(N) ， 时间效率较低 。由于我们需要再使用一个指针指向链表前一个结点 ， 这也可能在一些情况下导致出错 ， 例如链表只有一个结点 。（详情请见上一期 ， 含动图分析）由于其不带头结点 ， 头指针直接指向第一个有效结点 ， 所以在进行头插等可能改变头指针的操作时我们如果传一级指针就会出错 。2.带头双向循环链表1.逻辑结构
那么 ， 我们要如何解决以上劣势呢？这就不得不说到另一种最为常见的链表结构：带头双向循环链表 。
头结点：所谓头结点 ， 其作用就是标识链表的有效部分 。我们之前实现的无头结点的链表 ， 都是通过头指针直接指向链表的有效数据部分 。而带头结点的链表 ， 则是用头指针指向一个不存放有效数据的结点 ， 这个结点就称作头结点 。这个结点的next指针存放的下一个结点才是链表的有效结点部分 。图示如下：
带头双向循环链表：其结构是8种结构中最复杂的 ， 一般用在单独存储数据 。实际中使用的链表数据结构 ， 都是带头双向循环链表 。此链表的结点在单向链表的基础上 ， 添加了前驱指针prev指向上一个结点 ， 然后添加了上述所描述的头结点 ， 而循环则是体现在首尾结点相连上 。另外这个结构虽然结构复杂 ， 但是使用代码实现以后会发现结构会带来很多优势 ， 实现起来反而更加简单 。逻辑结构如下：
注：蓝色箭头代表逻辑上指针的指向 ， 均表示某个结点next或prev指针指向另一个结点 ， 下同 。
2.结点的代码实现
根据单向链表结点的代码实现和双向链表的结构体 ， 我们可以得出其结点的结构体定义如下：
3.双向链表接口的实现
我们同样先在主函数中定义一个头指针用于指向我们的头结点 ， 后续通过这个指针来完成对链表各种接口的实现 。由于头指针并不直接指向有效数据部分 ， 有效数据是从第二个结点开始的 ， 因此当我们对数据进行操作时并不需要改变头指针的内容 ， 只需进行传值调用 ， 用一级指针接收即可 ， 可以有效避免头指针被无意修改 。
1.接口1---初始化
在使用链表前 ， 我们需要对链表进行初始化 。我们可以在初始化接口中创建一个头结点并将其返回给头指针 ， 代码如下：
//用于创建新结点ListNode* CreatNode(ListDateType x){ListNode* cur=(ListNode*)malloc(sizeof(ListNode));cur->date = x;cur->next = NULL;cur->prev = NULL;return cur;}//链表初始化ListNode* InitList(){ListNode* phead=CreatNode(0); //创建头结点phead->next = phead; //前驱指针指向自身phead->prev = phead; //后继指针指向自身return phead; //将这个结点返回}