JavaScript 算法与数据结构学习路线：8 周实践清单

这是一份以动手实现和边界测试为主线的 8 周导览。它不替代上游源码，也不要求先刷几百道题；每周只聚焦一组概念，并留下能运行、能解释、能复测的练习产出。

你最终会获得什么

能用大 O 表示法说明常见操作的时间与空间成本，不再只凭代码行数判断快慢。
能用 JavaScript 实现链表、栈、队列、哈希表、堆、树和图，并解释各自的适用场景。
能识别二分查找、分治、回溯、动态规划、广度优先搜索和深度优先搜索的基本结构。
能为空输入、单元素、重复值、异常分支和大规模输入编写测试。
能完成一个依赖任务调度器，把队列、优先队列、图和拓扑排序组合成完整项目。

1. 开始之前：准备环境与学习方法

先修知识

开始路线前，确认自己已经理解变量与函数、数组和对象、Map 与 Set、类、模块、递归以及基本异常处理。暂时不熟悉异步编程不影响本路线；先掌握同步数据结构，再学习复杂应用。

上游固定版本要求 Node.js 22 或更高版本、npm 10 或更高版本。以下命令会取得完整仓库并切换到本文核对的 Commit：

git clone https://github.com/trekhleb/javascript-algorithms.git
cd javascript-algorithms
git checkout 85293e3e2b88f4d2ce330d956b139cf628aa1e82
npm ci
npm test -- --runInBand

上游提供简体中文说明。建议先读任务说明和测试，再独立实现，最后才对照源码；不要从复制答案开始。

每个主题的固定练习循环

描述问题：写清输入、输出、约束、边界和是否允许修改原数据。
先猜成本：在实现前写下预期时间复杂度和额外空间复杂度。
写最小实现：先让普通样例通过，再处理空输入、重复值和异常分支。
补自动化测试：至少包含一个正常用例、三个边界用例和一个反例。
对照与复述：比较上游实现，合上书重新解释关键不变量，并记录自己曾犯的错误。

每周建议投入 5–7 小时：两次各 60–90 分钟用于学习，两次用于编码，最后一次只做测试和复盘。时间不足时减少主题数量，不省略测试。

2. 复杂度：先学会比较方案

大 O 描述输入规模增长时资源消耗的增长趋势，不等于某一次运行的精确毫秒数。O(1) 也可能比小输入下的 O(n) 慢，比较方案时必须同时说明数据规模和常数开销。

O(1)：哈希表的平均查找、栈顶读取。
O(log n)：有序数组上的二分查找、平衡二叉搜索树的典型操作。
O(n)：遍历数组、单向链表查找。
O(n log n)：归并排序，以及比较排序中常见的高效方案。
O(n²)：对所有元素两两比较的朴素算法。
O(2ⁿ)：没有缓存且每一步产生两个分支的朴素递归。

分析递归时，同时写出单次调用成本、调用次数和递归深度。分析空间时，不遗漏递归调用栈、辅助数组、字符串拼接和返回值本身。

练习：分别写出一个 O(n) 和一个 O(n²) 的重复元素检测函数，用相同输入比较结果；再使用 Set 改进方案，并说明平均成本为什么变化。

3. 八周学习路线

第 1 周：链表、栈与队列——理解引用和顺序

精选入口：单向链表。

画出节点与 next 引用的变化，再实现链表追加、查找、删除和反向遍历。
用栈实现括号匹配，用队列模拟按到达顺序处理任务。
比较链表头部操作与数组 push、shift、unshift 的成本。
本周产出：一个支持 toArray() 的单向链表，以及括号匹配的 Jest 测试。
过关标准：删除头节点、尾节点、唯一节点和不存在节点时，行为都可解释且有测试。

第 2 周：哈希表、堆与优先队列——按特征选结构

精选入口：哈希表。

用 Map 完成词频统计，再实现一个简化哈希表，观察碰撞为何需要处理。
在最小堆中维护父节点不大于子节点的性质，逐层画出插入和删除过程。
比较“每次排序取最值”和“堆中取最值”的总成本。
本周产出：一个支持插入、读取堆顶、删除堆顶的最小堆。
过关标准：重复优先级、空堆删除和大量降序输入均有明确行为。

第 3 周：二叉搜索树、树遍历与前缀树——掌握递归结构

精选入口：二叉搜索树。

写出二叉搜索树查找所依赖的左小右大不变量，并讨论重复值策略。
实现前序、中序、后序和层序遍历，比较递归与显式栈两种思路。
用前缀树实现单词插入、完整单词查找和前缀查找，区分“节点存在”与“单词结束”。
本周产出：一棵可插入、查找和按中序输出的二叉搜索树。
过关标准：能解释极度倾斜时查找为何退化，并能写出对应输入序列。

第 4 周：查找与排序——比较不变量和成本

精选入口：线性搜索。

使用左闭右闭或左闭右开区间实现二分查找，全篇保持同一种区间定义。
手写归并过程，理解分治如何把大问题拆小，再合并有序结果。
比较插入、归并、快速和堆排序的平均成本、最坏成本、额外空间与稳定性。
注意 JavaScript 默认 Array.prototype.sort() 的字符串排序规则；数字排序需要明确比较函数。
本周产出：统一测试套件下的一种二分查找和两种排序实现。
过关标准：空数组、单元素、全相等、已排序、逆序和含负数输入全部通过。

第 5 周：递归、分治与回溯——管理搜索状态

精选入口：递归爬楼梯、N 皇后。

