数据结构层面，大家需要掌握以下几种：
- 数组
- 栈
- 队列
- 链表
- 树（这里我们着重讲二叉树）
对于这些数据结构，各位如果没有大量的可支配时间可以投入，那么其实不建议找厚厚的大学教材来刷。此时此刻，时间为王，我们追求的是效率的最大化。
不同的数据结构教材，对数据结构有着不同的划分、不同的解读、不同的编码实现。在这里，我们面向 JavaScript，面向前端面试，只针对大家后续做题、答题时会用到的最贴合实战的数据结构特性&编码技能作讲解。
- 这两节我们所提及的基础知识细节，很可能会成为你后面写代码的关键线索。
- 不要因为乍一看觉得简单，就急着跳读急着做题。
- 不然你很可能做题做到一半，会不知道自己到底为什么就卡了壳。
- 到时候万一又因为懒得回头看，而原地卡死，那就更做不下去了orz。
注：由于 JavaScript 中字符串和数组关联紧密，关键知识点重复度较高，故我们在数据结构部分，不再单独为字符串保留篇幅。字符串相关的知识点，我们直接带到后续的解题技巧归纳专题里去看。
# 数组
30 秒速记
- 做题时把数组当成「按下标直接取」的盒子：读写下标按
O(1)算 - 尾部
push/pop均摊O(1)；头部unshift/shift要挪后面所有元素 →O(n) JS数组不保证是连续内存，V8会按元素类型和稀疏程度换内部表示，别把「底层一定连续」当标准答案new Array(n)是一排空槽，map/forEach会跳过；要初值用Array(n).fill(0)- 二维数组别用
fill([])，每行要单独创建：Array.from({ length: rows }, () => Array(cols).fill(0))
算法题里数组就是一个按下标直接取值的容器，读写下标算 O(1)，尾部增删算 O(1)，头部增删算 O(n)。 打个比方，数组像电影院一排座位，知道座位号就能直接走过去；但有人要插到第一个，后面所有人都得往后挪一位。JS 这边要多说一句，它的 Array 是语言层的抽象，V8 会根据元素是整数、浮点还是对象、有没有空洞来选内部存储，所以「底层一定是连续内存」这话不严谨。实际写题真正会坑人的是两件事：new Array(3) 只有长度没有元素，还有 fill([]) 让所有行共用一个数组。
先补一个算法面试里常被忽略的前提：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 亦然。这意味着我们可以对数组做到“开箱即用”，而不必自行模拟实现，非常方便。
考虑到日常开发过程中，数组的出镜率本身已经很高，相信它也是大多数同学最熟悉的数据结构。 即便如此，这里仍然需要提醒各位：要对数组格外走点心，毕竟后面需要它帮忙的地方会非常多。
面试官追问
追问 1arr.shift() 和 arr.pop() 都是删一个元素，复杂度为什么不一样？
pop 删最后一个，别的元素下标不动；shift 删第一个，剩下每个元素下标都要减一，元素越多挪得越多。所以 BFS 这种要频繁出队的场景，别拿 shift 当队列用，维护一个 head 下标就行。
追问 2new Array(3) 和 [undefined, undefined, undefined] 打印出来差不多，有区别吗？
有。0 in new Array(3) 是 false，那个位置压根不存在；显式写 undefined 的数组 0 in arr 是 true。区别会体现在 map、forEach、Object.keys 上，空槽会被跳过。
追问 3有人说 JS 数组放了不同类型就变成链表了，对吗？
不对。混合类型在 V8 里只是换成存「指向堆对象的指针」那种 elements kind，背后还是连续的一段存储。真正会退化成哈希表（字典模式）的是特别稀疏的数组，比如 arr[1000000] = 1 这种。
追问 4一个 10000 × 10000 的矩阵，绝大部分是 0，你还会老老实实建二维数组吗？
不会，那是一亿个格子，内存先扛不住。只存非零点就行，比如用一个 Map，键写成 row + ',' + col，或者按行建 Map，空间降到和非零元素数量成正比。
# 数组的创建
30 秒速记
- 已知内容用字面量
[1, 2, 3]；new Array()和[]等价 new Array(7)只给长度不给元素，是7个空槽，map/forEach会直接跳过- 要初值：基本类型用
new Array(n).fill(1)，对象/数组用Array.from({ length: n }, () => ({})) - 小坑：
new Array(3)是长度3，new Array(3, 4)却是[3, 4]，单个数字参数才表示长度；想稳就用Array.of
创建数组先分清楚「有长度」和「有元素」，new Array(3) 只有长度，里面是三个空槽。 这就像订了三个座位但没人坐，map 遍历的时候会直接跳过这些座位，所以 new Array(3).map(() => 0) 拿到的还是空槽。要真正填值，基本类型用 fill，比如 new Array(7).fill(1)；要填对象就得用 Array.from({ length: 7 }, () => ({ done: false }))，让每个位置调一次工厂函数，拿到各自独立的对象。
大家平时用的最多的创建方式想必就是直接方括号+元素内容这种形式：
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的数组：
面试官追问
追问 1new Array(3).map(() => 0) 为什么结果不是 [0, 0, 0]？
map 只处理真实存在的元素，空槽直接跳过，回调一次都没执行。先 fill 再 map，或者直接 Array.from({ length: 3 }, () => 0)。
追问 2任务列表用 new Array(7).fill({ done: false }) 初始化，勾一个全勾上了，为什么？
fill 放进去的是同一个对象的引用，arr[0] === arr[6] 是 true，改谁都是改同一个。换成 Array.from({ length: 7 }, () => ({ done: false }))，回调每次 new 一个新对象。
