【数据结构】双链表的定义和操作

这篇具有很好参考价值的文章主要介绍了【数据结构】双链表的定义和操作。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【数据结构】双链表的定义和操作,数据结构与算法,数据结构,笔记,c++,c语言,学习,青少年编程,改行学it

目录

1.双链表的定义

2.双链表的创建和初始化

3.双链表的插入节点操作

4.双链表的删除节点操作

5.双链表的查找节点操作

6.双链表的更新节点操作

7.完整代码


🌈嗨!我是Filotimo__🌈。很高兴与大家相识,希望我的博客能对你有所帮助。

💡本文由Filotimo__✍️原创,首发于CSDN📚。

📣如需转载,请事先与我联系以获得授权⚠️。

🎁欢迎大家给我点赞👍、收藏⭐️,并在留言区📝与我互动,这些都是我前进的动力!

🌟我的格言:森林草木都有自己认为对的角度🌟。

【数据结构】双链表的定义和操作,数据结构与算法,数据结构,笔记,c++,c语言,学习,青少年编程,改行学it

【数据结构】双链表的定义和操作,数据结构与算法,数据结构,笔记,c++,c语言,学习,青少年编程,改行学it

1.双链表的定义

双链表是一种常见的数据结构,它由一系列节点组成,每个节点包含两个指针,一个指向前一个节点,另一个指向后一个节点。与单链表不同的是,双链表的节点可以双向访问,因此可以在任意位置快速插入、删除和查找元素。

一个双链表通常包含以下属性和操作:
头节点(head):指向第一个节点的指针。
尾节点(tail):指向最后一个节点的指针。
节点(node):包含数据和两个指针的数据单元。
插入(insert):在指定位置插入一个新的节点。
删除(delete):删除指定位置的节点。
查找(search):根据给定的值查找节点。
遍历(traverse):按顺序访问链表中的每个节点。

2.双链表的创建和初始化

创建一个双链表需要定义一个结构体,包含数据域和前后指针域。初始化时要注意将头结点的前后指针均指向 NULL。

struct DNode {
    int data;  //数据域
    struct DNode *prior;  //前驱指针域
    struct DNode *next;   //后继指针域
};

struct DNode *createList() {
    struct DNode *head = (struct DNode*)malloc(sizeof(struct DNode));
    head->prior = NULL;
    head->next = NULL;
    return head;
}

定义结构体struct DNode表示双向链表的节点。
该节点包括三个成员变量:
int data表示节点的数据域,可以存储整数类型的数据。
struct DNode *prior表示指向前一个节点的指针域。
struct DNode *next表示指向后一个节点的指针域。

在createList函数内部,首先通过malloc函数动态分配了一块内存,大小为一个struct DNode结构体的大小。然后将分配的内存强制转换为struct DNode*类型,并将其赋值给head指针变量,作为链表的头节点。

3.双链表的插入节点操作

在插入节点时,需要将新节点插入到某个节点之前或之后,通过修改前后指针实现。具体操作分为两步,先将新节点的前后指针赋值,然后修改它前后节点的指针。需要注意判断特殊情况,如插入到空链表、插入到头结点等。

void insertNode(struct DNode *p, int data) {
    if (p == NULL) return;
    struct DNode *newNode = (struct DNode*)malloc(sizeof(struct DNode));
    newNode->data = data;
    newNode->prior = p;
    newNode->next = p->next;
    if (p->next != NULL) p->next->prior = newNode;
    p->next = newNode;
}

函数insertNode接受两个参数:指向双向链表结点的指针p和要插入的数据data。

如果p不为空,则创建一个新的双向链表结点newNode,通过malloc函数动态分配内存。然后,将新节点的data字段设置为传入的data值。再将新节点的prior字段设置为指向p,将新节点的next字段设置为指向p->next。

检查p的下一个结点是否为空,如果不为空,则将下一个结点的prior字段指向新节点newNode。最后将p的next指针指向新结点newNode,完成插入操作。这样,插入操作就将新节点插入到了链表中p结点之后的位置。

4.双链表的删除节点操作

在删除节点时,需先找到要删除的节点,然后修改前后节点的指针。在执行 free 操作后,需要将指针置为 NULL,避免出现野指针。

void deleteNode(struct DNode *p) {
    if (p == NULL) return;
    p->prior->next = p->next;
    if (p->next != NULL) p->next->prior = p->prior;
    free(p);
    p = NULL;
}

