C语言数据结构——详细讲解 双链表

从单链表到双链表:数据结构的演进与优化

  • 前言
  • 一、单链表回顾
  • 二、单链表的局限性
  • 三、什么是双链表
  • 四、双链表的优势
    • 1.双向遍历
    • 2.不带头双链表的用途
    • 3.带头双链表的用途
  • 五、双链表的操作
    • 双链表的插入操作
      • (一)双链表的尾插操作
      • (二)双链表的头插操作
      • (三)双链表在指定位置之后插入数据
    • 双链表的删除操作
      • (一)双链表的尾删操作
      • (二)双链表的头删操作
      • (三)双链表删除指定位置数据


前言

         在数据结构的广袤天地里,链表作为一种重要的线性数据结构,以其独特的存储方式和灵活的操作特性,在众多编程场景中发挥着关键作用。今天,我们就来深入探讨一下从单链表双链表的发展历程,看看双链表是如何在单链表的基础上应运而生,并解决了单链表所面临的一些问题


一、单链表回顾

  • 首先,我们来回顾一下单链表的基本结构。单链表是由一系列节点组成的数据结构,每个节点包含两部分数据域指针域数据域用于存储具体的数据指针域则存储指向下一个节点的指针,通过这样的指针链接,各个节点依次相连,形成了一条链表。
  • 单链表不带头单向不循环,是链表结构中较为基础的一种形式,与带头节点的单链表不同不带头节点的单链表在进行操作时,第一个节点就直接存储了实际的数据,没有专门设置一个额外的头节点来简化某些操作逻辑。

以下是带头单链表和不带头单链表的图片

在这里插入图片描述
在这里插入图片描述

以上这些图片均表示单链表

  • 例如,我们有一个简单的单链表存储整数数据,节点结构可以定义如下
typedef struct ListNode 
{int data;struct ListNode *next;
} ListNode;
  • 单链表很多场景下都非常有用,它能够方便地进行动态内存分配实现数据的灵活存储操作,比如插入删除节点等操作相对数组来说更加灵活,不需要移动大量元素

二、单链表的局限性

  • 然而,单链表也存在一些局限性:
  • 单向遍历

单链表的指针只能指向一个方向,也就是只能从表头顺着指针依次访问到表尾的节点

  • 删除操作的不便:

当我们想要删除单链表中的某个节点时,如果只知道要删除节点的指针(而不是它的前驱节点指针),操作起来会比较麻烦,,往往需要从头开始遍历链表去找到前驱节点,这同样会影响操作的效率。

为了克服单链表的这些局限性,我们就引入了双链表

在这里插入图片描述

三、什么是双链表

  • 双链表的每个节点除了包含数据域和指向下一个节点的指针域外还增加了一个指向前一个节点的指针域。也就是说,双链表的节点结构可以定义如下:

在这里插入图片描述

typedef struct DoublyListNode 
{int data;struct DoublyListNode *prev;struct DoublyListNode *next;
} DoublyListNode;
  • 在这个结构中,**prev 指针指向当前节点的前一个节点,next 指针指向当前节点的下一个节点。**这样一来,双链表就具备了双向遍历的能力。

双链表可以分为带头节点和不带头结点

  • 不带头节点的双链表
    在这里插入图片描述
  • 结构特点:

1.链表的第一个节点就直接存储实际的数据元素,不存在一个专门作为 “头” 的额外节点。
2.每个节点除了数据域外,有两个指针域,一个指向前驱节点(prev 指针),一个指向后继节点(next 指针)

  • 带头结点的双链表
    在这里插入图片描述

  • 结构特点:

1.有一个专门的头节点,这个头节点的数据域一般不存储实际的数据(当然也可以根据具体需求赋予特殊含义,但通常为空数据域),主要作用是方便链表的各种操作。
2.头节点同样有两个指针域,prev 指针一般指向 NULL(因为它是表头,前面没有节点了),next 指针指向链表中的第一个实际存储数据的节点。

四、双链表的优势

1.双向遍历

从表头到表尾遍历:和单链表类似,我们可以通过每个节点的 next 指针依次访问后续节点,从而实现从表头到表尾的遍历。

  • 删除操作的便利性

在双链表中删除一个节点就变得更加容易了。假设我们要删除节点 p,我们可以直接通过 p 的 prev 和 next 指针来完成删除操作,而不需要像单链表那样去专门寻找它的前驱节点

总结一下带头和不带头有什么用

