前言
本章将带你们走进带头双向循环链表的实现与讲解
写在前面的话
在前一章我们学习实现了单链表（无头单向不循环链表），这里我们引入带头双向循环链表
很明显这两种结构截然不同，但都是作为链表最常使用链表结构
前者因其结构上的缺点而作为面试考题的常驻嘉宾
后者则是以结构最优著称，实现起来也是非常的简单（少了单链表头节点，尾节点，前一节点等问题的困扰）
链表类型区别
- 单向/双向
单向：节点结构中只存在下一节点的地址，所以难以从后一节点找到前一节点
双向：节点结构中存在前一节点和后一节点的地址，寻找前一节点和后一节点很便利
图示：
- 带头/不带头
带头：在本来的头结点之前还有一个哨兵卫节点作为头节点，它的址域指针指向头节点，值域不做使用
不带头：没有哨兵卫头节点，在尾删尾插等问题中要考虑头结点的情况（局限）
图示：
- 循环/非循环
循环：头结点会与尾节点相连
非循环：头结点不与尾节点相连
图示：
结构对比：
带头+双向+循环链表增删查改实现
接口展示
// 创建链表（链表初始化） ListNode* ListCreate(); //创建节点 ListNode* BuyListNode(ListNode* pHead); // 双向链表销毁 void ListDestory(ListNode* pHead); // 双向链表打印 void ListPrint(ListNode* pHead); // 双向链表尾插 void ListPushBack(ListNode* pHead, LTDataType x); // 双向链表尾删 void ListPopBack(ListNode* pHead); // 双向链表头插 void ListPushFront(ListNode* pHead, LTDataType x); // 双向链表头删 void ListPopFront(ListNode* pHead); // 双向链表查找 ListNode* ListFind(ListNode* pHead, LTDataType x); // 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x); // 双向链表删除pos位置的节点 void ListErase(ListNode* pos);
构建节点类型
这里的节点成员包含三个：值域，前址域，后址域
注：为了便于以后维护，我们将值域数据类型用tyedef修饰（便于更改）
参考代码：
//默认址域数据类型 typedef int LTDataType; //节点结构 typedef struct ListNode { //值域 LTDataType data; //后址域 struct ListNode* next; //前址域 struct ListNode* prev; }ListNode;
创建链表及初始化
- 注意：
要想得到并带出动态开辟的链表空间地址有两个方案：
- 设计传入参数为链表指针的地址，只有传入指针的地址，才能修改指针的内容，即改成动态开辟的链表地址将之带出函数
- 设计返回类型为节点指针，返回动态开辟的链表节点指针，使之在函数外就能够接受到改地址
注：这里展示第二个方案
- 参考代码：
// 创建链表（初始化） ListNode* ListCreate() { //开辟哨兵卫头结点 ListNode* plist = (ListNode*)malloc(sizeof(ListNode)); if (plist == NULL)//失败打印错误信息并结束进程 { perror("ListCreat fail:"); exit(-1); } //初始化哨兵卫头结点址域 plist->next = plist; plist->prev = plist; return plist; }
节点开辟
注：在后许多位置都需要开辟节点，这里我们将之封装成一个函数，便于调用
- 参考代码：
//创建节点 ListNode* BuyListNode(LTDataType x) { //创建节点 ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL)//失败打印错误信息并结束进程 { perror("creatnode fail:"); exit(-1); } newnode->data = x; //初始化结点 newnode->next = NULL; newnode->prev = NULL; return newnode; }
链表摧毁
注：动态开辟的链表空间，在不使用后需要将之释放，避免造成内存泄漏
- 注意：
- 循环遍历释放节点
- 释放前保存下一节点地址，避免地址丢失
参考代码:
// 双向链表销毁 void ListDestory(ListNode* pHead) { //断言传入指针不为NULL assert(pHead); //创建寻址指针 ListNode* cur = pHead; //断开循环链表 pHead->prev->next = NULL; while (cur!=NULL) { //记录下一个节点地址 ListNode* next = cur->next; //释放当前节点 free(cur); //找到下一个节点 cur = next; } return; }
链表打印
- 注意：
- 循环遍历链表打印数据
- 以哨兵卫头节点地址作为遍历结束标记
- 参考代码：
// 双向链表打印 void ListPrint(ListNode* pHead) { //断言传入指针不为NULL assert(pHead); //创建寻址指针 ListNode* cur = pHead->next; //循环遍历链表 while (cur != pHead) { //打印数据 printf("%d->", cur->data); //找到下一个节点 cur = cur->next; }printf("NULL\n"); return; }
链表尾插
- 注意：
- 尾插需要保存尾节点前一节点的地址
- 注意构建节点关系的逻辑
- 参考代码：
// 双向链表尾插 void ListPushBack(ListNode* pHead, LTDataType x) { //断言传入指针不为NULL assert(pHead); //创建节点 ListNode* newnode = BuyListNode(x); //找到尾节点 ListNode* tail=pHead->prev; //构建尾节点与新节点，新节点与哨兵卫头结点的关系 tail->next = newnode; newnode->prev = tail; pHead->prev = newnode; newnode->next = pHead; }
链表尾删
- 注意:
- 考虑节点只剩哨兵卫的情况
- 尾删前记录前一节点的地址
- 注意构建节点关系的逻辑
- 参考代码：
// 双向链表尾删 void ListPopBack(ListNode* pHead) { //断言传入指针不为NULL assert(pHead); //只剩哨兵卫头结点的情况 if (pHead->prev == pHead) return; //记录尾节点及其前一节点 ListNode* tail = pHead->prev; ListNode* tailprev = tail->prev; //释放尾节点 free(tail); //构建尾节点前一节点与哨兵卫头结点的关系 tailprev->next = pHead; pHead->prev = tailprev; return; }
链表头插
- 注意:
- 头插前记录哨兵卫头节点的下一节点
- 注意构建节点关系的逻辑
- 参考代码：
// 双向链表头插 void ListPushFront(ListNode* pHead, LTDataType x) { //断言传入指针不为NULL assert(pHead); //创建节点 ListNode* newnode = BuyListNode(x); //记录哨兵卫头结点的下一节点 ListNode* next = pHead->next; //构建各节点之间的关系 pHead->next = newnode; newnode->prev = pHead; newnode->next = next; next->prev = newnode; return; }
链表头删
- 注意：
- 考虑只剩哨兵卫头结点的情况
- 头删前保存节点地址
- 注意节点关系的构建
- 参考代码：
// 双向链表头删 void ListPopFront(ListNode* pHead) { //断言传入指针不为NULL assert(pHead); //只剩哨兵卫头结点的情况 if (pHead->next == pHead) return; //记录哨兵卫头结点下一节点及其的下一节点 ListNode* next = pHead->next; ListNode* nextNext = next->next; //释放节点以及构建关系 free(next); pHead->next = nextNext; nextNext->prev = pHead; return; }
链表查找
- 注意：
- 循环遍历链表，以哨兵卫头节点地址作为结束遍历
- 没找到则返回NULL，找到就返回其地址
- 参考代码：
// 双向链表查找 ListNode* ListFind(ListNode* pHead, LTDataType x) { //断言传入指针不为NULL assert(pHead); //创建寻址指针 ListNode* cur = pHead->next; while (cur != pHead) { //比较数据 if (cur->data == x) return cur; //找到下一个节点 cur = cur->next; } //没找到则返回NULL return NULL; }
链表pos位置前插
- 注意：
- 前插前保存前一节点地址
- 注意构建节点关系的逻辑
- 参考代码：
// 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x) { //断言传入指针不为NULL assert(pos); //创建新节点 ListNode* newnode = BuyListNode(x); //记录pos节点的前一节点 ListNode* prev = pos->prev; //构建节点之间的关系 prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; return; }
链表pos删除
- 注意：
- 删除前保存前节点和后节点地址
- 注意节点关系的构建
- 参考代码：
// 双向链表删除pos位置的节点 void ListErase(ListNode* pos) { //断言传入指针不为NULL assert(pos); //记录pos的前一节点和后一节点 ListNode* prev = pos->prev; ListNode* next = pos->next; //释放节点并构建关系 free(pos); prev->next = next; next->prev = prev; return; }
总结
- 因为前址域和后址域的存在，我们更好的找到当前节点的前后节点地址
- 因为带头的存在，我们能不用在意特殊的情况的困扰
- 因为循环的存在，我们能够直接找到尾节点
可见带头双向循环链表结构是非常强大的~
