目录

一：前言

（1）什么是双链表

（2）双向带头循环链表的好处

二：双向链表实现

（1）创建源文件和头文件

（2）生成一个新结点

（3）链表初始化

（4）链表的打印

（5）尾部插入

（6）尾部删除

（7）头部插入

（8）头部删除

（9）查找

（10）指定插入

（11）指定删除

（12）小优化和最终代码

😉小优化

🧐最终代码

三：小结

一：前言

上次我们学习了怎么实现单链表，这一次我们将以单链表为基础实现双链表。

附上单链表链接：http://t.csdn.cn/G7z4m

（1）什么是双链表

🤓我们先看下面这个结构体

 相较与单链表，双链表多定义了一个prev(prevent)指针用来记录该结点的前一个结点，这样我们就既可以找前又可以找后了，双链表有很多种结构，有带哨兵不循环，带哨兵循环或者不带哨兵不循环以及不带哨兵循环。

本文选择的是带哨兵循环(双向带头循环)

（2）双向带头循环链表的好处

我们先看一下双向带头循环链表的大致结构：

 

【1】我们可以很清楚的看到双向带头循环链表的一大优势:由哨兵位直接找到尾部结点。

【2】由于哨兵位的存在，我们不必考虑链入第一个结点这样的特殊情况。

【3】代码实用性强，实际运用最多。

 

二：双向链表实现

（1）创建源文件和头文件

🤓头文件：BoubleList.h用来包含一些必须的头文件，定义结构体，声明相关函数。

🤓源文件：

【1】BoubleList.c用来实现具体的功能。

【2】text.c用来测试接口函数。

（2）生成一个新结点

后续的插入，初始化我们都需要生成一个新的结点，为了让代码更加简洁美观，我们把这个部分单独封装成函数BuyListNode()，函数返回值位新结点地址。

代码：

 

（3）链表初始化

🤓初始化的要点：

【1】要申请一个哨兵位的结点。

【2】返回申请的哨兵位的地址。(也可以通过传入二级指针的方式进行初始化，形参和实参的关系在单链表一文已经讲过，这里不再赘述)

【3】这个时候只有一个结点，我们让这个结点自己成环。

代码：

（4）链表的打印

🤓与单链表打印的不同：

【1】链表是循环的，没法以空指针位结束条件。

【2】链表的第一个结点存储的是无效数据，我们要忽略哨兵结点。

综上所述我们可以以第一个有效结点为起始位置，以走到哨兵位为结束条件。

代码：

图解：

（5）尾部插入

🤓尾插的基本思路：

【1】生成新结点。

【2】尾结点的next指向新结点。

【3】新结点的prev指向原尾结点，next指向头结点。

【4】头结点的prev指向新结点。

代码：

 

（6）尾部删除

🤓尾删的基本思路：

【1】记录尾部的前一个结点。

【2】头指针的prev指向新的尾结点。

【3】新的尾结点的next指向头结点。

【4】注意不要删除掉头结点。

代码：

 

（7）头部插入

🤓头插的基本思路：

【1】记录原有效头的结点。

【2】原有效头的prev指向新有效头。

【3】新有效头的prev指向哨兵位，next指向原有效头。

【4】哨兵位的next指向新有效头。

代码：

 

（8）头部删除

🤓头删的基本思路：

【1】记录要删除的原有效头结点。

【2】新有效头结点的prev指向哨兵位。

【3】哨兵位的next指向新有效头结点。

【4】注意不要删除哨兵位。

代码：

 

（9）查找

🤓查找的基本思路：

【1】和打印类似，从有效头开始遍历，到哨兵结束。

【2】返回对应结点的地址。

代码：

 

（10）指定插入

🤓指定插入的基本思路：

【1】先用查找找到节点位置pos。

【2】记录后一个结点。

【3】新结点的next指向pos的后一个结点，新结点的prev指向pos

【4】后一个结点的prev指向新结点。

【5】pos结点的next指向新结点。

代码：

 

（11）指定删除

🤓指定删除的基本思路：

【1】记录要删除的结点的后一个结点和前一个结点。

【2】后一个结点的prev指向待删除结点的前一个结点。

【3】前一个结点的next指向待删除结点的后一个结点。

【4】注意不要删除掉哨兵位。

代码：

 

（12）小优化和最终代码

😉小优化

前面我们已经实现了指定插入和指定删除，而头尾删，头尾插不过是指定删除和指定插入的特殊情况而已，所有我们可以在这些函数中复用指定插入和删除，使代码更加简洁。

代码：

 

 

 

 

🧐最终代码

BoubleList.