2.不带头双链表的用途

  • 节省内存空间:

每一个节点都实实在在地用于存储数据及相关指针,不存在一个仅为了方便操作而占据空间但通常不存储实际有效数据的头节点。

  • 体现数据原始性

3.带头双链表的用途

  • 简化操作逻辑:
  • 插入 无论是头插、尾插还是指定位置插入,由于有头节点的存在,不需要针对链表为空的情况单独设计特殊的处理逻辑。

  • 删除 进行头删、尾删或指定位置删除时,操作逻辑相对统一,不用特别考虑链表为空时删除操作的特殊变化。

  • 遍历 遍历链表时,从头节点的下一个节点开始顺着 next 指针向后遍历(正向遍历)以及从链表末尾顺着 prev 指针向前遍历(反向遍历)的逻辑较为清晰、简单,不用像不带头双链表那样,正向遍历要从第一个实际存储数据的节点开始,反向遍历要先找到末尾节点。

五、双链表的操作

双链表的插入操作

(一)双链表的尾插操作

void LTTPushFront(LTNode* head, int x)
{assert(head);LTNode* newnode = new LTNode;newnode->data = x;newnode->next = head;head = newnode;// 打印链表printList(head);
}
  • head 为双链表的头结点
  • x为要插入的数值

插入节点的步骤

  • LTNode* newnode = new LTNode创建新节点
  • newnode->data = x初始化新节点的数据
  • newnode->next = head
  • 这行代码将新节点的next指针指向当前的头节点head。这样,新节点就指向了原来的第一个节点
  • head = newnode
  • 这行代码将头节点head更新为新节点newnode。这样,新节点就成为了链表的新头节点。

(二)双链表的头插操作

// 头插操作
void LTPushFront(LTNode* head, int x) 
{assert(head);LTNode* newnode = buyNode(x);newnode->next = head->next;newnode->prev = head;head->next->prev = newnode;head->next = newnode;
}
  • newnode->next = head->next;
  • newnode->prev = head;
  • 第一行代码将新节点newnode的next指针指向当前头节点head的下一个节点(即原来链表中的第一个节点)。
  • 第二行代码将新节点newnode的prev指针指向头节点head
  • head->next->prev = newnode;
  • 将原来链表中第一个节点(即head->next)的prev指针指向新节点newnode。这一步是为了让原来的第一个节点知道它的前一个节点变成了新节点
  • head->next = newnode;
  • 将头节点head的next指针指向新节点newnode。这一步是为了让头节点指向新插入的节点,从而使新节点成为链表中的第一个节点

(三)双链表在指定位置之后插入数据

// 在pos位置之后插入数据
void LTInsert(LTNode* pos, int x) {assert(pos);LTNode* newnode = buyNode(x);newnode->next = pos->next;newnode->prev = pos;if (pos->next) {pos->next->prev = newnode;}pos->next = newnode;
}
  • newnode->next = pos->next;:
  • 将新节点newnode的next指针指向pos节点的下一个节点。
  • newnode->prev = pos;
  • 将新节点newnode的prev指针指向pos节点
  • if (pos->next) { pos->next->prev = newnode; }:
  • 如果pos节点有下一个节点(即pos->next不为NULL),那么将pos的下一个节点的prev指针指向新节点newnode。
  • 这一步是为了保持双链表的双向连接关系
  • 最后将pos节点的next指针指向新节点newnode,完成新节点在pos节点之后的插入操作

双链表的删除操作

(一)双链表的尾删操作

// 尾删
void LTPopBack(LTNode* head) 
{assert(!LTEmpty(head));LTNode* del = head->prev;LTNode* prev = del->prev;prev->next = head;head->prev = prev;delete del;
}
  • LTNode* del = head->prev;
  • 双链表通常有一个头节点,尾节点是头节点的前一个节点,所以这里head->prev就是尾节点,将其赋值给del
  • LTNode* prev = del->prev;,找到尾节点del的前一个节点prev
  • prev->next = head;,将尾节点的前一个节点的next指针指向头节点,这样就把尾节点从链表中移除了。
  • head->prev = prev;,同时更新头节点的prev指针指向新的尾节点(原来尾节点的前一个节点)

(二)双链表的头删操作