如果p不为空,将p结点的前驱结点的next指针指向p结点的后继结点,断开p结点与前后结点的连接。即p->prior->next = p->next。

检查p结点的后继结点是否为空,如果不为空,则将后继结点的前驱指针指向p结点的前驱结点,断开p结点与后继结点的连接。即p->next->prior = p->prior。

使用free函数释放了指针p指向的内存,将p结点从链表中删除。

将指针p设置为NULL,确保不再引用已经删除的结点。

5.双链表的查找节点操作

查找节点时,可以采用遍历的方法进行查找。需要注意判断特殊情况,如链表为空等。

struct DNode *findNode(struct DNode *head, int data) {
    if (head == NULL) return NULL;
    struct DNode *p = head->next;
    while (p != NULL) {
        if (p->data == data) return p;
        p = p->next;
    }
    return NULL;
}

如果head不为空,代码将p指针初始化为head结点的下一个结点,即head->next。

使用while循环遍历链表,如果指针p指向的结点的data字段等于要查找的数据data,则直接返回该结点的指针p,表示查找成功。

如果没有查找到要找的数据,即p到达链表结尾指针为NULL,则返回NULL,表示查找失败。

6.双链表的更新节点操作

更新节点操作与单链表类似,具体步骤为先查找要更新的节点,然后修改其数据域的值即可。

void updateNode(struct DNode *p, int newData) {
    if (p != NULL) {
        p->data = newData;
    }
}

首先检查指针p是否为空,如果不为空,则将指针p所指向的结点的data字段更新为新的数据newData。如果结点p为空,则不进行任何操作。

7.完整代码

#include <stdio.h>
#include <stdlib.h>

//双链表结构体定义
struct DNode {
    int data;  //数据域
    struct DNode *prior;  //前驱指针域
    struct DNode *next;   //后继指针域
};

//创建双链表
struct DNode *createList() {
    struct DNode *head = (struct DNode*)malloc(sizeof(struct DNode));
    head->prior = NULL;
    head->next = NULL;
    return head;
}

//插入节点
void insertNode(struct DNode *p, int data) {
    if (p == NULL) return;
    struct DNode *newNode = (struct DNode*)malloc(sizeof(struct DNode));
    newNode->data = data;
    newNode->prior = p;
    newNode->next = p->next;
    if (p->next != NULL) p->next->prior = newNode;
    p->next = newNode;
}

//删除节点
void deleteNode(struct DNode *p) {
    if (p == NULL) return;
    p->prior->next = p->next;
    if (p->next != NULL) p->next->prior = p->prior;
    free(p);
    p = NULL;
}

//查找节点
struct DNode *findNode(struct DNode *head, int data) {
    if (head == NULL) return NULL;
    struct DNode *p = head->next;
    while (p != NULL) {
        if (p->data == data) return p;
        p = p->next;
    }
    return NULL;
}

//更新节点
void updateNode(struct DNode *p, int newData) {
    if (p != NULL) {
        p->data = newData;
    }
}