#define _CRT_SECURE_NO_WARNINGS 1
#include 
#include 
#include 
//重定义，方便更改存储数据的类型
typedef int LTDataType;
typedef struct ListNode {LTDataType data;struct ListNode* next;struct ListNode* prev;
}LT;
//申请新结点
LT* BuyListNode();
//链表初始化
LT* ListInit();
//打印链表
LT* ListPrint(LT* phead);
//尾部插入
void ListPushBack(LT* phead, LTDataType x);
//尾部删除
void LsitPopBack(LT* phead);
//头部插入
void ListPushFront(LT* phead, LTDataType x);
//头部删除
void ListPopFront(LT* phead);
//查找
LT* ListPopFind(LT* phead, LTDataType x);
//指定插入
void ListInsert(LT* phead, LT* pos, LTDataType x);
//指定删除
void ListErase(LT* phead, LT* pos);

BoubleList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "BoubleList.h"
//申请新结点
LT* BuyListNode()
{LT* newNode = (LT*)malloc(sizeof(LT));//新结点的prev，next最好置空newNode->next = NULL;newNode->prev = NULL;//返回新结点return newNode;
}//初始化
LT* ListInit( )
{LT* phead = NULL;//生成哨兵结点phead = BuyListNode();//只有一个结点，这个结点自己成环phead->next = phead;phead->prev = phead;//返回头结点return phead;
}//打印
LT* ListPrint(LT* phead)
{//如果未初始化，报错assert(phead != NULL);//从有效头结点开始走，一直到哨兵位结束LT* cur = phead->next;while (cur != phead){//打印printf("%d ", cur->data);//迭代cur = cur->next;}printf("NULL");printf("\n");
}//尾插
void ListPushBack(LT* phead,LTDataType x)
{//如果未初始化，报错assert(phead != NULL);//复用指定插入ListInsert(phead, phead->prev, x);
}//尾部删除
void LsitPopBack(LT* phead)
{//如果未初始化，报错assert(phead != NULL);//不能删除哨兵结点assert(phead != phead->prev);//复用指定删除ListErase(phead, phead->prev);
}//头部插入
void ListPushFront(LT* phead,LTDataType x)
{//如果未初始化，报错assert(phead != NULL);//复用指定插入ListInsert(phead, phead, x);
}//头部删除
void ListPopFront(LT* phead)
{//如果未初始化，报错assert(phead != NULL);//不能删除哨兵位assert(phead->next != phead);//复用指定删除ListErase(phead, phead->next);
}//查找，返回结点位置
LT* ListPopFind(LT* phead, LTDataType x)
{//如果未初始化，报错assert(phead != NULL);//和打印一样从第一个有效结点开始遍历LT* cur = phead->next;while (cur != phead){//查找到返回结点位置if (cur->data == x)return cur;//迭代cur = cur->next;}//查找失败，返回nullreturn NULL;
}//指定插入（后）
void ListInsert(LT* phead, LT* pos,LTDataType x)
{//如果未初始化，报错assert(phead != NULL);//生成新结点LT* newnode = BuyListNode();//记录后一个结点LT* beforenode = pos->next;//新结点的next指向pos的后一个结点newnode->next = beforenode;//新结点的prev指向posnewnode->prev = pos;//后一个结点的prev指向新结点beforenode->prev = newnode;//pos结点的next指向新结点pos->next = newnode;//存储数据newnode->data = x;
}//指定删除
void ListErase(LT* phead, LT* pos)
{//如果未初始化，报错assert(phead != NULL);//不能删除哨兵assert(pos != phead);//记录要删除的结点的后一个结点LT* beforepos = pos->next;//记录待删除结点的前一个结点LT* aheadpos = pos->prev;//后一个结点的prev指向待删除结点的前一个结点beforepos->prev = aheadpos;//前一个结点的next指向待删除结点的后一个结点aheadpos->next = beforepos;//释放结点free(pos);
}

text.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "BoubleList.h"
//测试1
void text1()
{//初始化LT* SL=ListInit();//尾部插入ListPushBack(SL, 5);ListPushBack(SL, 8);ListPushBack(SL, 10);//打印ListPrint(SL);//头部插入ListPushFront(SL, 8);ListPushFront(SL, 889);//尾部删除LsitPopBack(SL);//打印ListPrint(SL);//头部删除ListPopFront(SL);ListPopFront(SL);ListPopFront(SL);//指定插入ListInsert(SL, ListPopFind(SL,8), 56);ListPushBack(SL, 100);ListPrint(SL);ListErase(SL, ListPopFind(SL, 100));ListPrint(SL);
}void text2()
{//初始化LT* SL = ListInit();ListPushFront(SL, 8);ListPushFront(SL, 889);ListPushBack(SL, 5);ListPushBack(SL, 8);ListPushFront(SL, 800);LsitPopBack(SL);ListPrint(SL);}int main()
{text1();//text2();return 0;
}

三：小结

【1】与单链表相比，双向带头循环链表的结构更复杂，但是实用性更强。

【2】单链表结构一般不会单独用来存储数据，更多的是作为其它结构的子结构。

【3】正因单链表的不完美，所以能够更好考验水平。下一次我们会进行链表OJ题目的讲解，其中大部分的题目都是通过巧妙的方式弥补单链表的缺点。