作者:云小逸
个人主页:云小扬的主页
码云：云小扬 (YunXiaoYang003) – Gitee.com
motto:要敢于一个人默默的面对自己，强大自己才是核心。不要等到什么都没有了，才下定决心去做。种一颗树，最好的时间是十年前，其次就是现在！学会自己和解，与过去和解，努力爱自己。希望春天来之前，我们一起面朝大海，春暖花开！
专栏：C语言初阶专栏：C语言进阶专栏：数据结构和算法
专栏：C++初阶—专栏：C++进阶–专栏：Linux学习

文章目录

  • 前言
  • 1.链表的分类：
  • 2.双向链表的初始化：
      • 方法一：传==双指针==
      • 方法二：==返回值==法
  • 3.双向链表的打印
    • （1）运行代码：
    • （2）运行结果：
  • 4.双向链表的尾插：
    • （1）运行代码：
    • （2）运行结果：
  • 5.双向链表的尾删
    • （1）运行代码：
    • （2）运行结果：
  • 6.双向链表的头插：
    • （1）运行代码：
    • （2）运行结果：
  • 7.双向链表的头删：
    • （1）运行代码：
    • （2）运行结果：
  • 8.双向链表的查找
    • （1）运行代码：
    • （2）运行结果：
  • 9.双向链表的中间插入：
    • （1）运行代码：
    • （2）运行结果：
  • 10.双向链表的中间删除：
    • （1）运行代码：
    • （2）运行结果：
  • 11.双向链表的销毁：
  • 12.完整代码：
    • （1）List.h文件：
    • （2）List.c文件：
    • （3）test.c文件：
  • 最后
    • ​

前言

今天我们来聊一聊：数据结构中链表的双向循环带头链表，对于第一次听到双向循环带头链表的同学，可能会认为双向循环带头链表是十分复杂的，的确双向循环带头链表的结构是有点复杂，但是它的操作是非常简单的，非常便于操作，那么现在就由云小逸带你了解认识学习双向循环带头链表。
——————————————————————————————

1.链表的分类：

  1. 单向、双向
  2. 带头、不带头
  3. 循环、非循环

    今天我们就来讲一讲链表中看似结构复杂的双向循环带头链表：

2.双向链表的初始化：

方法一：传双指针

void ListNodeInit(ListNode** pphead){*pphead = ListNodeBuy(0);//ListNodeBuy（0）是建立一个存储0的地址的函数，后面会写上这个函数(* pphead)->next = *pphead;(*pphead)->prev = *pphead;}

方法二：返回值法

ListNode* ListNodeInit(){ListNode* phead = ListNodeBuy(0);phead->next = phead;phead->prev = phead;return phead;}

再加上主函数上写：

ListNode* phead=ListNodeInit();

即可完成双向链表的初始化。

PS：双向循环带头链表为空时，即是只有头指针时，head->next和head->prev均指向自己（head）

3.双向链表的打印

（1）运行代码：

void ListPrint(ListNode* phead){assert(phead);ListNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");}

这里要记得双向循环带头链表打印时的终止条件是：当cur遍历回到了phead！

（2）运行结果：

4.双向链表的尾插：

（1）运行代码：

由于插入时要创建一个变量newnode，需向内存申请空间存储变量，且变量的值为插入的值，又因为每次插入都需要这一步，故将这一步写成一个函数，便于使用该函数为：

ListNode* ListNodeBuy(LTDataType x){ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));newnode->next = NULL;newnode->prev = NULL;newnode->data=x;return newnode;}

尾插函数：

