前端算法入坑指南：用 JavaScript 一口气搞懂数组、栈、队列、链表和二叉树

前端算法入坑指南：用 JavaScript 一口气搞懂数组、栈、队列、链表和二叉树

用 JS 重新理解最基础的数据结构，面向面试，从零搭建知识体系。 涵盖数组的底层机制、栈与队列的受限操作、链表的增删优势、二叉树的递归遍历。

目录

• JavaScript 数据结构三讲：数组 · 栈与队列 · 树
  • 目录
  • 一、为什么要重新学数据结构
  • 二、数组：最熟悉也最陌生的老朋友
    • 2.1 数组的本质：连续内存 + 下标寻址
    • 2.2 创建数组的几种姿势
    • 2.3 增删方法：谁动了原数组
    • 2.4 纯函数与非纯函数
    • 2.5 遍历的六种方式，怎么选
    • 2.6 二维数组与 fill 的坑
    • 2.7 JS 数组真的是数组吗
  • 三、栈与队列：操作受限的数组
    • 3.1 栈（Stack）：LIFO
    • 3.2 队列（Queue）：FIFO
    • 3.3 splice：数组增删的瑞士军刀
  • 四、链表：另一种"列表"
    • 4.1 链表 vs 数组：两种哲学
    • 4.2 节点的 JS 表达
    • 4.3 增删操作的本质
  • 五、树与二叉树
    • 5.1 树的基本概念
    • 5.2 二叉树的递归定义
    • 5.3 在 JS 中表示一棵树
    • 5.4 四种遍历方式
    • 5.5 递归思想：爬楼梯问题
  • 六、总结

一、为什么要重新学数据结构

数据结构是程序员的基本功，但很多前端同学接触得晚。Vue、React 用熟了，业务代码写了不少，一到算法面试就犯怵——因为框架替你把数据结构封装好了，日常开发很少直接跟链表、树打交道。

这套笔记的核心思路是：用 JavaScript 的视角重新走一遍数据结构，从数组开始，到栈和队列，再到树。不需要学 C 语言再来搞这个，就用你每天写的 JS，把底层逻辑搞懂。

三个原则贯穿始终：

二、数组：最熟悉也最陌生的老朋友

数组是每个 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 数组增删的核心方法有四个：

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 的行为，但没必要，用对应的方法更清晰。

选择建议速查表：

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 数组：两种哲学

数组和链表都是有序列表（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 的，同一层的节点一定会按顺序被处理。这里巧妙地把"树"的问题转化成了"队列"的问题——数据结构之间不是孤立的。

四种遍历方式速查：

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，树几乎必考递归遍历——这些对应关系，就是后续刷题时要刻意建立的直觉。

感谢阅读。如果这篇文章对你有帮助，欢迎点赞和关注，后续会继续更新算法和前端基础相关的学习笔记。