04 · 数据结构与算法（前端视角）
不背算法大全，只补"前端日常和面试真正用得上"的部分：数组/哈希/栈/队列/树的直觉、复杂度思维、以及它们在前端渲染、状态更新、列表 diff 里的影子。
速览卡
| 项 | 内容 |
|---|---|
| 一句话定位 | 给前端用的最小必要算法与数据结构心智 |
| 核心内容 | 复杂度直觉、常用结构、典型套路、前端对照 |
| 读完能回答 | 为什么要会复杂度？LRU、树遍历、滑动窗口在前端哪用得上？ |
| 相关板块 | E01 Python 基础 ｜ IA 算法面试题 |
一、复杂度：先想"数据量到多少会崩"
| 复杂度 | 直觉 | 前端例子 |
|---|---|---|
| O(1) | 一步到位 | 数组按下标、Map 查值 |
| O(n) | 扫一遍 | 渲染一页列表 |
| O(n log n) | 分而治之 | 排序 |
| O(n²) | 两两比较 | 嵌套循环的 diff |
判断框架：列表 1000 条内怎么都行；上万条再谈优化。先算"最坏情况有几层循环"，再决定要不要改。
二、常用结构的"什么时候用"
| 结构 | 擅长的操作 | 前端场景 |
|---|---|---|
| 数组 | 按下标访问、顺序遍历 | 列表渲染 |
| 哈希（Map/Set） | O(1) 查重、找对应 | 去重、id → 数据映射 |
| 栈 | 后进先出 | 路由回退、撤销 |
| 队列 | 先进先出 | 任务调度、消息队列 |
| 树 | 层级关系、递归 | 组件树、菜单、DOM |
| 链表 | 频繁头尾增删 | LRU 缓存 |
三、两个最常用的套路
哈希表：把"找"变成"查"
ts
// 两数之和：O(n²) → O(n)
const twoSum = (nums, target) => {
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
if (seen.has(target - nums[i])) return [seen.get(target - nums[i]), i];
seen.set(nums[i], i);
}
};滑动窗口：连续子数组问题
ts
// 最长无重复子串：O(n)
let l = 0, ans = 0;
const seen = new Set();
for (let r = 0; r < s.length; r++) {
while (seen.has(s[r])) seen.delete(s[l++]);
seen.add(s[r]);
ans = Math.max(ans, r - l + 1);
}四、树：前端的形状
text
组件树 / 目录树 / 菜单树 / DOM 树——全是树| 遍历 | 顺序 | 用处 |
|---|---|---|
| 前序 | 根 → 左 → 右 | 组件挂载 |
| 中序 | 左 → 根 → 右 | 二叉搜索树有序输出 |
| 后序 | 左 → 右 → 根 | 组件卸载、自底向上汇总 |
| 层序 | 一层层 | 找最短路径、展开层级 |
树的操作几乎都是递归。先写"对当前节点做什么 + 递归子树做什么"，别急着迭代。
五、栈与队列的工程影子
| 前端概念 | 底层结构 |
|---|---|
| 路由返回 | 栈 |
| 撤销/重做 | 两个栈 |
| 事件循环任务队列 | 队列 |
| 消息总线 | 队列 |
六、LRU：面试高频的"设计题"
text
读：O(1) → 用哈希表
淘汰最近最少用 → 维护访问顺序 → 链表前端场景：浏览器缓存淘汰、状态管理里的大数据缓存。会讲"哈希 + 双向链表"组合，比背代码更重要。
七、自检清单
- [ ] 能说出常用结构各自的擅长操作
- [ ] 会估算一段代码的时间复杂度
- [ ] 能写出两数之和与滑动窗口两题
- [ ] 能对着组件树说清前序/后序遍历
- [ ] 能解释 LRU 为什么是哈希 + 链表
八、常见误区
| 误区 | 事实 |
|---|---|
| "算法和前端无关" | 树、栈、哈希每天都在用 |
| "只会背题就行" | 关键是复杂度思维与场景映射 |
| "O(n²) 一定不行" | 数据量小的时候完全够用 |
| "所有树都要自己写" | 会用递归遍历和常见库即可 |
九、动手练习
练习 A：把真实数据建模
给一段嵌套的菜单 JSON，用递归展平成数组，再写一个按 id 查找的函数（用 Map）。
练习 B：滑动窗口实战
实现"最长无重复字符子串"，再用 LeetCode 同题验证。
练习 C：画组件树
画出你最近写的页面的组件树，标注哪部分可以缓存、哪部分每次必渲染，联系树遍历理解。
相关文档
本区
- 01 · Python 语言基础与 TS 对照 —— 用 Python 再写一遍这些套路
前端区
- 18 · 手写题与代码设计 —— 前端面试手写
面试区
- IA · 算法与数据结构面试题 —— 完整题型清单