void ListNodePushBack(ListNode* phead, LTDataType x){assert(phead);ListNode* tail = phead->prev;ListNode* newnode = ListNodeBuy(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}

（2）运行结果：

5.双向链表的尾删

（1）运行代码：

void ListNodePopBack(ListNode* phead){assert(phead);//这是调用断言函数，该表达式的意思为判断phead是否为NULLassert(phead->next != phead);//这是判断该链表是否为空链表，若为空链表，则会报错ListNode* tail = phead->prev;ListNode* tail_prev = tail->prev;tail_prev->next = phead;phead->prev = tail_prev;free(tail);tail = NULL;}

assert(phead);//这是调用断言函数，该表达式的意思为判断phead是否为NULL
assert(phead->next != phead);//这是判断该链表是否为空链表，若为空链表，则会报错

（2）运行结果：

6.双向链表的头插：

（1）运行代码：

void ListNodePushFront(ListNode* phead, LTDataType x){assert(phead);ListNode* first = phead->next;ListNode* newnode = ListNodeBuy(x);phead->next = newnode;newnode->next = first;newnode->prev = phead;first->prev = newnode;}

注：头插是是将newnode插在phead和first（头结点后的第一个结点）

（2）运行结果：

7.双向链表的头删：

（1）运行代码：

void ListNodePopFront(ListNode* phead){assert(phead);//这是调用断言函数，该表达式的意思为判断phead是否为NULLassert(phead->next != phead);//这是判断该链表是否为空链表，若为空链表，则会报错ListNode* first = phead->next;ListNode* second = first->next;phead->next = second;second->prev = phead;free(first);first = NULL;}

（2）运行结果：

8.双向链表的查找

（1）运行代码：

ListNode* ListNodeFind(ListNode* phead, LTDataType x){assert(phead);ListNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;}

查找后返回的是结点的指针，可以用pos->data=某个数进而修改这个点的值！！！

（2）运行结果：

9.双向链表的中间插入：

（1）运行代码：

插入在指定位置的前面

void ListNodeInsert(ListNode* pos, LTDataType x){assert(pos);ListNode* pos_prev = pos->prev;ListNode* newnode = ListNodeBuy(x);newnode->next = pos;pos->prev = newnode;pos_prev->next = newnode;newnode->prev = pos_prev;}

（2）运行结果：

10.双向链表的中间删除：

（1）运行代码：

void ListNodeErase(ListNode* pos){assert(pos);ListNode* pos_prev = pos->prev;ListNode* next = pos->next;free(pos);pos = NULL;pos_prev->next = next;next->prev = pos_prev;}

（2）运行结果：

11.双向链表的销毁：

每一次用完链表后销毁是很有必要的，如果不销毁，将会导致内存的泄露，短时间内可能没用什么，且很难被发现，但时间长了，必将导致程序的崩溃，最终将导致时间和金钱的浪费！！！
这里介绍两种销毁：
方法一：销毁全部，不保留头结点：

void ListNodeDestroy(ListNode* phead){assert(phead);ListNode* cur = phead;while (cur != phead){ListNode* next = cur->next;free(cur);cur = NULL;cur = next;}free(phead);phead=NULL;}

方法二：保留头结点：

void ListNodeDestroy(ListNode* phead){assert(phead);ListNode* cur = phead;while (cur != phead){ListNode* next = cur->next;free(cur);cur = NULL;cur = next;}}

具体选择哪一种，需要看实际需要！！！

12.完整代码：

（1）List.h文件：

#define _CRT_SECURE_NO_WARNINGS 1#pragma once#include#include#includetypedef int LTDataType;typedef struct ListNode{struct ListNode* prev;LTDataTypedata;struct ListNode* next;}ListNode;ListNode* ListNodeBuy(LTDataType x);void ListNodeInit(ListNode** pphead);void ListPrint(ListNode* phead);void ListNodePushBack(ListNode* phead, LTDataType x);void ListNodePopBack(ListNode* phead);void ListNodePushFront(ListNode* phead, LTDataType x);void ListNodePopFront(ListNode* phead);ListNode* ListNodeFind(ListNode* phead, LTDataType x);void ListNodeInsert(ListNode* pos, LTDataType x);void ListNodeErase(ListNode* pos);void ListNodeDestroy(ListNode* phead);

（2）List.c文件：

#include"List.h"#define _CRT_SECURE_NO_WARNINGS 1ListNode* ListNodeBuy(LTDataType x){ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));newnode->next = NULL;newnode->prev = NULL;newnode->data=x;return newnode;}void ListNodeInit(ListNode** pphead){*pphead = ListNodeBuy(0);(* pphead)->next = *pphead;(*pphead)->prev = *pphead;}ListNode* ListNodeInit(){ListNode* phead = ListNodeBuy(0);phead->next = phead;phead->prev = phead;return phead;}void ListPrint(ListNode* phead){assert(phead);ListNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");}void ListNodePushBack(ListNode* phead, LTDataType x){assert(phead);ListNode* tail = phead->prev;ListNode* newnode = ListNodeBuy(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}void ListNodePopBack(ListNode* phead){assert(phead);assert(phead->next != phead);ListNode* tail = phead->prev;ListNode* tail_prev = tail->prev;tail_prev->next = phead;phead->prev = tail_prev;free(tail);tail = NULL;}void ListNodePushFront(ListNode* phead, LTDataType x){assert(phead);ListNode* first = phead->next;ListNode* newnode = ListNodeBuy(x);phead->next = newnode;newnode->next = first;newnode->prev = phead;first->prev = newnode;}void ListNodePopFront(ListNode* phead){assert(phead);assert(phead->next != phead);ListNode* first = phead->next;ListNode* second = first->next;phead->next = second;second->prev = phead;free(first);first = NULL;}ListNode* ListNodeFind(ListNode* phead, LTDataType x){assert(phead);ListNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;}void ListNodeInsert(ListNode* pos, LTDataType x){assert(pos);ListNode* pos_prev = pos->prev;ListNode* newnode = ListNodeBuy(x);newnode->next = pos;pos->prev = newnode;pos_prev->next = newnode;newnode->prev = pos_prev;}void ListNodeErase(ListNode* pos){assert(pos);ListNode* pos_prev = pos->prev;ListNode* next = pos->next;free(pos);pos = NULL;pos_prev->next = next;next->prev = pos_prev;}void ListNodeDestroy(ListNode* phead){assert(phead);ListNode* cur = phead;while (cur != phead){ListNode* next = cur->next;free(cur);cur = NULL;cur = next;}}

（3）test.c文件：

#include"List.h"#define _CRT_SECURE_NO_WARNINGS 1int main(void){ListNode* phead = NULL;ListNodeInit(&phead);/*ListNodePushBack(phead, 1);ListNodePushBack(phead, 2);ListNodePushBack(phead, 3);ListNodePushBack(phead, 4);ListNodePushBack(phead, 5);ListNodePushBack(phead, 6);ListPrint(phead);ListNodePopBack(phead, 1);ListNodePopBack(phead, 2);ListNodePopBack(phead, 3);ListNodePopBack(phead, 4);ListNodePopBack(phead, 5);ListPrint(phead);*/ListNodePushFront(phead, 1);ListNodePushFront(phead, 2);ListNodePushFront(phead, 3);ListNodePushFront(phead, 4);ListNodePushFront(phead, 5);ListNodePushFront(phead, 6);ListPrint(phead);/*ListNodePopFront(phead, 1);ListNodePopFront(phead, 2);ListNodePopFront(phead, 3);ListNodePopFront(phead, 4);ListNodePopFront(phead, 5);ListPrint(phead);*/ListNode* pos = ListNodeFind(phead,3);pos->data = 300;ListPrint(phead);ListNodeInsert(pos, 1);ListPrint(phead);ListNodeErase(pos);ListPrint(phead);ListNodeDestroy(phead);return 0;}

最后

十分感谢你可以耐着性子把它读完和我可以坚持写到这里，送几句话，对你，也对我：

1.也许你要早上七点起床，晚上十二点睡觉,日复一日，踽踽独行。但只要笃定而努力地活着，即使生不逢时，你人生最坏的结果，也只是大器晚成。
2.这个世界根本不存在“不会”这回事。当你失去所有依靠的时候，你自然就什么都会了。
3.当你足够优秀时，你周围的一切自然都会好起来。
4.人一旦堕落，哪怕是短暂的几年，上帝就会以最快的速度，收走你的天赋和力量。5.你所做的事情，也许暂时看不到成果，但不要灰心或焦虑，你不是没有成长，而是在扎根。

最后如果觉得我写的还不错，请不要忘记点赞✌，收藏✌，加关注✌哦(｡･ω･｡)

愿我们一起加油，奔向更美好的未来，愿我们从懵懵懂懂的一枚菜鸟逐渐成为大佬。加油，为自己点赞！
​

​