前端面试高频算法与数据结构：从复杂度到手写题一网打尽
前端面试考算法，问的不是"你数学好不好"，而是两件事：你有没有数据结构意识（看到问题能想到该用栈、哈希表还是树），你有没有复杂度意识（知道这段代码是 O(n) 还是 O(n²)）。因为前端日常处理的 DOM、事件、状态、缓存，底层全是数据结构——只是平时被框架藏起来了。
这篇文章按"数据结构 → 算法 → 手写题"三层把最常考的内容串一遍：每个结构讲清特性、给一两个高频题、再落到前端场景。不贪多，但每一块都能直接拿去应对面试。
1. 复杂度：一切讨论的前提
面试里"这个解法复杂度多少"是必问的。复杂度用大 O 表示法描述数据量变大时，运行时间/空间增长的量级：
| 复杂度 | 含义 | 典型场景 |
|---|---|---|
| O(1) | 恒定 | 数组按下标访问、哈希表查找 |
| O(log n) | 每次砍一半 | 二分查找、平衡树查找 |
| O(n) | 线性 | 数组遍历、单层 for 循环 |
| O(n log n) | 分治 | 快排、归并 |
| O(n²) | 双重循环 | 冒泡排序、两两比较 |
前端的复杂度直觉：一个 10 万条的列表，O(n) 是 10 万次操作，O(n²) 是 100 亿次——后者必然卡死页面。所以 React 的 diff、虚拟列表、防抖节流，本质上都是在"把复杂度压下来"。这也是为什么"写代码前先估一下复杂度"是面试官最看重的基本功。
2. 数组：随机访问之王
特性：按下标访问 O(1)；但在中间插入/删除要挪动后面的元素，O(n)。
高频操作三个：
// ① 去重 —— O(n)
const unique = [...new Set([1, 1, 2, 3, 3])]; // [1, 2, 3]
// ② 扁平化 —— O(n)（含所有元素）
const flat = [1, [2, [3, [4]]]].flat(Infinity); // [1, 2, 3, 4]
// 手写版（递归，面试爱考）
function flatten(arr) {
return arr.reduce(
(acc, cur) => Array.isArray(cur) ? acc.concat(flatten(cur)) : acc.concat(cur),
[],
);
}
// ③ 翻转 —— O(n)
const rev = [1, 2, 3].reverse(); // [3, 2, 1]
前端场景：列表渲染 map、去重后的筛选条件、flatMap 拍平树形数据再渲染——都是数组基本功。
3. 栈 Stack：后进先出（LIFO）
栈只有两个动作：压栈 push（放栈顶）、弹栈 pop（取栈顶），看栈顶 peek。特性一句话：最后放进去的，最先被拿出来。
经典题：有效的括号
function isValid(s) {
const stack = [];
const map = { ')': '(', ']': '[', '}': '{' };
for (const ch of s) {
if (ch in map) {
if (stack.pop() !== map[ch]) return false; // 遇到右括号，必须匹配栈顶
} else {
stack.push(ch); // 左括号入栈
}
}
return stack.length === 0;
}
前端场景：栈无处不在——
- 函数调用栈：每次函数调用压栈，返回时弹栈——递归爆栈就是栈被压满了；
- 错误堆栈：
console.trace()/ 报错时的调用链，就是栈的直观展示； - Undo / Redo：撤销栈 + 重做栈；
- 括号/标签匹配：HTML 解析、模板引擎都在用。
4. 队列 Queue：先进先出（FIFO）
队列只有两个动作：入队（放队尾）、出队（取队头）。特性：先来的先处理。
JS 里的队列：shift() 出队是 O(n)（要挪动），追求性能可用两个栈模拟或用环形数组。但前端高频考的不是实现，而是事件循环：
规则就一句：每次事件循环取一个宏任务执行 → 然后把微任务队列清空 → 再取下一个宏任务。所以：
console.log(1); // 同步
Promise.resolve().then(() => console.log(2)); // 微任务
setTimeout(() => console.log(3)); // 宏任务
// 输出：1 → 2 → 3
前端场景：BFS 也是用队列——见第 6 节树的层序遍历。React 的并发渲染、消息队列、任务调度全是队列思想。
5. 链表 Linked List：插入删除快，随机访问慢
链表和数组正好互补：已知节点时插入/删除 O(1)（改指针即可），但按下标访问要逐个走，O(n)。
经典题 ①：反转链表（三指针）
function reverseList(head) {
let prev = null, cur = head;
while (cur) {
const next = cur.next; // 先记住下一个
cur.next = prev; // 反转指针
prev = cur;
cur = next;
}
return prev;
}
经典题 ②：环形链表（快慢指针——最常用的技巧之一）
function hasCycle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next; // 走一步
fast = fast.next.next; // 走两步
if (slow === fast) return true; // 有环必相遇
}
return false;
}
前端场景：React Fiber 的 workInProgress 树底层就是链表结构；浏览器的 DOM 的 nextSibling / parentNode 也是指针式遍历；LRU 缓存（见第 7 节）更是链表 + 哈希表的经典组合。
6. 哈希表（Map / Set / Object）：O(1) 查找
哈希表的核心思想：用"散列函数"把键映射成数组下标，直接落到对应的"桶"里。所以查找 / 插入 / 删除平均都是 O(1)——不靠遍历，靠"算一下就定位"。
6.1 先分清 JS 里的三个容器：Map / Set / Object
面试最爱问"Map 和 Object 选谁"。先说结论：需要"键值对 + 保持插入顺序 + 任意类型的键"时用 Map；只是普通的"名值结构 / 要 JSON 序列化"时用 Object。
| 特性 | Map | Object |
|---|---|---|
| 键的类型 | 任意（对象、函数都能当键） | 只能是字符串 / Symbol（数字键会被转成字符串） |
| 顺序 | 保持插入顺序（for...of / forEach 遍历稳定） | 整数键会自动按升序重排，不保证插入序 |
| 元素个数 | map.size 直接拿 | 要 Object.keys(o).length 额外数一遍 |
| 遍历 | 原生可迭代，for...of 直接用 | 要借 Object.keys / Object.entries |
| 频繁增删 | 性能稳定 | 删属性可能触发枚举重排，历史上更慢 |
| JSON | 不能直接 JSON.stringify | ✅ 原生序列化 |
| 原型链 | 纯"数据容器"，无原型干扰 | 继承 Object.prototype，键可能和原型方法撞名 |
Set 是"只有键、不重复"的集合：new Set([1, 1, 2]) → {1, 2}，同样保持插入顺序，常用于去重和判存在。
6.2 经典题：两数之和
用哈希表把"已经见过的值"记下来，一次遍历就能找到另一半：
function twoSum(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
if (map.has(need)) return [map.get(need), i]; // 找到了之前存的另一半
map.set(nums[i], i); // 记下"当前值 → 下标"
}
return [];
}
不用哈希表的话，双循环要 O(n²)；用哈希表把"查找另一半"从 O(n) 降到 O(1)，整体 O(n)。这就是"用空间换时间"的典型。
6.3 进阶：LRU 缓存（最常考的设计题）
先弄懂它是干嘛的。缓存 = 把"算得贵 / 读得慢"的结果暂时存起来，下次直接取，省得再算。但缓存容量有限（内存就那么大），满了就得淘汰旧数据。淘汰谁？——最久没被用过的那个。这就是 LRU（Least Recently Used，最近最少使用）。
为什么偏偏淘汰"最久未使用"？ 因为真实数据有时间局部性（temporal locality）：刚被访问过的数据，短时间内大概率还会再被访问；反之，很久没碰的最可能以后也用不上了。所以"先丢最久没用的"。浏览器 HTTP 缓存、Redis 内存淘汰、操作系统的页置换，全是这个思路。
Map 版本（能写出来就是加分项）——秘密全在 §6.1 说的"Map 保持插入顺序"：
class LRUCache {
constructor(capacity) { this.capacity = capacity; this.cache = new Map(); }
get(key) {
if (!this.cache.has(key)) return -1;
const value = this.cache.get(key);
this.cache.delete(key); // ① 先删掉旧的
this.cache.set(key, value); // ② 再插回去 → 排到"最新"位置
return value;
}
put(key, value) {
if (this.cache.has(key)) this.cache.delete(key); // 更新也先删旧的
this.cache.set(key, value);
if (this.cache.size > this.capacity) {
this.cache.delete(this.cache.keys().next().value); // 淘汰队头
}
}
}
每步在干什么，拆开看：
get命中：delete再set，等于把这条记录从旧位置挪到队尾——队尾永远是最新用过的；put更新：同理，先删后插；- 淘汰：
keys().next().value是迭代器的第一个元素 = 插入最早 = 最久未使用，超容量就删它。
（整套思路一句话：访问一次就把记录"顶"到最新，淘汰时永远踢队头。）
教科书版：双向链表 + 哈希表——为什么还要会这个版本？因为 Map 版本虽然能写，但面试官想确认你理解 O(1) 是怎么保证的。标准答案是双向链表管"顺序"，哈希表管"O(1) 定位"：
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.map = new Map(); // key → 链表节点
this.head = this.tail = null; // 双向链表头尾
}
_detach(node) { // O(1) 从链表摘掉 node
if (node.prev) node.prev.next = node.next; else this.head = node.next;
if (node.next) node.next.prev = node.prev; else this.tail = node.prev;
}
_pushToTail(node) { // O(1) 把 node 放到队尾
node.prev = this.tail; node.next = null;
if (this.tail) this.tail.next = node; else this.head = node;
this.tail = node;
}
get(key) {
const node = this.map.get(key);
if (!node) return -1;
this._detach(node);
this._pushToTail(node); // 顶到最新
return node.value;
}
put(key, value) {
if (this.map.has(key)) this._detach(this.map.get(key));
const node = { key, value, prev: null, next: null };
this.map.set(key, node);
this._pushToTail(node);
if (this.map.size > this.capacity) {
this.map.delete(this.head.key); // 淘汰队头
this._detach(this.head);
}
}
}
为什么是"哈希表 + 双向链表"这套组合：
- 哈希表负责"给个 key 直接 O(1) 找到节点"——没有它，找节点要遍历链表 O(n)；
- 双向链表负责"O(1) 移动 / 删除节点"——单向链表删除时不知道前驱，还得遍历找；双向链表有
prev指针，摘除即 O(1)。
两个数据结构各管一件事，合起来才是完整的 O(1) LRU。这也是面试设计题的标准答题骨架：先想清楚"哪个结构负责哪种能力"，再动手写。
真实场景：浏览器 HTTP 缓存、Redis 的 maxmemory-policy=allkeys-lru、Vue 的 <keep-alive> 组件缓存、React Query / SWR 的请求缓存、小程序本地缓存——凡是"内存有限 + 读多 + 想把热的留着"的地方，都是 LRU。
前端场景：对象属性查找 O(1)、Set 去重、函数 memo 缓存（useMemo 依赖比对底层）、依赖收集（Vue 的响应式）、虚拟 DOM 的属性 diff，全是哈希表。
7. 树：二叉树遍历与 DFS / BFS
树是最"前端"的数据结构——DOM 树、组件树、AST 都是树。核心操作是遍历，两种方式：
DFS（深度优先）：用递归或栈。二叉树的前/中/后序都是 DFS：
// 前序：根 → 左 → 右（递归版，最好写）
function preorder(root, res = []) {
if (!root) return res;
res.push(root.val);
preorder(root.left, res);
preorder(root.right, res);
return res;
}
// 前序（迭代版，用栈）——面试官常让你把递归改成迭代
function preorderIter(root) {
const res = [], stack = [root];
while (stack.length) {
const node = stack.pop();
if (!node) continue;
res.push(node.val);
stack.push(node.right, node.left); // 先压右，后压左 → 弹出来先左
}
return res;
}
BFS（广度优先）：用队列，一层一层扫。层序遍历必考：
function levelOrder(root) {
const res = [];
if (!root) return res;
const queue = [root];
while (queue.length) {
const size = queue.length; // 先记下这一层有几个节点
const level = [];
for (let i = 0; i < size; i++) {
const node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
res.push(level);
}
return res;
}
DOM 树的 DFS vs BFS（以一颗小 DOM 树为例）：
- DFS（前序）：
html → head → body → div → span → p（一条道走到黑再回头）； - BFS：
html → head, body → div, p → span（一层层扫）。
document.querySelectorAll 等选择器匹配、ReactDOM 的递归渲染，本质都是树的 DFS。
8. 排序：快排必须能手写
经典题：手写快排（分治思想：选基准 → 分区 → 递归）
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[0];
const left = [], right = [];
for (let i = 1; i < arr.length; i++) {
(arr[i] < pivot ? left : right).push(arr[i]);
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
（这是最容易手写、最不会出错的版本，代价是空间 O(n)。进阶可以聊原地分区的 in-place 版本，以及"最坏 O(n²) 怎么避免"——随机选基准 / 三数取中。）
排序复杂度与稳定性：
| 算法 | 平均 | 最坏 | 空间 | 稳定 |
|---|---|---|---|---|
| 快排 | O(n log n) | O(n²) | O(log n) | 否 |
| 归并 | O(n log n) | O(n log n) | O(n) | 是 |
| 冒泡 | O(n²) | O(n²) | O(1) | 是 |
| 选择 | O(n²) | O(n²) | O(1) | 否 |
| 插入 | O(n²) | O(n²) | O(1) | 是 |
稳定的意思是"相等的元素排序后保持原来的相对顺序"——需要稳定时（比如按日期排完再按状态排）选归并。
前端场景：Array.prototype.sort 底层——现代 V8 用 TimSort（稳定），小数组会走插入排序；但要注意 sort() 默认按字符串排序，排数字必须传比较函数：
[10, 9, 100].sort(); // [10, 100, 9] ← 按字符串排的坑
[10, 9, 100].sort((a, b) => a - b); // [9, 10, 100] ✅
9. 二分查找：有序数组的 O(log n)
经典题：标准二分（注意边界 lo <= hi）
function binarySearch(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1; // 取中位
if (arr[mid] === target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
面试升级问法：找左边界（第一个 >= target 的位置）：
function lowerBound(arr, target) {
let lo = 0, hi = arr.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (arr[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
前端场景：数据库索引就是 B+Tree 上的二分（见本博客 MySQL 索引）；前端里的二分常用于"有序列表找插入位置"、降级策略、CDN 最优节点等。
10. 递归与手写深拷贝
递归的核心是"把大问题拆成同样的子问题，直到最小规模"。手写深拷贝是前端最常考的手写题：
function deepClone(obj, seen = new Map()) {
if (obj === null || typeof obj !== 'object') return obj; // 基础类型直接返回
if (seen.has(obj)) return seen.get(obj); // 处理循环引用！
const res = Array.isArray(obj) ? [] : {};
seen.set(obj, res);
for (const key of Object.keys(obj)) {
res[key] = deepClone(obj[key], seen);
}
return res;
}
三个考点，一个都不能少：
- 基础类型直接返回（否则
typeof会误判）； seen记录已克隆对象，处理循环引用obj.self = obj——没有它直接爆栈；- 数组要单独判断（用
Array.isArray），否则克隆出来是对象。
递归的坑：层级太深会爆栈（RangeError: Maximum call stack size exceeded）。能改迭代就改迭代，或至少知道"大列表别用深递归"。
11. 动态规划入门：爬楼梯
动态规划（DP）记住三句话：① 大问题能拆成子问题；② 子问题会被反复用到（重叠子问题）；③ 边界和递推式。
经典题：爬楼梯（一次爬 1 或 2 阶，到第 n 阶有几种爬法）——答案就是斐波那契：f(n) = f(n-1) + f(n-2)。
从"会写"到"不超时"有三个层次：
// 层次 1：纯递归 —— O(2^n)，指数爆炸，n 稍大就卡死 ❌
function climb1(n) {
if (n <= 2) return n;
return climb1(n - 1) + climb1(n - 2);
}
// 层次 2：记忆化（自顶向下）—— O(n) ✅
function climb2(n, memo = {}) {
if (n <= 2) return n;
if (memo[n] !== undefined) return memo[n];
return (memo[n] = climb2(n - 1, memo) + climb2(n - 2, memo));
}
// 层次 3：自底向上滚动数组（真正的 DP）—— O(n) 时间 O(1) 空间 ✅
function climb3(n) {
if (n <= 2) return n;
let a = 1, b = 2;
for (let i = 3; i <= n; i++) [a, b] = [b, a + b];
return b;
}
前端场景：diff 算法的 LCS（最长公共子序列）就是二维 DP（见 React diff 系列博客）；菜单高亮、路径统计这类"分步决策"问题都是 DP 的形态。
12. 双指针 / 滑动窗口
双指针是解字符串、数组题的高频套路。两个经典：
① 滑动窗口：最长无重复子串
function lengthOfLongestSubstring(s) {
const seen = new Set();
let left = 0, max = 0;
for (let right = 0; right < s.length; right++) {
while (seen.has(s[right])) { // 窗口里有重复 → 右移 left 直到没有
seen.delete(s[left]);
left++;
}
seen.add(s[right]);
max = Math.max(max, right - left + 1);
}
return max;
}
② 双指针：回文判断（字符串预处理后左右夹逼）
function isPalindrome(s) {
s = s.toLowerCase().replace(/[^a-z0-9]/g, '');
let l = 0, r = s.length - 1;
while (l < r) {
if (s[l] !== s[r]) return false;
l++; r--;
}
return true;
}
前端场景：防抖节流里的时间窗口、输入联想、评论分页加载，本质都是"维护一个窗口，只在窗口内做事"。
13. 前端手写题清单（速查表）
面试前最后冲刺，对着这张表过一遍。带链接的已有专题文章，不重复展开：
| 手写题 | 关键点 | 复杂度 | 位置 |
|---|---|---|---|
| 数组去重 | Set / filter + indexOf | O(n) | 本文 §2 |
| 数组扁平化 | 递归 + reduce | O(n) | 本文 §2 |
| 有效括号 | 栈 | O(n) | 本文 §3 |
| 两数之和 | 哈希表 | O(n) | 本文 §6 |
| LRU 缓存 | Map 保持插入顺序 / 双向链表 + 哈希表 | 均摊 O(1) | 本文 §6.3 |
| 反转链表 | 三指针 | O(n) | 本文 §5 |
| 环形链表 | 快慢指针 | O(n) | 本文 §5 |
| 二叉树遍历 | 递归 ↔ 迭代 | O(n) | 本文 §7 |
| 快排 | 分治 + 递归 | O(n log n) | 本文 §8 |
| 二分查找 | 边界 lo <= hi | O(log n) | 本文 §9 |
| 深拷贝 | 递归 + 循环引用 Map | O(n) | 本文 §10 |
| 爬楼梯 | 滚动数组 DP | O(n) | 本文 §11 |
| 最长无重复子串 | 滑动窗口 | O(n) | 本文 §12 |
| 防抖 / 节流 | 闭包 + 定时器 | — | 防抖节流专题 |
call / apply / bind / Promise | 状态机 / 链式调用 | — | 手写 JS 系列 |
14. 一句话总结
前端面试考算法，考的是数据结构意识 + 复杂度意识：看到"要快速查找"想哈希表、看到"要后进先出"想栈、看到"要先进先出 / 一层层"想队列、看到"递归结构 / 树形"想 DFS/BFS、看到"有序数组"想二分、看到"要排序"想快排、看到"分步决策可拆分"想 DP。而这一切在前端都有真实的落点——调用栈、事件循环、DOM 树、diff、LRU、响应式依赖收集，数据结构从来不是面试的孤岛，它就是前端的日常。