👉前端需要掌握的数据结构
常用数据结构
| 数据结构 | 要点 | 适合场景 |
|---|
| 数组 | 连续内存、O(1) 随机访问 | 频繁访问、遍历 |
| 链表 | 指针链接、O(1) 插入删除 | 频繁增删、动态大小 |
| 栈 | LIFO、后进先出 | 函数调用、括号匹配 |
| 队列 | FIFO、先进先出 | 任务调度、BFS |
| 哈希表 | 键值映射、O(1) 查找 | 快速查找、去重 |
| 树 | 层级结构、节点连接 | DOM、文件系统 |
| 堆 | 完全二叉树、优先队列 | top K、排序 |
| 图 | 节点 + 边、邻接矩阵/表 | 社交网络、路径规划 |
数组与字符串
| 操作 | 时间复杂度 | 空间复杂度 |
|---|
| 访问 | O(1) | - |
| 搜索 | O(n) | - |
| 插入/删除 | O(n) | O(1) |
| 翻转 | O(n) | O(n) |
常用技巧：双指针、滑动窗口、前缀和
链表
| 操作 | 时间复杂度 |
|---|
| 访问 | O(n) |
| 插入/删除 | O(1) |
| 反转 | O(n) |
题型：反转链表、环形检测、合并有序链表
栈与队列
| 数据结构 | 核心操作 | 特性 |
|---|
| 栈 | push/pop | LIFO |
| 队列 | enqueue/dequeue | FIFO |
| 双端队列 | 前后均可操作 | 滑动窗口 |
应用：函数调用栈、括号匹配、BFS、单调栈
哈希表
| 操作 | 平均复杂度 | 最坏复杂度 |
|---|
| 查找 | O(1) | O(n) |
| 插入 | O(1) | O(n) |
| 删除 | O(1) | O(n) |
题型：两数之和、计数、去重、字母异位词
树
| 操作 | 时间复杂度 |
|---|
| 遍历 | O(n) |
| 搜索 | O(log n) |
| 插入/删除 | O(log n) |
题型：二叉搜索树、路径总和、层序遍历
堆
| 操作 | 时间复杂度 |
|---|
| 插入 | O(log n) |
| 取最值 | O(1) |
| 删除最值 | O(log n) |
应用：top K、数据流中位数、优先级队列
复杂度速查
| 分类 | 数据结构 | 查询 | 插入 | 删除 |
|---|
| 线性 | 数组 | O(1) | O(n) | O(n) |
| 线性 | 链表 | O(n) | O(1)* | O(1)* |
| 线性 | 哈希表 | O(1) | O(1) | O(1) |
| 线性 | 栈/队列 | - | O(1) | O(1) |
| 树形 | 二叉搜索树 | O(log n) | O(log n) | O(log n) |
| 树形 | 堆 | O(1) | O(log n) | O(log n) |
参考资源
- LeetCode 分类刷题（数组、链表、树、堆）
- 前端算法面试高频题集
- 《算法导论》数据结构章节