导航
1、带头双向循环链表介绍
在上一篇博客我们讲述了链表的概念和结构，还实现了无头单向非循环链表接口写法，那么这一章节，我们来实现另一种常用的链表组成结构——带头双向循环链表。
如果对前面的链表基本概念还是不了解，可以看作者的上一篇博客：线性表中链表介绍及无头单向非循环链表接口实现
2、结构体及接口函数定义
首先是结构体的定义
代码如下：
typedef int LTDateType; typedef struct ListNode { LTDateType data;//结点存储元素 struct ListNode* next;//下一结点指针 struct ListNode* prev;//上一结点指针 }LTNode;
然后就是接口函数的定义
代码如下：
void ListInit(LTNode* phead)；//哨兵位头结点初始化 LTNode* BuyListNode(LTDateType x);//动态申请结点 void ListPushBack(LTNode* phead, LTDateType x);//双向链表尾插 void ListPopBack(LTNode* phead);//双向链表尾删 void ListPushFront(LTNode* phead, LTDateType x);//双向链表头插 void ListPopFront(LTNode* phead);//双向链表头删 LTNode* ListFind(LTNode* phead, LTDateType x);//双向链表查找 void ListInsert(LTNode* pos, LTDateType x);//在pos位置前插入 void ListErase(LTNode* pos);//删除pos位置的结点 void ListPrint(LTNode* phead);//打印双向链表 void ListDestroy(LTNode* phead);//销毁双向链表
3、接口函数实现
在上一篇博客中我们讲到不带头的单非循环链表存在一定缺陷，就是无法访问上一结点，但是这一节讲的带头双向循环链表就很好的弥补了这一缺点，带头双向循环链表看来比单链表结构要复杂很多，但其实实现起来要比单链表更简单，更高效；下面我们就来实现带头双向循环链表的接口函数吧！
3.1 头结点初始化
头结点初始化（ListInit）
首先是我们的头结点的定义，它是不存放数据的，起到一个哨兵的作用
代码如下：
void ListInit(LTNode* phead) { // 哨兵位头结点 LTNode* phead = (LTNode*)malloc(sizeof(LTNode)); phead->next = phead; phead->prev = phead; return phead; }
第一步当然是先使用malloc函数申请内存空间，然后就是两个指针的建立，尾部指针指向头结点头部，头部指针指向头结点尾部，返回带头结点，头结点初始化完成。
3.2 结点动态内存申请
结点动态内存申请（BuyListNode）
这个函数和上一篇中的单链表的函数类似
代码如下:
LTNode* BuyListNode(LTDateType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }
第一步也是先使用malloc函数申请内存空间，然后就是初始化这个结点的操作，将元素插入，两个指针指向空，返回新结点，完成结点初始化操作。
3.3 双向链表尾插
双向链表尾插（ListPushBack）
代码如下：
void ListPushBack(LTNode* phead, LTDateType x) { assert(phead); LTNode* tail = phead->prev; LTNode* newnode = BuyListNode(x); tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
这里我们先是把phead的上一级指针赋给tail
再将要插入的元素赋给临时结点newnode
接着将tail的下一级指针指向newnode
再将newnode上一级指针指向tail
newnode下一级指针指向被插入结点phead
最后将phead的上一级指针再指向newnode完成尾插操作
3.4 双向链表尾删
双向链表尾删（ListPopBack）
代码如下：
void ListPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead);//防止链表中无元素继续删除的断言 LTNode* tail = phead->prev; phead->prev = tail->prev; tail->prev->next = phead; free(tail); }
上述代码中第二个断言是为了防止链表中无元素继续删除
这里我们也是先把phead的上一级指针赋给tail
再将tail的上一级指针赋给phead的上一级指针
也就是指向要删除结点的上一结点
最后将要删除结点的前一个结点的下一级指针指向头结点
然后释放掉tail的内存空间完成尾删
3.5 双向链表头插
双向链表头插（ListPushFront）
代码如下：
void ListPushFront(LTNode* phead, LTDateType x) { assert(phead); LTNode* newnode = BuyListNode(x); LTNode* next = phead->next; phead->next = newnode; newnode->prev = phead; newnode->next = next; next->prev = newnode; }
这里我们先和尾插一样将要插入的元素值赋给临时结点newnode
将phead下一级指针赋给临时结点next
再将newnode赋给phead下一级指针
也就是把phead的尾部指针指向newnode
把phead赋给newnode的上一级指针
再将next赋给newnode的下一级指针
最后把newnode赋给next的上一级指针，完成头插
