第22~26天线性表-北京尧图网络

一.线性表1.线性结构特点1.存在唯一的“第一个”元素2.存在唯一的“最后一个”元素3.除第一个外每个元素只有一个前驱4.除最后一个外每个元素只有一个后驱图是一种非线性数据结构其他的栈、队列和数组都是线性结构。顺序表时间复杂度插入一个元素的时间复杂度On删除一个元素的时间复杂度O(n)二.线性链表特点:一个节点包括两个域存储数据元素信息的域称为数据域存储直接后继存储位置的域称为指针域指针域指向下一个节点的位置。应用场景1 .动态数据结构动态调整大小的数据结构方便的插入和删除元素。2.频繁的插入和删除操作例如任务调度、操作系统中的进程管理等场景。3.实现其他数据结构如栈、队列、哈希表等。4.处理不确定数量的数据。5.实现图的邻接表。6.内存管理空闲内存块的链表管理可以有效地跟踪和分配内存。三.双向链表应用场景浏览器的历史记录在 Web 浏览器中双向链表被用于管理浏览器的前进和后退历史记录前进与后退功能双向链表允许用户在浏览器中轻松实现前进next和后退previous操作。当用户访问一个新页面时当前页面会被添加到链表中用户可以在链表中进行遍历快速返回到之前的页面或者前进到未来的页面。双向导航菜单在用户界面UI设计中双向链表可以用来构建双向导航菜单前进与后退功能用户可以在多个菜单层级之间进行前后跳转双向链表使得这种操作变得更加高效尤其在用户需要频繁切换菜单时。音乐播放器中的播放列表在音乐播放器或视频播放器中双向链表可以用来管理播放列表播放列表的管理双向链表允许用户在播放列表中前后跳转用户可以选择跳到播放列表中的任意歌曲并且支持播放列表的循环播放和顺序播放。双向链表构建一个结点中有两个指针域一个指向直接后继另一个指向直接前驱。四.总结链表内存不连续分散内存通过指针保存下一个节点的地址。中间插入删除性能高。数组内存连续大小固定支持随机访问数组下标访问性能最高中间插入删除性能偏低。动态数组堆区创建的数组插入/删除链表O(1)只需改指针数组O(n)需移动元素。随机访问链表O(n)得从头遍历数组O(1)直接下标。内存链表不连续无碎片问题但每个节点多耗内存存指针。Dummy 节点也叫虚拟头节点、哨兵节点是一个不存储实际数据的辅助节点作为链表的头节点简化链表操作。Dummy 节点的作用1.简化头节点操作:不用特判头节点2.统一插入删除逻辑:所有节点处理方式相同3.避免空指针异常:链表为空时也有节点4.返回dummy-nextreturn dummy-next; // 返回真实头节点1.在数组中访问元素的时间复杂度为 O(1)。如果数组有足够空间插入元素到末尾也是 O(1)。链表在头部插入元素也是 O(1)。而在链表中查找元素需要遍历因此是 O(n)。2.链表支持动态内存分配可以在运行时根据需要分配内存且插入和删除操作无需移动元素效率较高。链表不支持随机访问访问元素需要顺序遍历。3.链表的每个节点除了存储数据外还需要存储指针因此相较于数组链表的空间开销更大空间利用率较低。

第22~26天线性表

相关推荐

DDR5省电/掉电模式详解与DDR4的差异，Power Down Mode章节

Comprehensive Rust 生命周期实战：用 Rust 手写一个零拷贝 Protobuf 二进制解析器（附完整解答与测试）

Milvus QueryNode v2 重构设计解读：Delegator/Worker 角色分离与无 delta channel 的删除转发架构

更多资讯

Reflex Enterprise AG Grid Master-Detail 实战：在纯 Python 中实现可展开的主从嵌套网格

深入 ESLint：可插拔 JavaScript 代码检查器的设计哲学与源码实现

使用 WorkOS OAuth 保护 FastMCP 服务器：从零开始的端到端接入指南

Graphite 编辑器调试指南：Wasm 架构下的排查技巧与构建二分定位法

永磁同步电机MPCC控制原理与工程实践

美业门店效率革命：数据驱动与流程优化实战

今日更新

Linux 内核 ARM 虚拟内存布局全解析：从 4GB 地址空间划分到源码级验证

AIGC降重工具测评与教育应用指南

数据容灾核心指标与实战方案解析

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？