前端算法入坑指南：用 JavaScript 一口气搞懂数组、栈、队列、链表和二叉树
前端算法入坑指南：用 JavaScript 一口气搞懂数组、栈、队列、链表和二叉树
用 JS 重新理解最基础的数据结构，面向面试，从零搭建知识体系。
涵盖数组的底层机制、栈与队列的受限操作、链表的增删优势、二叉树的递归遍历。
目录
- JavaScript 数据结构三讲：数组 · 栈与队列 · 树
一、为什么要重新学数据结构
数据结构是程序员的基本功，但很多前端同学接触得晚。Vue、React 用熟了，业务代码写了不少，一到算法面试就犯怵——因为框架替你把数据结构封装好了，日常开发很少直接跟链表、树打交道。
这套笔记的核心思路是：用 JavaScript 的视角重新走一遍数据结构，从数组开始，到栈和队列，再到树。不需要学 C 语言再来搞这个，就用你每天写的 JS，把底层逻辑搞懂。
三个原则贯穿始终：
- 面向 JavaScript——不脱离日常语言环境
- 面向面试——聚焦 HOT 100 高频考点
- 不要急于刷题——先把数据结构本身吃透，再去做题
二、数组：最熟悉也最陌生的老朋友
数组是每个 JS 开发者每天都会用的东西。const arr = [1, 2, 3]，闭着眼睛都能写。但你真的理解数组在内存里是怎么存的吗？new Array(7) 和 new Array(7).fill(0) 有什么区别？为什么 fill([]) 会翻车？
2.1 数组的本质：连续内存 + 下标寻址
从数据结构的角度看，数组由两样东西定义：
- 一段连续的存储空间——元素在内存里一个挨着一个
- 特定的操作行为——通过下标（索引）直接访问任意位置
JS 里创建数组最简单的方式是方括号字面量：
const arr = ['a', 'b', 'c'];
引擎在内存里划出一块连续区域，arr[0] 就是这块区域的起始地址，arr[1] 是起始地址 + 一个偏移量，arr[2] 再往后偏一格。这解释了为什么数组按下标访问是 O(1)——不需要遍历，算一下偏移量直接就能拿到。
这种"连续存储 + 特定操作"的抽象，在计算机科学里叫做 ADT（Abstract Data Type，抽象数据类型）。ADT 不关心底层怎么实现，只关心"支持哪些操作，这些操作有什么行为"。数组的 ADT 就是：连续空间，支持按下标读写。
2.2 创建数组的几种姿势
除了字面量，JS 还提供了构造函数 new Array()：
const arr1 = new Array(); // 等价于 []，空数组
const arr2 = new Array(7); // 创建长度为 7 的空数组
new Array(7) 的结果比较特殊：
[empty × 7]
这不是 [undefined, undefined, ...]。empty 表示这个内存位置还没有被任何值占据，它不属于任何类型。你访问 arr[0] 会得到 undefined，但这不意味着第 0 位存了一个 undefined 值——它只是"不存在"。
empty 和 undefined 的区别在遍历时会体现出来：
const arr = new Array(3);
arr[1] = 'hello';
arr.forEach((item, index) => {
console.log(index, item); // 只打印 1 'hello'，0 和 2 被跳过
});
forEach、map、filter 这些方法会自动跳过 empty 槽位，而 for 循环和 for...of 不会。
如果你需要一个"长度确定、每个元素也确定"的数组，用 fill：
const arr = (new Array(7)).fill(1);
// [1, 1, 1, 1, 1, 1, 1]
2.3 增删方法：谁动了原数组
JS 数组增删的核心方法有四个：
| 方法 | 作用 | 返回值 | 是否修改原数组 |
|---|---|---|---|
push(item) |
尾部插入 | 新长度 | ✅ 是 |
pop() |
尾部移除 | 被移除的元素 | ✅ 是 |
unshift(item) |
头部插入 | 新长度 | ✅ 是 |
shift() |
头部移除 | 被移除的元素 | ✅ 是 |
const arr = ['a', 'b', 'c'];
arr.push(1); // 返回 4，arr 变成 ['a', 'b', 'c', 1]
arr.push(2); // 返回 5，arr 变成 ['a', 'b', 'c', 1, 2]
arr.unshift(3); // 返回 6，arr 变成 [3, 'a', 'b', 'c', 1, 2]
arr.pop(); // 返回 2，arr 变成 [3, 'a', 'b', 'c', 1]
arr.shift(); // 返回 3，arr 变成 ['a', 'b', 'c', 1]
四个方法都直接修改原数组。这不是 bug，是设计——但确实容易在你不注意的时候产生副作用。
push 的扩容问题：数组在内存中是连续空间，当 push 导致元素数量超出当前容量时，引擎需要在内存里找一块更大的连续空间，把原有数据全部搬过去，再把新元素放进去。这个过程叫"扩容"，有性能开销。链表没有这个问题——每次增删只申请或释放一个节点的空间，不需要整块搬迁。这个问题在 2.7 节还会展开聊。
2.4 纯函数与非纯函数
上面四个方法都不是纯函数。那什么是纯函数？
一个纯函数必须满足两条：
- 相同的输入永远得到相同的输出——不依赖外部状态
- 没有副作用——不修改外部变量
let num = 0;
// 非纯函数：依赖外部变量 num，每次调用结果可能不同
function add(b) {
num += b;
return num;
}
add(5) 第一次返回 5，第二次返回 10——同样的输入，输出不同。因为它修改了外部的 num。
把这个概念套回数组方法：push、pop、shift、unshift、splice 都是非纯函数，它们修改了原数组。而 map、filter、concat、slice 是纯函数——返回新数组，原数组纹丝不动。
实际开发中优先用纯函数版本，数据流更可控，bug 更少。
2.5 遍历的六种方式，怎么选
JS 遍历数组的方式多得让人选择困难。下面逐一拆解，帮你搞清楚什么时候该用哪个。
① for 计数循环
for (let i = 0; i < arr.length; i++) {
console.log(arr[i]);
}
这是最"机器化"的写法。优点只有一个：性能最好。缺点是代码可读性差，i < arr.length 这种模板代码写多了烦。当你在写性能敏感的底层逻辑（比如图形渲染、大数据量处理），用 for。日常业务代码不推荐。
② for…of
for (const item of arr) {
console.log(item);
}
语义非常清晰——“对于数组里的每一项”。性能仅次于 for 循环，远好于 forEach。如果你不需要 index，这是最推荐的遍历方式。
③ forEach
arr.forEach((item, index, self) => {
console.log(item, index, self);
});
功能最强大——回调里能拿到元素值、索引、数组本身三个参数。但有一个致命限制：不能用 break 中途退出。在 forEach 里写 break 会直接报语法错误。如果业务需要"找到某个元素就停"，别用 forEach。
另一个容易被忽略的点：forEach 每次迭代都会产生一次函数调用，函数入栈出栈有开销。数据量大时性能劣化明显。
④ map
const doubled = arr.map((item) => item * 2);
基于 forEach 实现，返回一个全新的数组，原数组不变。适用于"把数组里的每一项都转换一下"的场景。
⑤ filter
const evens = arr.filter((item) => item % 2 === 0);
筛选：回调函数返回 true 的元素留下，false 的丢弃。返回新数组。
⑥ every / some
arr.every((item) => item % 2 === 0); // 每一项都满足 → true
arr.some((item) => item % 2 === 0); // 至少一项满足 → true
语义化判断。every 是"全真才真"，some 是"有一真就真"。它们有一个实用的短路特性：every 遇到第一个 false 就停止遍历，some 遇到第一个 true 就停止。
⑦ reduce（附赠）
const sum = arr.reduce((prev, item, index) => {
return prev + item;
}, 0); // 0 是初始值
reduce 是这堆方法里最灵活也最难读的。第一个参数是累加器回调，第二个参数是初始值。上面的代码等价于把数组从头到尾加一遍。reduce 能做的事情远不止求和——它可以模拟 map、filter 的行为，但没必要，用对应的方法更清晰。
选择建议速查表：
| 需求 | 推荐方法 |
|---|---|
| 需要 index 且可能中途退出 | for 循环 |
| 只要值，不需要 index | for...of |
| 需要 item + index + 原数组 | forEach（不能 break） |
| 每一项映射成新值 | map |
| 按条件筛选 | filter |
| 判断是否全部/部分满足 | every / some |
| 累加/聚合计算 | reduce |
2.6 二维数组与 fill 的坑
二维数组就是"数组的数组"，在算法题里经常作为矩阵出现。LLM 语境下的向量、矩阵计算，底层也是二维数组。
创建二维数组有一个经典陷阱：
const arr = (new Array(7)).fill([]);
arr[0][0] = 1;
console.log(arr);
// 你会发现 arr[1][0]、arr[2][0]……全部变成了 1！
原因是 fill([]) 只创建了一个空数组对象，然后把这一个对象的引用填进了七个槽位。七个槽指向的是同一个数组，改一个等于全改。
正确的做法是逐个槽位创建独立数组：
const arr = new Array(7);
for (let i = 0; i < arr.length; i++) {
arr[i] = []; // 每个槽位都是独立的新数组
}
arr[0][0] = 1;
console.log(arr); // 只有 arr[0] 受影响，其余六个还是空数组
遍历二维数组也很直观——嵌套循环：
const outerLen = arr.length;
for (let i = 0; i < outerLen; i++) {
const innerLen = arr[i].length;
for (let j = 0; j < innerLen; j++) {
console.log(arr[i][j], i, j);
}
}
一个小优化：把 arr.length 提到循环外面存成变量 outerLen，避免每次迭代都访问一次 .length 属性。.length 是对象属性访问，虽然 JS 引擎会做优化，但养成这个习惯没坏处。
2.7 JS 数组真的是数组吗
这个问题在笔记里被着重标记。答案是：不一定。
const arr1 = [1, 2, 3, 4]; // 元素类型一致
const arr2 = ['haha', 1, { a: 1 }]; // 元素类型不一致
当数组里所有元素类型一致时（比如全是数字），JS 引擎会用真正的连续内存来存——这是货真价实的数组，下标访问 O(1)。
当元素类型不一致时，连续内存没有意义（不同类型占用的字节数不同，偏移量算不了）。这时候 JS 引擎退化为用哈希表（HashTable）存储，通过键值对模拟下标访问。你依然可以写 arr2[2]，但底层走的是哈希查找，不是内存偏移量计算。
还有一个常踩的坑——sort 方法：
let arr = [10, 2, 5];
arr.sort(); // [10, 2, 5] —— 不对！
arr.sort((a, b) => a - b); // [2, 5, 10] —— 正确
sort() 默认按 ASCII 码（字典序） 排序，数字会被先转成字符串再比较。“10” 的第一个字符是 ‘1’，ASCII 码比 ‘2’ 小，所以 10 排在了 2 前面。对数字排序永远传比较函数，这是一个写一次就忘不掉的教训。
三、栈与队列：操作受限的数组
掌握了数组之后，栈和队列的理解成本就非常低了。它们本质上是操作受限的数组——不是不能做某些操作，而是约定只做某些操作。
为什么要"自我设限"？因为受限意味着行为可预测。栈保证后进先出，队列保证先进先出。在合适的场景下，这种约束让程序逻辑变得清晰。
3.1 栈（Stack）：LIFO
栈的规则只有一条：只能在栈顶操作。对应到数组，栈顶就是数组尾部——用 push 入栈，用 pop 出栈。
LIFO = Last In, First Out（后进先出）
可以把它想象成冰柜里的雪糕——你先放进去的埋在底下，最后放进去的在最上面，伸手拿到的永远是最后放进去那根。
const stack = []; // 空栈
stack.push("东北大板");
stack.push("可爱多");
stack.push("冰工厂");
stack.push("巧乐滋");
// 出栈：从栈顶一个一个往外拿
while (stack.length) {
const top = stack[stack.length - 1]; // peek：看一眼栈顶
console.log(`取出来的是`, top);
stack.pop(); // 真正出栈
}
console.log(stack); // [] 栈空了
几个关键操作：
- push — 入栈，往栈顶加元素
- pop — 出栈，从栈顶取走元素
- peek — 只看栈顶元素的值，不取走。JS 里就是
stack[stack.length - 1]
栈的应用场景非常多：浏览器后退按钮、函数调用栈（执行上下文）、括号匹配校验、表达式求值。你在 JS 里每调用一个函数，它就被 push 进调用栈；函数 return 时就 pop 出去。递归爆栈就是栈太深了——函数一层层 push 进去，迟迟不 pop，栈内存撑爆了。
3.2 队列（Queue）：FIFO
队列的规则也只有一条：只能队尾入队，队首出队。
FIFO = First In, First Out（先进先出）
跟排队取餐一样——先来的先取，后来的在后面等着。
const queue = []; // 空队列
queue.push('许');
queue.push('叶');
queue.push('戴');
while (queue.length) {
const top = queue[0]; // 看队首是谁
console.log(top, '取餐');
queue.shift(); // 队首出队
}
console.log(queue); // [] 队列空了
因为只能在队首删除，所以出队必须用 shift()。push + shift 就是 JS 里最简单的队列实现。
3.3 splice：数组增删的瑞士军刀
除了 push/pop/shift/unshift，还有一个更灵活的方法——splice。它能在数组的任意位置删除和插入：
array.splice(start_index, delete_count, ...items_to_add)
三个参数：
start_index— 从哪个位置开始操作delete_count— 删几个元素...items_to_add— 在删除位置插入的新元素（可选）
const arr = [1, 2];
arr.splice(1, 0, 3); // 在索引1处，删0个，插入3
console.log(arr); // [1, 3, 2]
arr.splice(1, 1); // 在索引1处，删1个
console.log(arr); // [1, 2]
splice 也是非纯函数——直接改原数组。它的返回值是被删除的元素组成的数组（没删东西就返回空数组）。
四、链表：另一种"列表"
栈和队列属于"操作受限的数组"，但数组本身有一个结构性的弱点：增删成本高。往数组中间插入一个元素，后面所有元素都要往后挪一位。删一个元素，后面所有元素都要往前补。这个开销随数组长度线性增长——O(n)。
链表就是为了解决这个问题而生的。
4.1 链表 vs 数组：两种哲学
| 维度 | 数组 | 链表 |
|---|---|---|
| 存储方式 | 连续内存 | 离散分布 |
| 访问元素 | O(1)，按索引直接定位 | O(n)，从头一个个找 |
| 增删元素 | O(n)，需要移动后续元素 | O(1)，只改指针指向 |
| 内存分配 | 扩容时整块搬迁 | 每次增删申请/释放一个节点 |
数组和链表都是有序列表（List），都是线性结构——有且仅有一个前驱、有且仅有一个后继。区别在于"有序"的实现方式不同：数组靠内存连续来维持顺序，链表靠指针（next 引用）来串联。
选型的经验法则：数据量小用数组，遍历和索引访问快；数据量大且频繁增删用链表，避免反复搬迁。但实际前端开发中，数组的适用场景远多于链表——JS 引擎对数组做了大量优化，小规模数据的增删开销几乎可以忽略。
4.2 节点的 JS 表达
链表的每个节点包含两块信息：数据和指向下一个节点的指针。
function ListNode(val) {
this.val = val; // 数据域
this.next = null; // 指向下一个节点的指针
}
const node1 = new ListNode(1);
node1.next = new ListNode(2);
console.log(node1);
// { val: 1, next: { val: 2, next: null } }
也可以用纯对象字面量表达：
{
val: 1,
next: {
val: 2,
next: {
val: 3,
next: null
}
}
}
链表的头节点叫 head，尾节点叫 tail（它的 next 指向 null）。要访问链表里的任意一个元素，必须从 head 开始，顺着 next 一路找下去——这就是链表访问是 O(n) 的原因。
4.3 增删操作的本质
链表增删元素的核心操作只有一句话：改前驱节点的 next 指针。
- 插入：新节点的
next指向前驱节点原本的next，前驱节点的next指向新节点 - 删除：前驱节点的
next直接跨过要删除的节点，指向它的next
不用担心"坐过站"——只要你在改指针之前记下了目标节点的引用，就不会丢失后面的链。
这也是链表增删是 O(1) 的原因：不管链表多长，你只需要改一两个指针的指向，不涉及任何元素的移动。反观数组，中间插一个元素要挪动后面所有元素，O(n)。
但注意——这里的 O(1) 有个前提：你已经知道要插入/删除的位置。如果你不知道位置，需要从头遍历去找，那总复杂度还是 O(n)（O(n) 查找 + O(1) 操作）。
五、树与二叉树
数组、栈、队列、链表都是线性结构——一个接一个，顺序明确。树则是非线性结构，一个节点可以分出多个分支。树结构在计算机世界里无处不在：DOM 树、文件系统、数据库索引（B+ 树）、抽象语法树（AST）……
5.1 树的基本概念
数据结构的树是对现实世界树的简化：
- 根节点 — 树的最顶层，一棵树只有一个根
- 边 — 连接节点的线，对应现实中的树枝
- 叶子节点 — 没有子节点的节点，对应树叶
- 层次 — 根节点是第一层，它的子节点是第二层，以此类推
- 高度 — 叶子节点高度为 1，每往上一层高度 +1。树的高度就是根节点的高度
- 度 — 一个节点分叉出去多少个子树。叶子节点的度为 0
注意：计算机里的树通常是倒过来画的——根在上，叶子在下。这跟现实中树的方向相反，初次接触可能有点别扭，习惯了就好。
5.2 二叉树的递归定义
二叉树不是"每个节点最多有两个子节点"这么简单。它的完整定义是用递归写的：
二叉树可以是空树。如果不是空树，它必须由根节点、左子树和右子树组成，且左右子树也都是二叉树。
这里面有三个关键点：
- 递归定义——用二叉树来定义二叉树，这是递归思想的核心
- 左右子树严格区分——左子树和右子树的位置不能交换。交换了就变成另一棵树
- 空树也是二叉树——这给递归提供了出口
递归三要素（在 5.5 节会结合爬楼梯问题展开）：
- 自顶向下思考——把大问题分解成小问题
- 递归公式——每次解决同样模式的问题，找到递推关系
- 退出条件——到某个规模直接返回结果，不再递归
5.3 在 JS 中表示一棵树
最简单的方式是用构造函数定义节点：
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
三个属性：
val— 数据域，存节点的值left— 左子节点的引用right— 右子节点的引用
用对象字面量搭一棵具体的树：
const tree = {
val: 'A',
left: {
val: 'B',
left: { val: 'D', left: null, right: null },
right: { val: 'E', left: null, right: null }
},
right: {
val: 'C',
left: { val: 'F', left: null, right: null },
right: { val: 'G', left: null, right: null }
}
};
这棵树的形状：
A
/ \
B C
/ \ / \
D E F G
5.4 四种遍历方式
二叉树的遍历分两大类：深度优先（DFS）和广度优先（BFS）。DFS 按根节点的访问顺序又分为前序、中序、后序三种。BFS 就是层序遍历。
所有遍历都遵循一个铁律：先左后右。
① 前序遍历（Preorder）：根 → 左 → 右
function preorder(root) {
if (!root) return; // 退出条件
console.log(`当前遍历节点值是：`, root.val); // 先访问根
preorder(root.left); // 再递归左子树
preorder(root.right); // 最后递归右子树
}
// 对上面的树：A → B → D → E → C → F → G
② 中序遍历（Inorder）：左 → 根 → 右
function inorder(root) {
if (!root) return;
inorder(root.left); // 先递归左子树
console.log(`当前遍历节点值是：`, root.val); // 再访问根
inorder(root.right); // 最后递归右子树
}
// 对上面的树：D → B → E → A → F → C → G
BST（二叉搜索树）的中序遍历结果是一个有序序列——这是中序遍历最经典的应用。
③ 后序遍历（Postorder）：左 → 右 → 根
function postorder(root) {
if (!root) return;
postorder(root.left); // 先递归左子树
postorder(root.right); // 再递归右子树
console.log(`当前遍历节点值是：`, root.val); // 最后访问根
}
// 对上面的树：D → E → B → F → G → C → A
后序遍历的一个典型应用是计算目录大小——先算出所有子目录的大小，再汇总到父目录。
④ 层序遍历（Level Order）：一层一层来
层序遍历不走递归，走队列：
function levelOrder(root) {
const queue = [];
const result = [];
if (!root) return result;
queue.push(root); // 根节点入队
while (queue.length) {
const node = queue.shift(); // 队首出队
result.push(node.val); // 记录当前节点值
if (node.left) queue.push(node.left); // 左子入队
if (node.right) queue.push(node.right); // 右子入队
}
return result;
}
// 对上面的树：A → B → C → D → E → F → G
层序遍历的精髓在于：访问一个节点时，把它的左右子节点丢进队列末尾。因为队列是 FIFO 的，同一层的节点一定会按顺序被处理。这里巧妙地把"树"的问题转化成了"队列"的问题——数据结构之间不是孤立的。
四种遍历方式速查：
| 遍历方式 | 顺序 | 实现方式 | 典型应用 |
|---|---|---|---|
| 前序 | 根→左→右 | 递归 | 序列化树、复制树 |
| 中序 | 左→根→右 | 递归 | BST 有序输出 |
| 后序 | 左→右→根 | 递归 | 目录大小计算、删除树 |
| 层序 | 逐层 | 队列迭代 | 求树的宽度、BFS |
5.5 递归思想：爬楼梯问题
笔记里用爬楼梯（LeetCode 70）来练习递归。这个例子非常经典：
爬 n 级台阶，每次可以爬 1 级或 2 级，有多少种不同的爬法？
自顶向下思考：爬到第 n 级，上一步要么在第 n-1 级（然后爬 1 级），要么在第 n-2 级（然后爬 2 级）。所以 f(n) 的爬法 = f(n-1) 的爬法 + f(n-2) 的爬法。
递归公式：f(n) = f(n-1) + f(n-2)
退出条件：f(1) = 1（只有 1 级，一种爬法），f(2) = 2（1+1 或 2，两种爬法）
function climbStairs(n) {
if (n == 1) return 1;
if (n == 2) return 2;
return climbStairs(n - 1) + climbStairs(n - 2);
}
这个实现有一个严重问题：大量重复计算。climbStairs(100) 会直接卡死——因为 f(3) 被算了上亿次。
f(5)
/ \
f(4) f(3)
/ \ / \
f(3) f(2) f(2) f(1)
/ \
f(2) f(1)
可以看到 f(3) 算了两次，f(2) 算了三次。n 越大，重复越恐怖。实际面试中记得提一嘴"可以用记忆化搜索（memo）或动态规划（DP）优化"，这本身就展示了你对递归局限性的理解。
六、总结
回顾一下整套笔记覆盖的知识体系：
数据结构（JS 视角）
├── 数组
│ ├── 本质：连续内存 + 下标访问（ADT）
│ ├── 创建：字面量 / new Array(n) / fill()
│ ├── 增删：push、pop、shift、unshift、splice（非纯函数）
│ ├── 遍历：for / for...of / forEach / map / filter / every / some / reduce
│ ├── 二维数组：fill([]) 的引用陷阱
│ └── JS 特色：元素类型不同时退化为哈希表
├── 栈（LIFO）：push + pop，受限操作
├── 队列（FIFO）：push + shift，受限操作
├── 链表
│ ├── 节点 = val + next
│ ├── 增删 O(1)，访问 O(n)
│ └── 与数组的互补关系
└── 二叉树
├── 递归定义（空树 | 根 + 左子树 + 右子树）
├── 遍历：前序 / 中序 / 后序（递归） + 层序（队列迭代）
└── 递归思维：公式 + 退出条件
从数组到树，核心的进阶线索是：线性 → 非线性，连续 → 离散，迭代 → 递归。数组是连续内存、下标直接定位；链表是离散节点、指针串联；树把这种串联从"一对一"扩展到了"一对多"，递归成了最自然的思维方式。
这些数据结构本身不难，难的是在做题时一眼看出题目背后对应的是哪种结构。数组题用双指针、滑动窗口，栈用来做括号匹配和表达式求值，队列用来做 BFS，树几乎必考递归遍历——这些对应关系，就是后续刷题时要刻意建立的直觉。
感谢阅读。如果这篇文章对你有帮助，欢迎点赞和关注，后续会继续更新算法和前端基础相关的学习笔记。
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
4
0- 0
已为社区贡献3条内容
所有评论(0)