嵌入式学习(双向链表)

2024-09-04 22:44
文章标签 学习 链表 双向 嵌入式

本文主要是介绍嵌入式学习(双向链表),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在我们使用链表存储数据时,往往会从堆空间上申请空间。因此在使用完之后需要我们手动释放空间。

valgrind工具可以帮助我们检测在一段进程中申请的空间是否被释放完全。

在使用时:

valgrind  +  运行文件  :如  valgrind  ./a.out

双向链表

主要结构是由prev、next、data,这三个结构组成,通过prev找到前一个节点,next指向下一个节点。

结构:

在双向链表中同样可以实现单向链表中的头插,尾插,头删等操作。

此外,如用到结构体,结构体可以整体赋值。

比较单向链表和双向链表:

单向链表

结构:

  • 节点(Node):每个节点包含两部分:
    • 数据(Data):存储节点的值。
    • 指针(Next):指向链表中下一个节点的指针。

特点:

  • 单向遍历:单向链表只能从头节点开始,按顺序向下遍历,直到链表的末尾。无法逆向遍历。
  • 内存占用较少:每个节点只需要一个指针(指向下一个节点),因此占用的内存相对较少。
  • 操作复杂度
    • 插入节点:在链表头插入效率较高,但在链表尾部插入需要遍历整个链表。
    • 删除节点:如果要删除特定节点,需要从头遍历到目标节点的前一个节点

双向链表

结构:

  • 节点(Node):每个节点包含三部分:
    • 数据(Data):存储节点的值。
    • 前指针(Prev):指向链表中前一个节点的指针。
    • 后指针(Next):指向链表中下一个节点的指针。

特点:

  • 双向遍历:可以从链表的头节点向后遍历,也可以从链表的尾节点向前遍历。这种双向遍历特性使得某些操作更加灵活。
  • 内存占用较多:每个节点需要两个指针(指向前一个节点和后一个节点),因此占用的内存比单向链表多。
  • 操作复杂度
    • 插入节点:可以在链表的任意位置高效地插入节点,因为可以通过前后指针直接找到所需位置。
    • 删除节点:由于可以通过前指针找到前一个节点,因此删除操作也更加高效。

使用单向链表的情况

  1. 内存有限

    • 内存占用:单向链表每个节点只包含一个指针,因此占用的内存较少。如果内存资源非常有限,单向链表是更合适的选择。
  2. 只需要单向遍历

    • 简单遍历:当只需要从头到尾的单向遍历时,单向链表更简单高效。例如,队列(FIFO)的实现通常使用单向链表,因为只需要从头部插入,从尾部删除。
  3. 操作集中在链表的头部

    • 高效插入和删除:如果插入和删除操作主要集中在链表的头部(如栈的实现),单向链表的效率更高,因为只需调整头指针即可。
  4. 数据的插入顺序较为简单

    • 顺序存储:如果数据的插入顺序是线性的且不需要复杂的插入操作(例如,追加到链表尾部),单向链表足够满足需求。

使用双向链表的情况

  1. 需要双向遍历

    • 双向访问:如果需要从任意节点向前或向后遍历链表,双向链表是必要的。例如,双向链表适用于实现双端队列(Deque),其中可以从两端进行插入和删除操作。
  2. 频繁插入和删除操作

    • 任意位置的高效操作:双向链表可以在链表的任意位置高效地插入或删除节点,因为可以通过前后指针快速找到前驱和后继节点。例如,某些缓存系统使用双向链表来管理元素的插入和删除,以便在 O(1) 时间内更新链表。
  3. 需要从尾部高效操作

    • 尾部插入/删除:如果需要频繁从链表尾部进行插入或删除操作,双向链表是更好的选择,因为你可以直接访问尾节点,而无需遍历整个链表。
  4. 实现复杂数据结构

    • 复杂数据结构:某些复杂的数据结构,如自平衡二叉搜索树或图的邻接表,可能需要双向链表来更灵活地管理节点和指针。

这篇关于嵌入式学习(双向链表)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1137241

相关文章

SQLite3 在嵌入式C环境中存储音频/视频文件的最优方案

《SQLite3在嵌入式C环境中存储音频/视频文件的最优方案》本文探讨了SQLite3在嵌入式C环境中存储音视频文件的优化方案,推荐采用文件路径存储结合元数据管理,兼顾效率与资源限制,小文件可使用B... 目录SQLite3 在嵌入式C环境中存储音频/视频文件的专业方案一、存储策略选择1. 直接存储 vs

嵌入式数据库SQLite 3配置使用讲解

《嵌入式数据库SQLite3配置使用讲解》本文强调嵌入式项目中SQLite3数据库的重要性,因其零配置、轻量级、跨平台及事务处理特性,可保障数据溯源与责任明确,详细讲解安装配置、基础语法及SQLit... 目录0、惨痛教训1、SQLite3环境配置(1)、下载安装SQLite库(2)、解压下载的文件(3)、

C++链表的虚拟头节点实现细节及注意事项

《C++链表的虚拟头节点实现细节及注意事项》虚拟头节点是链表操作中极为实用的设计技巧,它通过在链表真实头部前添加一个特殊节点,有效简化边界条件处理,:本文主要介绍C++链表的虚拟头节点实现细节及注... 目录C++链表虚拟头节点(Dummy Head)一、虚拟头节点的本质与核心作用1. 定义2. 核心价值二

Linux链表操作方式

《Linux链表操作方式》:本文主要介绍Linux链表操作方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、链表基础概念与内核链表优势二、内核链表结构与宏解析三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势六、典型应用场景七、调试技巧与

Go学习记录之runtime包深入解析

《Go学习记录之runtime包深入解析》Go语言runtime包管理运行时环境,涵盖goroutine调度、内存分配、垃圾回收、类型信息等核心功能,:本文主要介绍Go学习记录之runtime包的... 目录前言:一、runtime包内容学习1、作用:① Goroutine和并发控制:② 垃圾回收:③ 栈和

Android学习总结之Java和kotlin区别超详细分析

《Android学习总结之Java和kotlin区别超详细分析》Java和Kotlin都是用于Android开发的编程语言,它们各自具有独特的特点和优势,:本文主要介绍Android学习总结之Ja... 目录一、空安全机制真题 1:Kotlin 如何解决 Java 的 NullPointerExceptio

重新对Java的类加载器的学习方式

《重新对Java的类加载器的学习方式》:本文主要介绍重新对Java的类加载器的学习方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、介绍1.1、简介1.2、符号引用和直接引用1、符号引用2、直接引用3、符号转直接的过程2、加载流程3、类加载的分类3.1、显示

嵌入式Linux之使用设备树驱动GPIO的实现方式

《嵌入式Linux之使用设备树驱动GPIO的实现方式》:本文主要介绍嵌入式Linux之使用设备树驱动GPIO的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录一、设备树配置1.1 添加 pinctrl 节点1.2 添加 LED 设备节点二、编写驱动程序2.1

嵌入式Linux驱动中的异步通知机制详解

《嵌入式Linux驱动中的异步通知机制详解》:本文主要介绍嵌入式Linux驱动中的异步通知机制,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言一、异步通知的核心概念1. 什么是异步通知2. 异步通知的关键组件二、异步通知的实现原理三、代码示例分析1. 设备结构

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》:本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter(过滤器)1. Filter 的工作原理2. Filter 的配置与使用二、Listen