2.1 KiB
2.1 KiB
数组
- 一种线性数据结构，相同类型的元素存储于连续的内存空间中
- 元素在数组中的位置称为该元素的索引
- 常用操作
- 初始化数组
- 访问元素
-
索引本质上是内存地址的偏移量
-
- 插入元素
- 删除元素
- 遍历数组
- 查找元素
- 扩容数组
- 优点
- 空间效率高
- 支持随机访问
- 缓存局部性
- 局限性
- 插入与删除效率低
- 长度不可变
- 空间浪费
- 典型应用
- 随机访问
- 排序与搜索
- 查找表
- 机器学习
- 数据结构实现
-
链表
- 一种线性结构，每一个元素都是一个节点对象，各个节点之间通过引用连接
- 各个节点可以分散在内存各处，内存地址无需连续
- 链表的首个节点被称为头节点，最后一个元素称为尾节点
- 尾部指向的是空
-
相同数据量下，链表比数组占用更多内存空间
- 常用操作
- 初始化链表
- 插入节点
- 删除节点
- 访问节点
- 查找节点
- 常见链表类型
- 单向链表
- 环形链表
- 双向链表
- 典型应用
- 栈与队列
- 哈希表
- 图
- 高级数据结构
- 浏览器历史
- LRU算法
- 时间片轮转算法
- 数据缓冲区
-
列表
- 可以动态扩容的数组
- 常用操作
- 初始化列表
- 访问元素
- 插入与删除元素
- 遍历列表
- 拼接列表
- 排序列表
- 列表实现
- 初始容量
- 数量记录
- 扩容机制
-
内存与缓存
-
物理结构在很大程度上决定了程序对内存和缓存的使用效率
- 金字塔结构
- 硬盘难以被内存取代
- 缓存的大容量和高速度难以兼得
- 硬盘用于长期存储大量数据，内存用于临时存储程序中正在处理的数据，缓存用来存储经常访问的数据
- 数据结构的内存效率
- 内存是有限的且同一块内存不能被多个程序共享
- 随着反复申请与释放内存，空闲内存的碎片化程度会越来越高
