一、常用数据结构总览

数据结构

核心作用

主要解决的问题

查询(平均/典型)

插入

删除

修改

空间代价

数组(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

$users[$userId]

商品列表展示

数组

顺序存储,遍历方便

商品列表 API

订单任务排队

队列

FIFO 顺序处理

订单异步任务

撤销操作

栈

LIFO

编辑器撤销

获取销量最高的 10 个商品

堆

Top K 问题

商品销量排行榜

用户组织架构

树

父子层级关系

部门、员工

商品分类

树

多级分类关系

一级分类、二级分类

Redis 缓存

哈希表

Key-Value 映射

用户信息缓存

最近最少使用缓存

哈希表 + 双向链表

O(1) 查询和调整访问顺序

LRU Cache

地图导航

图

节点与路径关系

最短路径算法

服务依赖分析

图

处理复杂依赖关系

微服务调用关系

五、几个容易混淆的概念

对比

核心区别

数组 vs 链表

数组擅长随机访问,链表擅长已定位节点后的插入删除

队列 vs 栈

队列先进先出,栈后进先出

堆 vs 栈

堆是树形优先级数据结构;栈是后进先出的线性数据结构。二者不是同一概念

堆 vs 二叉搜索树

堆只保证父子节点的优先级关系;二叉搜索树保证左小右大的搜索顺序

二叉树 vs 图

树是特殊的图,具有层级结构且没有环

数组 vs 哈希表

数组通过下标定位,哈希表通过 Key 定位

最重要的选型原则:

  • 追求随机访问速度:选择数组。

  • 追求已定位节点的插入、删除效率:选择链表。

  • 需要按顺序处理任务:选择队列。

  • 需要回溯、撤销:选择栈。

  • 需要快速获取最大值、最小值:选择堆。

  • 需要层级关系:选择树。

  • 需要 Key 快速查询:选择哈希表。

  • 需要表达复杂关联关系:选择图。