常用数据结构
一、常用数据结构总览
|
数据结构 |
核心作用 |
主要解决的问题 |
查询(平均/典型) |
插入 |
删除 |
修改 |
空间代价 |
|---|---|---|---|---|---|---|---|
|
数组(Array) |
连续存储数据,通过下标访问 |
快速随机访问元素 |
O(1) |
O(n) |
O(n) |
O(1) |
O(n) |
|
链表(Linked List) |
通过指针连接节点 |
频繁插入、删除元素 |
O(n) |
O(1)* |
O(1)* |
O(n) |
O(n) |
|
队列(Queue) |
先进先出(FIFO) |
任务排队、顺序处理 |
O(n) |
O(1) |
O(1) |
O(n) |
O(n) |
|
栈(Stack) |
后进先出(LIFO) |
回溯、撤销、递归调用 |
O(n) |
O(1) |
O(1) |
O(n) |
O(n) |
|
堆(Heap) |
快速获取最大值或最小值 |
优先级调度、Top K |
O(1)** |
O(log n) |
O(log n)** |
O(n) |
O(n) |
|
二叉树(Binary Tree) |
层级组织数据 |
层级关系、快速搜索 |
O(log n)*** |
O(log n)*** |
O(log n)*** |
O(log n)*** |
O(n) |
|
哈希表(Hash Table) |
通过 Key 快速定位 Value |
快速查找、去重、映射 |
O(1) |
O(1) |
O(1) |
O(1) |
O(n) |
|
图(Graph) |
表示节点之间的复杂关系 |
路径搜索、网络关系、依赖关系 |
O(V+E)**** |
O(1)**** |
O(V+E)**** |
O(1)**** |
O(V+E) |
说明:以上为典型实现的复杂度,不代表所有实现都相同。n 为元素数量,V 为顶点数量,E 为边数量。
-
*链表已经定位到目标节点时,插入和删除为 O(1),但查找目标节点通常为 O(n)。 -
**堆的 O(1) 查询指获取堆顶;删除堆顶为 O(log n),任意元素查找为 O(n)。 -
***指平衡二叉搜索树,如 AVL 树、红黑树。普通二叉树不保证 O(log n)。 -
****图的复杂度取决于邻接表、邻接矩阵及具体操作,表中查询主要指遍历。
二、数据结构的特点与使用场景
|
数据结构 |
主要特点 |
代价与缺点 |
典型使用情景 |
什么情况下使用 |
|---|---|---|---|---|
|
数组 |
内存连续,支持下标随机访问,缓存友好 |
中间插入、删除需要移动元素 |
商品列表、用户列表、批量数据 |
需要按下标访问,数据量相对稳定 |
|
链表 |
节点通过指针连接,插入删除灵活 |
不支持随机访问,额外占用指针空间 |
LRU 缓存、链式结构、内存管理 |
已经知道节点位置,需要频繁插入删除 |
|
队列 |
FIFO,先进入的先处理 |
不适合随机访问和中间操作 |
消息队列、订单处理、任务调度 |
需要按照提交顺序处理任务 |
|
栈 |
LIFO,后进入的先处理 |
只能操作栈顶,访问受限 |
函数调用、浏览器返回、撤销操作 |
需要后进先出、回溯或记录执行状态 |
|
堆 |
堆顶始终是最大值或最小值 |
不适合全量排序和任意元素查找 |
定时任务、优先级队列、Top K |
需要快速获取优先级最高或最低的元素 |
|
二叉树 |
父子节点结构,支持层级组织和搜索 |
普通二叉树可能退化为链表 |
数据库索引、文件目录、组织架构 |
需要层级关系或有序搜索 |
|
哈希表 |
Key 映射 Value,平均查找速度快 |
哈希冲突、扩容、额外空间开销 |
Redis、缓存、字典、用户 ID 映射 |
需要根据唯一 Key 快速查询数据 |
|
图 |
节点和边组成,可表示复杂关系 |
关系维护和遍历较复杂 |
社交网络、地图导航、依赖分析 |
数据之间存在多对多关系 |
三、常用数据结构的性能公式
这是实际开发中最值得掌握的部分。
|
数据结构 |
最重要的性能公式 |
具体含义 |
|---|---|---|
|
数组 |
O(1) |
根据下标直接访问 |
|
链表 |
O(n) |
遍历查找节点 |
|
队列 |
O(1) |
队尾插入、队头删除 |
|
栈 |
O(1) |
栈顶入栈、出栈 |
|
堆 |
O(log n) |
插入元素、调整堆 |
|
平衡二叉搜索树 |
O(log n) |
查找、插入、删除 |
|
哈希表 |
O(1) |
平均情况下根据 Key 查找 |
|
图 |
O(V+E) |
邻接表遍历整个图 |
四、结合 PHP / Python 后端开发的实际选择
|
业务需求 |
推荐数据结构 |
原因 |
实际例子 |
|---|---|---|---|
|
根据用户 ID 查询用户 |
哈希表 |
Key 快速定位 Value |
|
|
商品列表展示 |
数组 |
顺序存储,遍历方便 |
商品列表 API |
|
订单任务排队 |
队列 |
FIFO 顺序处理 |
订单异步任务 |
|
撤销操作 |
栈 |
LIFO |
编辑器撤销 |
|
获取销量最高的 10 个商品 |
堆 |
Top K 问题 |
商品销量排行榜 |
|
用户组织架构 |
树 |
父子层级关系 |
部门、员工 |
|
商品分类 |
树 |
多级分类关系 |
一级分类、二级分类 |
|
Redis 缓存 |
哈希表 |
Key-Value 映射 |
用户信息缓存 |
|
最近最少使用缓存 |
哈希表 + 双向链表 |
O(1) 查询和调整访问顺序 |
LRU Cache |
|
地图导航 |
图 |
节点与路径关系 |
最短路径算法 |
|
服务依赖分析 |
图 |
处理复杂依赖关系 |
微服务调用关系 |
五、几个容易混淆的概念
|
对比 |
核心区别 |
|---|---|
|
数组 vs 链表 |
数组擅长随机访问,链表擅长已定位节点后的插入删除 |
|
队列 vs 栈 |
队列先进先出,栈后进先出 |
|
堆 vs 栈 |
堆是树形优先级数据结构;栈是后进先出的线性数据结构。二者不是同一概念 |
|
堆 vs 二叉搜索树 |
堆只保证父子节点的优先级关系;二叉搜索树保证左小右大的搜索顺序 |
|
二叉树 vs 图 |
树是特殊的图,具有层级结构且没有环 |
|
数组 vs 哈希表 |
数组通过下标定位,哈希表通过 Key 定位 |
最重要的选型原则:
-
追求随机访问速度:选择数组。
-
追求已定位节点的插入、删除效率:选择链表。
-
需要按顺序处理任务:选择队列。
-
需要回溯、撤销:选择栈。
-
需要快速获取最大值、最小值:选择堆。
-
需要层级关系:选择树。
-
需要 Key 快速查询:选择哈希表。
-
需要表达复杂关联关系:选择图。