AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

双向链表增删查改详解及完整代码

2023-02-24 73
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 双向链表增删查改详解及完整代码
🌹作者:云小逸
📝个人主页: 云小扬的主页
📝码云： 云小扬 (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.你所做的事情，也许暂时看不到成果，但不要灰心或焦虑，你不是没有成长，而是在扎根。

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

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

​

文章标签：
C++
C语言
Linux
算法
存储
关键词：
链表代码
链表增删查改代码
云-小逸
目录
相关文章
修修修也
|
6月前
|
存储 编译器 C语言
【数据结构】C语言实现带头双向循环链表万字详解(附完整运行代码)
【数据结构】C语言实现带头双向循环链表万字详解(附完整运行代码)
修修修也
54 0
aliyun9861394983-11302
|
6月前
【数据结构】数组、双链表代码实现
【数据结构】数组、双链表代码实现
aliyun9861394983-11302
50 0
小徐在进步
|
2月前
|
存储 算法 C语言
C语言手撕实战代码_循环单链表和循环双链表
本文档详细介绍了用C语言实现循环单链表和循环双链表的相关算法。包括循环单链表的建立、逆转、左移、拆分及合并等操作；以及双链表的建立、遍历、排序和循环双链表的重组。通过具体示例和代码片段，展示了每种算法的实现思路与步骤，帮助读者深入理解并掌握这些数据结构的基本操作方法。
小徐在进步
36 2
邢仕冲的一亩三分地
|
5月前
|
存储 算法
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
邢仕冲的一亩三分地
45 4
wan__cheng
|
6月前
|
存储
实现双链表的增删查改
实现双链表的增删查改
wan__cheng
31 0
天玑y
|
6月前
leetcode代码记录（移除链表元素
leetcode代码记录（移除链表元素
天玑y
29 0
只是雪豹
|
6月前
|
存储
链表的实现（文末附完整代码）
链表的实现（文末附完整代码）
只是雪豹
49 2
颦颦Admin@123
|
6月前
|
存储
数据结构基础：一篇文章教你单链表（头插，尾插，查找，头删等的解析和代码）
数据结构基础：一篇文章教你单链表（头插，尾插，查找，头删等的解析和代码）
颦颦Admin@123
57 0
东方睿赢
|
6月前
在实现链表的代码中，为什么要使用继承而不是组合？
在实现链表的代码中，为什么要使用继承而不是组合？
东方睿赢
35 3
东方睿赢
|
6月前
|
设计模式 测试技术
在实现链表的代码中，为什么要使用`Node`类而不是直接在`LinkedList`类中定义节点？
在实现链表的代码中，为什么要使用`Node`类而不是直接在`LinkedList`类中定义节点？
东方睿赢
47 1