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

@TOC

前言

今天我们来聊一聊：数据结构中链表的双向循环带头链表，对于第一次听到双向循环带头链表的同学，可能会认为双向循环带头链表是==十分复杂==的，的确双向循环带头链表的结构是有点复杂，但是它的操作是非常简单的，非常便于操作，那么现在就由==云小逸==带你了解认识学习==双向循环带头链表==。
——————————————————————————————
首先先写上几句话：献给坚持创作的我和点开这篇文章希望进步的你

1.世人慌慌张张，不过是图碎银几两。偏偏这碎银几两，能解世间惆怅，可让父母安康，可护幼子成长，但这碎银几两，==也断了儿时念想，让少年染上沧桑，压弯了脊梁==

2.暂时抛去心灵深处的空洞与匮乏，沏一杯淡淡的茶，斜阳层层，叠叠的洒在桌面上，有那么一瞬间，好像忘记了曾经的阴霾和受过的伤。林徽因说过:“==温柔要有，但不是妥协，我们要在不慌不忙中安静的坚强。==″

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是否为NULL
    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;
}

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是否为NULL
    assert(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<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDataType;
typedef struct ListNode
{
    struct ListNode* prev;
    LTDataType  data;
    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 1
ListNode* 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 1
int 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.你所做的事情，也许暂时看不到成果，但不要灰心或焦虑，你不是没有成长，而是在扎根。

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

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

​