// 头删操作
void LTpopFront(LTNode* head) {assert(!LTEmpty(head));LTNode* del = head->next;head->next = del->next;if (del->next) {del->next->prev = head;}delete del;
}
  • LTNode* del = head->next;头节点的下一个节点就是要删除的第一个数据节点,将其赋值给del
  • head->next = del->next;,将头节点的next指针指向要删除节点del的下一个节点,这样就把del从链表中移除了。
  • if (del->next) { del->next->prev = head; },如果del有下一个节点(即del不是尾节点),那么将del的下一个节点的prev指针指向头节点

(三)双链表删除指定位置数据

// 删除指定位置数据
void LTEarse(LTNode* pos) {assert(pos);pos->prev->next = pos->next;if (pos->next) {pos->next->prev = pos->prev;}delete pos;
}
  • pos->prev->next = pos->next;,将pos节点的前一个节点的next指针指向pos节点的下一个节点,这样就把pos从链表中移除了。
  • if (pos->next) { pos->next->prev = pos->prev; },如果pos有下一个节点,那么将pos的下一个节点的prev指针指向pos的前一个节点
文章到这里就结束了,感谢你的阅读,喜欢的话记得三连

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/476672.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

ElasticSearch学习篇18_《检索技术核心20讲》LevelDB设计思想

目录 一些常见的设计思想以及基于LSM树的LevelDB是如何利用这些设计思想优化存储、检索效率的。 几种常见的设计思想 索引和数据分离减少磁盘IO读写分离分层思想 LevelDB的设计思想 读写分离设计分层设计与延迟合并LRU缓存加速检索 几种常见设计思想 索引与数据分离 索引…

JavaWeb之综合案例

前言 这一节讲一个案例 1. 环境搭建 然后就是把这些数据全部用到sql语句中执行 2.查询所有-后台&前台 我们先写后台代码 2.1 后台 2.2 Dao BrandMapper: 注意因为数据库里面的名称是下划线分割的,我们类里面是驼峰的,所以要映射 …

043 商品详情

文章目录 详情页数据表结构voSkuItemVo.javaSkuItemSaleAttrVo.javaAttrValueAndSkuIdVo.javaSpuAttrGroupVo.javaGroupAttrParamVo.java pom.xmlSkuSaleAttrValueDao.xmlSkuSaleAttrValueDao.javaAttrGroupDao.xmlAttrGroupServiceImpl.javaSkuInfoServiceImpl.javaSkuSaleAtt…

Django启用国际化支持(2)—实现界面内切换语言:activate()

文章目录 ⭐注意⭐1. 配置项目全局设置:启用国际化2. 编写视图函数3. 配置路由4. 界面演示5、扩展自动识别并切换到当前语言设置语言并保存到Session设置语言并保存到 Cookie ⭐注意⭐ 以下操作依赖于 Django 项目的国际化支持。如果你不清楚如何启用国际化功能&am…

中国省级新质生产力发展指数数据(任宇新版本)2010-2023年

一、测算方式:参考C刊《财经理论与实践》任宇新(2024)老师的研究,新质生产力以劳动者劳动资料劳动对象及其优化组合的质变为 基本内涵,借 鉴 王 珏 和 王 荣 基 的 做 法构建新质生产力发展水平评价指标体系如下所示&a…

设计模式之 状态模式

