快速上手——从0到1掌握算法面试需要的数据结构（一）|算法篇
数据结构层面，大家需要掌握以下几种：
- 数组
- 栈
- 队列
- 链表
- 树（这里我们着重讲二叉树）
对于这些数据结构，各位如果没有大量的可支配时间可以投入，那么其实不建议找厚厚的大学教材来刷。此时此刻，时间为王，我们追求的是效率的最大化。
不同的数据结构教材，对数据结构有着不同的划分、不同的解读、不同的编码实现。在这里，我们面向 JavaScript，面向前端面试，只针对大家后续做题、答题时会用到的最贴合实战的数据结构特性&编码技能作讲解。
- 这两节我们所提及的基础知识细节，很可能会成为你后面写代码的关键线索。
- 不要因为乍一看觉得简单，就急着跳读急着做题。
- 不然你很可能做题做到一半，会不知道自己到底为什么就卡了壳。
- 到时候万一又因为懒得回头看，而原地卡死，那就更做不下去了orz。
注：由于 JavaScript 中字符串和数组关联紧密，关键知识点重复度较高，故我们在数据结构部分，不再单独为字符串保留篇幅。字符串相关的知识点，我们直接带到后续的解题技巧归纳专题里去看。
# 数组
30 秒速记
- JavaScript 数组是按整数索引组织的动态容器，不保证像 C 语言数组那样把所有元素连续存成同一种值
- 算法题里最重要的不是 API 数量，而是索引访问期望
O(1)、尾部增删通常O(1)，头部插删需要搬移元素所以是O(n) new Array(n)创建的是稀疏数组，空槽与值为undefined不完全等价；要初始化数值状态可用Array(n).fill(0)fill([])会把同一个数组引用填进所有位置；二维数组应使用Array.from({ length: rows }, () => Array(cols).fill(0))- 遍历矩阵前先确认是不是规则矩阵；不规则数组每行长度不同，内层边界必须取
matrix[row].length
JavaScript 的 Array 是按整数索引访问的动态容器，不能简单等同于 C 语言中元素同类型且内存连续的数组。 算法题通常把索引读写按期望 O(1) 分析，尾部增删通常也是 O(1)，而头部插删会影响后续索引，一般是 O(n)。new Array(n) 产生空槽；初始化二维数组时要为每一行单独创建数组，避免 fill([]) 共享引用。遇到不规则矩阵，内层边界还要使用当前行的 length。
先补一个算法面试里常被忽略的前提：JavaScript 的 Array 是语言抽象，V8 会根据元素类型和稠密程度选择不同内部表示，所以不能把“底层永远是一段连续内存”当成通用答案。但在解题模型中，按索引读取仍按期望 O(1) 分析；shift() / unshift() 会影响后续索引，通常按 O(n) 处理。
下面这段代码可以直接验证“空槽”和显式 undefined 的差异，以及二维数组正确初始化方式：
const sparse = new Array(3)
const explicit = [undefined, undefined, undefined]
console.log(0 in sparse) // false：0 号位置是空槽
console.log(0 in explicit) // true：位置存在，只是值为 undefined
console.log(sparse.map(() => 1)) // [ <3 empty items> ]，map 会跳过空槽
const rows = 2
const cols = 3
const matrix = Array.from({ length: rows }, () => Array(cols).fill(0))
matrix[0][0] = 7
console.log(matrix) // [[7, 0, 0], [0, 0, 0]]
这里的关键不变量是：matrix[i] 必须是一次独立创建的数组。若写成 Array(rows).fill(Array(cols).fill(0))，所有行引用同一个对象，修改一行会污染全部行。初始化时间和空间都是 O(rows × cols)；当矩阵很大且绝大多数位置为零时，应考虑 Map 保存非零坐标，而不是无条件分配完整二维数组。
数组是各位要认识的第一个数据结构。
作为最简单、最基础的数据结构，大多数的语言都天然地对数组有着原生的表达，JavaScript 亦然。这意味着我们可以对数组做到“开箱即用”，而不必自行模拟实现，非常方便。
考虑到日常开发过程中，数组的出镜率本身已经很高，相信它也是大多数同学最熟悉的数据结构。 即便如此，这里仍然需要提醒各位：要对数组格外走点心，毕竟后面需要它帮忙的地方会非常多。
# 数组的创建
30 秒速记
- 字面量
[]适合已知元素；new Array(length)适合先占长度，但得到的是会被map、forEach跳过的空槽 - 需要真正的初始值时用
Array.from({ length }, factory)；原始值也可用fill，引用值不能直接fill({})或fill([]) - 长度来自输入时先校验非负整数和容量上限，避免
RangeError或一次性分配过大数组
创建数组时要先分清“设置了长度”和“真正放入了元素”，new Array(3) 只有长度，并没有三个可遍历的值。 已知内容时可以直接写数组字面量，例如 [1, 2, 3]；只需要空数组时，new Array() 与 [] 等价。若长度和初始值都确定，可以使用 new Array(7).fill(1)，这样每个位置才会实际填入 1。
大家平时用的最多的创建方式想必就是直接方括号+元素内容这种形式：
const arr = [1, 2, 3, 4]
不过在算法题中，很多时候我们初始化一个数组时，并不知道它内部元素的情况。这种场景下，要给大家推荐的是构造函数创建数组的方法：
const arr = new Array()
当我们以构造函数的形式创建数组时，若我们像楼上这样，不传任何参数，得到的就会是一个空数组。等价于：
const arr = []
不过咱们使用构造函数，可不是为了创建空数组这么无聊。
我们需要它的时候，往往是因为我们有“创造指定长度的空数组”这样的需求。需要多长的数组，就给它传多大的参数：
const arr = new Array(7)
这样的写法就可以得到一个长度为7的数组：
在一些场景中，这个需求会稍微变得有点复杂—— “创建一个长度确定、同时每一个元素的值也都确定的数组”。这时我们可以调用 fill 方法，假设需求是每个坑里都填上一个1，只需给它 fill 一个1：
const arr = (new Array(7)).fill(1)
如此便可以得到一个长度为7，且每个元素都初始化为1的数组：
面试官追问
追问 1页面初始化代码写成 new Array(3).map(() => 0)，渲染时三个位置仍是空槽；为什么 length 明明为 3，回调却没有执行？
new Array(3) 创建的是指定长度的稀疏数组，三个位置并没有实际元素，map 会跳过这些空槽。需要确定初值时可写 new Array(3).fill(0)，或用 Array.from({ length: 3 }, () => 0)；不能把长度存在等同于元素已赋值。
追问 2算法页面要创建长度为 n、初值全为 1 的计数数组，你会选择哪种初始化写法并说明边界？
元素都是同一个基本类型值时，可使用 new Array(n).fill(1)，表达直接且符合指定长度初始化的需求。n 应是合法的非负长度，后续仍要按算法约束处理空数组；若填充的是可变对象，则不能照搬这种共享引用的写法。
追问 3需求改成长度为 7 的任务状态数组，每项都要独立修改 { done: false }；为什么 new Array(7).fill({ done: false }) 不合适？
fill 会把同一个对象引用放进所有位置，修改某一项的 done 可能让其他项同时变化。应使用 Array.from({ length: 7 }, () => ({ done: false }))，让回调每次创建新对象；这种写法会产生多个实例，但换来了状态隔离。
追问 4线上表单勾选第 2 行后所有行都变成已完成，数组由 fill 初始化；你会怎样快速定位并修复？
先检查初始化值是否为对象，以及各元素是否满足引用相等；若全部指向同一对象，故障就来自共享引用。改为逐项创建对象，再确认更新逻辑只替换目标下标；若状态对象内部还有嵌套可变值，也要继续检查更深层的共享。
追问 5团队在 []、new Array(n) 和 new Array(n).fill(value) 之间争论统一规范，你会按什么场景选型？
内容已知时直接使用数组字面量最清晰，只知道目标长度时可用 new Array(n)，需要确定初值时再配合 fill。稀疏数组会影响遍历方法的行为，而对象填充会共享引用；因此不宜强行统一成一种写法，应让初始化语义与后续访问方式一致。
# 数组的访问和遍历
30 秒速记
- 下标读取和写入按解题模型通常是
O(1)，合法索引范围是0到length - 1 forEach用于副作用且不能正常break；map必须返回新值；需要提前结束或精确控制下标时优先for/for...of- 稀疏数组会让
map、forEach跳过空槽，而for...of会读出undefined，选遍历方式前要明确数据是否稠密
数组通过下标读写，合法范围是 0 到 length - 1，在算法分析中通常按 O(1) 处理。 只做遍历副作用可以用 forEach，需要生成新数组则用 map，因为它会根据回调返回值构造结果。要提前结束循环或精确控制下标时，我一般会选 for 或 for...of。还要注意稀疏数组：map 和 forEach 会跳过空槽，而 for...of 会把空槽读成 undefined。
栈、队列与链表 →