每个递归函数先写终止条件，再写本层选择、下一层问题和状态恢复。
用递归树分析汉诺塔，观察子问题数量与层数如何决定总调用量。
实现组合搜索，在每次“选择—递归—撤销选择”前后检查共享状态。
在 N 皇后中用列和对角线集合提前剪枝，而不是生成全部排列后再过滤。
本周产出：一个带选择追踪日志的组合生成器。
过关标准：任意递归返回后，候选列表和已用标记都恢复到进入前状态。

第 6 周：动态规划——识别重复子问题

精选入口：最大子数组。

先用朴素递归暴露重复子问题，再选择记忆化搜索或递推填表。
写清状态含义、转移方程、初始值和遍历顺序，不只背代码模板。
用滚动数组优化空间前，先保存正确版本作为对照，并确认本轮不会被旧值覆盖。
区分“所有元素为正数”和“允许全为负数”时的最大子数组答案。
本周产出：最长公共子序列长度的递推实现及一张手工状态表。
过关标准：空序列、完全不相同、完全相等等边界都能从状态定义推出答案。

第 7 周：图搜索与最短路径——处理连接关系

精选入口：图。

用邻接表表示稀疏图，明确有向或无向、是否允许重边和自环。
BFS 使用队列求无权图最少边数，DFS 使用递归或显式栈探索连通分量。
在入队或发现节点时标记已访问，避免环导致重复处理。
用入度和队列实现拓扑排序；结果数量少于节点总数时检查环。
只在边权满足非负要求时使用 Dijkstra，并记录前驱节点以恢复路径。
本周产出：支持添加边、BFS、DFS 和环检测的有向图。
过关标准：孤立节点、不连通图、环和不可达目标均有测试。

第 8 周：综合项目与面试表达——把知识连起来

本周不增加新算法，完成一个“带优先级的依赖任务调度器”：任务有名称、优先级和前置依赖；只有依赖完成后才能执行，同批可执行任务按优先级选择。

用 Map 保存任务，用邻接表保存依赖，用入度判断是否可执行。
用最小堆选择当前最高优先级任务，用拓扑过程检测循环依赖。
对重复任务名、未知依赖、自依赖、空任务列表和不可达任务返回明确错误。
在 README 中解释数据结构选择、关键不变量、时间复杂度和空间复杂度。
录制或口述五分钟讲解：先讲问题，再讲方案、权衡、测试和一次失败调试。
最终验收：实现、测试、复杂度说明和示例运行记录齐全，不依赖复制上游代码才能讲清楚。

4. 测试清单：正确性先于技巧

上游使用 Jest。为自己的实现建立统一样例，让不同算法在相同输入上接受同样检查，而不是只验证一个演示数组。

test.each([
  [[], []],
  [[3], [3]],
  [[2, 2, 2], [2, 2, 2]],
  [[1, 2, 3], [1, 2, 3]],
  [[3, -1, 2], [-1, 2, 3]],
])('sorts %p', (input, expected) => {
  expect(mySort(input)).toEqual(expected);
});

每个主题至少检查以下项目：

规模：空输入、单元素、小输入和足以暴露性能问题的大输入。
数据形态：重复值、负值、已排序、逆序、极度倾斜或不连通。
修改语义：函数是否修改原数组、共享节点或调用方提供的对象。
错误路径：不存在的节点、非法参数、不可达目标和循环依赖。
结果性质：排序结果可复验，路径连续，调度不违反依赖，递归后状态已恢复。

性能测试单独记录环境、输入规模和重复次数，不把一次 console.time() 当作复杂度证明。

5. JavaScript 常见陷阱

数字排序：sort() 默认按字符串比较；数字场景显式传入 (a, b) => a - b。
数组头部操作：shift() 和 unshift() 通常需要移动剩余元素，不要误写成 O(1)。
对象引用：复制数组或节点列表不一定复制节点本身；回溯时明确需要浅拷贝还是重建状态。
递归深度：过深递归可能耗尽调用栈；大输入可改用显式栈或迭代。
浮点与整数：位运算会转换为 32 位整数，不能无条件替代安全整数范围内的算术。
原地修改：遍历数组时 splice() 会改变后续索引；先定义修改策略再写循环。
测试相等：Jest 的 toBe() 检查引用，数组和对象内容比较通常使用 toEqual()。

6. 自测：不看答案能否讲清楚

完成 8 周后，随机抽取以下问题。能写代码之外，还要能说明约束和权衡：

为什么有序数组可以二分查找，而单向链表通常不适合同样优化？
删除单向链表节点时，为什么头节点和尾节点需要分别检查？
堆为什么适合反复取最值，却不适合任意元素快速查找？
二分查找的区间定义如何影响左右边界更新和终止条件？
回溯中的“撤销选择”具体恢复哪些状态？浅拷贝是否足够？
动态规划的状态、转移、初始值和遍历顺序分别是什么？
BFS 为什么能得到无权图最少边数？已访问标记应何时设置？
拓扑排序为什么能检测环？Dijkstra 为什么要求非负边权？
你的调度器如何处理多个合法执行顺序，测试是否过度依赖某一种顺序？
如果输入扩大 100 倍，哪一步最先成为瓶颈，如何用复杂度分析和测量验证？

不能回答的问题回到对应周补一个最小实验，不盲目增加刷题数量。

7. 来源、版本与许可

上游项目：trekhleb/javascript-algorithms。
固定 Commit：85293e3e2b88f4d2ce330d956b139cf628aa1e82。
上游许可：MIT License。

本文依据上游固定版本的目录、主题和仓库使用方式重新编写学习顺序、练习与自测，不复制其算法实现。上游源码、测试和文档的再利用遵循其 MIT 许可；本文中的外部链接仅作为对应版本的阅读入口。

JavaScript 算法与数据结构学习路线