状态模式(State Pattern)是一种行为型设计模式,它允许一个对象在其内部状态改变时,改变其行为。这种模式将状态的转换和行为的变化解耦,将不同状态的行为封装到独立的状态类中,而通过上下文(Con…

学习日志015--python单链表

创建 class Node:def __init__(self,data):# 数据域self.data data# 链接域self.next Noneclass LinkList:def __init__(self,):# 初始化头节点self.head None# 记录链表的长度self.size 0 增加 #头插def insert_head(self,value):# 创建新节点node Node(value)q self…

CSP/信奥赛C++语法基础刷题训练(22):洛谷P1075:[NOIP2012 普及组] 质因数分解

CSP/信奥赛C语法基础刷题训练(22):洛谷P1075:[NOIP2012 普及组] 质因数分解 题目描述 已知正整数 n n n 是两个不同的质数的乘积,试求出两者中较大的那个质数。 输入格式 输入一个正整数 n n n。 输出格式 输出…

Java开发经验——开发常用工具类

摘要 本文介绍了Java开发中常用的工具类,包括Apache Commons Collections的SetUtils、Google Guava的Sets、Apache Commons Lang的ArrayUtils等,以及它们在集合操作、数组操作、字符串处理、JSON处理等方面的应用。文章还涉及了Optional类、Money工具类…

【Python TensorFlow】进阶指南(续篇三)

在前几篇文章中,我们探讨了TensorFlow的高级功能,包括模型优化、分布式训练、模型解释等多个方面。本文将进一步深入探讨一些更具体和实用的主题,如模型持续优化的具体方法、异步训练的实际应用、在线学习的实现细节、模型服务化的最佳实践、…

阿里系 acw_sc__v3 某教学网站

声明: 本文章中所有内容仅供学习交流使用,不用于其他任何目的,抓包内容、敏感网址、数据接口等均已做脱敏处理,严禁用于商业用途和非法用途,否则由此产生的一切后果均与作者无关! 有相关问题请第一时间头像私信联系我删…

1、HCIP之RSTP协议与STP相关安全配置

目录 RSTP—快速生成树协议 STP STP的缺点: STP的选举(Listening状态中): RSTP P/A(提议/同意)机制 同步机制: 边缘端口的配置: RSTP的端口角色划分: ensp模拟…

ChatGPT 与其他 AI 技术在短视频营销中的技术应用与协同策略

摘要: 本文深入探讨了 ChatGPT 及其他 AI 技术在短视频营销中的应用。从技术层面剖析了这些技术如何助力短视频内容创作、个性化推荐、用户互动以及营销效果评估等多方面,通过具体方法分析、数据引用与大模型工具介绍,旨在为短视频营销领域提…

数据结构-树状数组专题(2)

一、前言 接上回树状数组专题&#xff08;1&#xff09;&#xff0c;这次主要介绍差分跟树状数组联动实现区间更新 二、我的模板 重新放了一遍&#xff0c;还是提一嘴&#xff0c;注意下标从0开始&#xff0c;区间左闭右开 template <typename T> struct Fenwick {in…

使用 PyTorch-BigGraph 构建和部署大规模图嵌入的完整教程

当涉及到图数据时&#xff0c;复杂性是不可避免的。无论是社交网络中的庞大互联关系、像 Freebase 这样的知识图谱&#xff0c;还是推荐引擎中海量的数据量&#xff0c;处理如此规模的图数据都充满挑战。 尤其是当目标是生成能够准确捕捉这些关系本质的嵌入表示时&#xff0c;…

启动前后端分离项目笔记

一、项目 首先可以在各大开源软件拿取一个项目&#xff0c;以下项目是在gitee上获取 二、准备工作 配置JDK环境&#xff0c;node.js环境&#xff0c;安装vue脚手架工具以及maven环境 三、前端项目启动 在前端目录下安装依赖 npm install 如果报错可能是因为权限不够&#…

3个月,2000+台虚机迁移成功!

在全球数字化浪潮的推动下&#xff0c;各国政务部门纷纷加速信息化与数字化转型&#xff0c;以提升服务效率和数据安全。在这一背景下&#xff0c;墨西哥某政府部门因迅速增长的政务数字化需求&#xff0c;选择与华为云合作&#xff0c;构建专属的政务私有云平台。 经过多方尝…

GRU (门控循环单元 - 基于RNN - 简化LSTM又快又好 - 体现注意力的思想) + 代码实现 —— 笔记3.5《动手学深度学习》

目录 0. 前言 1. 门控隐状态 1.1 重置门和更新门 1.2 候选隐状态 1.3 隐状态 2. 从零开始实现 2.1 初始化模型参数 2.2 定义模型 2.3 训练与预测 3 简洁实现 4. 小结 0. 前言 课程全部代码&#xff08;pytorch版&#xff09;已上传到附件看懂上一篇RNN的所有细节&am…

微知-plantuml常用语法和要点以及模板?(note over、create、box,endbox、alt,else,end, autonumber)

文章目录 常见语法常用 线条类实线虚线斜箭头或奇数箭头 A ->(10) B: B->(10) A分割线&#xff1a;newpage 颜色类给箭头指定颜色 -[#red]->给某个note加颜色&#xff1a; note over Alice, Bob #FFAAAA: xxx给分组信息着色 alt#red 分组类alt xxx; else xxx; else xx…

YOLOV5/rknn生成可执行文件部署在RK3568上

接上一篇文章best-sim.rknn模型生成好后&#xff0c;我们要将其转换成可执行文件运行在RK3568上&#xff0c;这一步需要在rknpu上进行&#xff0c;在强调一遍&#xff01;&#xff01;rknpu的作用是可以直接生成在开发板上运行的程序 退出上一步的docker环境 exit1.复制best-…