//遍历双链表
void traverseList(struct DNode *head) {
    if (head == NULL) return;
    struct DNode *p = head->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

//测试双链表
int main() {
    struct DNode *head = createList();  //创建链表

    //插入节点
    insertNode(head, 1);
    insertNode(head, 2);
    insertNode(head, 3);
    insertNode(head, 4);

    traverseList(head);  //遍历链表

    struct DNode *p = findNode(head, 2);  //查找节点
    if (p != NULL) {
        printf("Found node: %d\n", p->data);
        updateNode(p, 5);  //更新节点
        printf("After updated, the list is:\n");
        traverseList(head);  //遍历链表
    }

    deleteNode(findNode(head, 3)); //删除节点
    printf("After deleted, the list is:\n");
    traverseList(head);  //遍历链表

    return 0;
}

输出结果如下:

【数据结构】双链表的定义和操作,数据结构与算法,数据结构,笔记,c++,c语言,学习,青少年编程,改行学it文章来源地址https://www.toymoban.com/news/detail-778104.html

到了这里,关于【数据结构】双链表的定义和操作的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】顺序表的定义和操作

    目录 1.初始化 2.插入 3.删除 4.查找 5.修改 6.长度 7.遍历 8.完整代码 🌈嗨!我是Filotimo__🌈。很高兴与大家相识,希望我的博客能对你有所帮助。 💡本文由Filotimo__✍️原创,首发于CSDN📚。 📣如需转载,请事先与我联系以获得授权⚠️。 🎁欢迎大家给我点赞👍、收藏⭐️

    2024年02月03日
    浏览(50)
  • 【数据结构】单链表的定义和操作

    目录 1.单链表的定义 2.单链表的创建和初始化 3.单链表的插入节点操作 4.单链表的删除节点操作 5.单链表的查找节点操作 6.单链表的更新节点操作 7.完整代码 🌈嗨!我是Filotimo__🌈。很高兴与大家相识,希望我的博客能对你有所帮助。 💡本文由Filotimo__✍️原创,首发于CS

    2024年02月02日
    浏览(56)
  • 数据结构之双链表的相关知识点及应用

     找往期文章包括但不限于本期文章中不懂的知识点: 个人主页 :我要学编程(ಥ_ಥ)-CSDN博客 所属专栏 :数据结构 目录 双链表的实现  初始化双链表  在双链表中尾插数据  在双链表中尾删数据 在双链表中头插数据  在双链表中头删数据  在双链表中的指定位置之后插入

    2024年04月26日
    浏览(53)
  • [C语言][数据结构][链表] 双链表的从零实现!

    目录 零.必备知识 0.1 一级指针 二级指针 0.2 双链表节点的成员列表         a. 数据         b. 后驱指针         c. 前驱指针 0.3 动态内存空间的开辟 一. 双链表的实现与销毁         1.1 节点的定义         1.2 双向链表的初始化 创建新节点         1.3 尾插       

    2024年04月17日
    浏览(245)
  • Java 数据结构篇-实现双链表的核心API

    🔥博客主页:  小扳_-CSDN博客 ❤感谢大家点赞👍收藏⭐评论✍       文章目录         1.0 双链表的说明         1.1 双链表 - 创建         1.2 双链表 - 根据索引查找节点         1.3 双链表 - 根据索引插入节点         1.4 双链表 - 头插节点         1.5 双链表 - 尾插

    2024年02月04日
    浏览(59)
  • 数据结构 2.1 线性表的定义和基本操作

    数据结构三要素——逻辑结构、数据的运算、存储结构(物理结构) 线性表是具有 相同数据类型 的n(n=0)个数据元素的 有限序列 ,其中n为表长,当n=0时,线性表是一个空表。 每个数据元素所占空间一样大,有次序。 几个概念 1.ai是线性表中的第i个 i表示元素线性表中的

    2024年02月07日
    浏览(53)
  • 数据结构 线性表的定义和基本操作(以顺序表为例)

    名人说:一花独放不是春,百花齐放花满园。——《增广贤文》 作者:Code_流苏(CSDN) (一个喜欢古诗词和编程的Coder😊) 以下代码个人分享出来,仅供学习交流,且仅在CSDN平台发布,未经授权禁止二次转发。 〇、线性表是什么? 1、定义 线性表 是具有 相同数据类型 的 n(

    2024年02月12日
    浏览(63)
  • 【玩转408数据结构】线性表——双链表、循环链表和静态链表(线性表的链式表示 下)

            在前面的学习中,我们已经了解到了链表(线性表的链式存储)的一些基本特点,并且深入的研究探讨了单链表的一些特性,我们知道,单链表在实现插入删除上,是要比顺序表方便的,但是,单链表中每个结点仅存在一个指针指向其后续结点,那么如果我们想要找

    2024年04月10日
    浏览(61)
  • 【数据结构】线性表(一)线性表的定义及其基本操作(顺序表插入、删除、查找、修改)

    目录 一、线性表 1. 线性表的定义 2. 线性表的要素 二、线性表的基本操作 三、线性表的顺序存储结构 1. 定义 2. 顺序表的操作       a. 插入操作 b. 删除操作 c. 查找操作 d. 修改操作 e. 代码实例          一个线性表是由零个或多个 具有相同类型的结点 组成的有序集合。

    2024年02月03日
    浏览(70)
  • 双链表——“数据结构与算法”

    各位CSDN的uu们你们好呀,今天,小雅兰又回来了,到了好久没有更新的数据结构与算法专栏,最近确实发现自己有很多不足,需要学习的内容也有很多,所以之后更新文章可能不会像之前那种一天一篇或者一天两篇啦,话不多说,下面,让我们进入双链表的世界吧  之前小雅

    2024年02月04日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包