1. 为什么JS里有了Array还要自己实现ArrayList1.1 很多人忽略的事实JS的Array不是传统意义上的数组看到这个标题第一反应大概率是JS的Array本身就是动态数组push、pop、splice全都有为什么还要自己写一个ArrayList这不是重复造轮子吗我一开始也是这么想的直到我认真翻了V8的源码逻辑之后才意识到这个想法有一个根本性的盲区——JS的Array底层实现并不是一个纯粹的连续内存数组它其实是“带数组外壳的对象”。在绝大多数JS引擎里数组元素实际上是作为对象的属性被存储的。索引0、1、2本质上是对象的key只是引擎做了特殊的优化在V8中称为ElementsKind让它在表现上接近数组。当你不断改变元素类型、进行稀疏赋值或删除中间元素时引擎会退化到更慢的字典模式。简单说原生Array是一个“自适应”的数据结构它为了通用性牺牲了一部分可预测性。这就带来一个很实际的问题刷算法题的时候你最需要的是可预测的时间复杂度和空间行为而原生Array在这些方面其实是“黑盒”——你往数组里塞了100万个数字引擎内部是用了PACKED_SMI_ELEMENTS还是DICTIONARY_ELEMENTS你没法控制。自己实现一个ArrayList正是为了把这一层“黑盒”变成“白盒”。1.2 标题背后真正要解决的三个问题这个标题表面上只有三个词数组、字符串、ArrayList但它实际上涵盖了刷题场景中三类基础却高频的能力第一数组操作的基本功。很多新手刷题写着写着发现自己竟然会被slice和splice搞混或者不知道为什么sort()排序结果不符合预期。这些API层面的问题不解决题目思路再清楚也没用。第二字符串处理的基本功。字符串在JS里是不可变的任何replace、split、toUpperCase调用都会返回新字符串频繁操作会带来大量内存分配。很多性能问题其实是字符串处理方式不当导致的。第三自己动手实现一个基础容器。很多人用了一年JS的Array问他扩容是怎么做的、为什么push的均摊复杂度是O(1)、为什么在数组中间插入元素是O(n)答不上来。这些恰恰是面试和竞赛中最常考的基础概念。所以这个标题下的内容本质上是让自己把“会用数组”升级为“理解数组”顺带补上字符串处理中容易踩的坑。1.3 哪些人适合认真看完这篇内容如果你是刚开始用JS刷算法题建议认真读一遍尤其是第3章的实现部分花二十分钟把代码自己敲一遍收获会非常大。如果你是准备面试的前端开发者第3章的扩容分析部分可以直接拿来应答“ArrayList的扩容机制”相关问题。如果你已经刷题很久了也可以快速扫一遍第2章的易错点清单查漏补缺。这篇内容不像教科书那样讲一堆理论而是完全围绕刷题场景展开每段都有对应的代码和实测数据你可以直接把代码复制到自己项目里跑一遍验证。2. 数组与字符串在刷题中的高频操作与易错点2.1 数组高频API清单哪些好用哪些有坑先列一个我刷题实战中最常用到的数组方法以及它们的关键边界条件方法作用是否改变原数组易错点push(value)尾部添加是返回新长度而非数组本身pop()尾部删除是空数组返回undefinedshift()头部删除是O(n)复杂度慎用unshift(value)头部添加是O(n)复杂度慎用slice(start, end)截取子数组否end参数是开区间不含末尾splice(start, count, ...)删除/插入是第二个参数是删除个数不是结束位置concat(arr)合并数组否非浅拷贝引用类型仍是同一引用indexOf(item)查找索引否无法查找NaN用includessort(compareFn)排序是不加比较函数时按字典序排序reverse()反转是原地反转fill(value, start, end)填充是填充的是同一引用这里最值得单独拎出来说的坑是sort。[10, 9, 100].sort()的结果是什么答案是[10, 100, 9]因为它把元素都转成了字符串再按字典序排序。所以刷题时只要排序的元素不是字符串就要立即补上比较函数nums.sort((a, b) a - b)。这是我见过的新手错误率最高的一个点。另一个容易被忽视的坑是shift和unshift的O(n)复杂度。很多人刷题时习惯用数组模拟队列shift一下觉得没什么但数据量大了之后性能会迅速劣化。如果确实需要频繁从头部增删可以考虑用一个头部指针来避免物理位移或者直接用专门的数据结构来模拟这一点在第4章还会展开。2.2 字符串操作不可变性是万恶之源JS字符串的不可变性是刷字符串题时所有性能坑的根源。字符串的split、replace、slice等方法都不会改变原字符串而是返回一个新字符串。这意味着在一个循环里反复做拼接操作每一轮都会创建新字符串旧字符串被GC掉内存和耗时都在白白增加。举个例子如果需要在循环里拼10000次字符串let str ; for (let i 0; i 10000; i) { str i; }这段代码的复杂度是O(n²)——每轮都要把旧字符串拷贝一遍再加上新内容。我实测过10000次拼接大约需要5~10毫秒看起来不多但如果是100万次就直接暴涨到几秒。换成先把内容push到数组里再一次性join耗时能降到原来的几十分之一。还有一个和字符串相关的高频操作组合是split、reverse、join这也是反转字符串题目的常见解法。但这里有一个隐藏的割裂点如果你处理的字符串包含中文、emoji或者组合字符split()会直接把一个完整的字符拆成两个部分。比如.split()得到的结果是两个孤立的代理对字符。这种情况下用Array.from(str)才能正确地逐字符分割。2.3 刷题时关于字符串拼接的性能实测记录为了验证上面的说法我专门做了一个简单的对比测试。测试环境就是普通的Chrome浏览器没有开任何沙盒之类的特殊设定。测试场景是把1到50000的数字用分隔符合并成一个大字符串// 方式一直接 let s1 ; let t1 Date.now(); for (let i 0; i 50000; i) { s1 i ,; } console.log(直接拼接耗时:, Date.now() - t1, ms); // 方式二先用数组收集再 join let arr []; let t2 Date.now(); for (let i 0; i 50000; i) { arr.push(i); } const s2 arr.join(,); console.log(push join 耗时:, Date.now() - t2, ms);最终结果方式一大概在15ms左右方式二稳定在4ms以下。而且随着循环次数的增加这个差距会越来越拉开因为直接拼接的O(n²)特征非常明显。注意这个测试是在数据量只有五万的情况下得出的。如果你恰好有一段字符串拼接的逻辑导致在线判题系统始终提交超时第一反应不应该是换思路而是先看看是不是拼接写成了改成push加一次join往往立刻就能通过。3. ArrayList的简单实现扩容、插入、删除、遍历3.1 为什么模板要选ArrayList而不是LinkedList既然决定自己实现一个动态数组为什么选ArrayList作为蓝本而不是LinkedList原因有两点。第一动态数组在刷题中的使用频率远高于链表模拟。LRU缓存、单调栈、双指针等场景虽然用链表思维建模但最终在代码里大部分情况下用的还是数组索引。数组对CPU缓存更友好遍历速度快得多。第二ArrayList的扩容机制是面试的高频考点而链表的指针操作细节相对琐碎。用JS实现ArrayList代码量适中又能完整覆盖“扩容—插入—删除—遍历”这条主线性价比最高。如果你刷的是用Java写题解的题目会经常看到new ArrayList(initialCapacity)这样的初始化方式。这个预分配容量的思想在我们自己的实现里也可以保留。3.2 从零写一个可用的ArrayList类完整带注释代码下面给出我认为“简单但不简陋”的版本。没有用ES6的类语法以外的任何花哨特性保证看一眼就能理解核心逻辑。class ArrayList { constructor(initialCapacity 10) { // 预分配底层连续空间的长度 this.capacity initialCapacity; // items 用于存放实际元素 this.items new Array(this.capacity); // size 记录当前元素数量同时是下一个可写入位置的指针 this.size 0; } // 扩容扩容为原来的2倍 _resize() { this.capacity this.capacity * 2; const newItems new Array(this.capacity); for (let i 0; i this.size; i) { newItems[i] this.items[i]; } this.items newItems; } // 尾部添加 push(value) { // 如果空间用完先扩容 if (this.size this.capacity) { this._resize(); } this.items[this.size] value; this.size; } // 按下标访问越界时显式抛错 get(index) { this._checkIndex(index); return this.items[index]; } // 修改指定下标的值 set(index, value) { this._checkIndex(index); this.items[index] value; } // 在指定位置插入 insertAt(index, value) { if (index 0 || index this.size) { throw new Error(索引越界); } if (this.size this.capacity) { this._resize(); } // 从后往前搬移给新元素腾出位置 for (let i this.size - 1; i index; i--) { this.items[i 1] this.items[i]; } this.items[index] value; this.size; } // 删除指定位置的元素返回被删除的值 removeAt(index) { this._checkIndex(index); const removed this.items[index]; // 从前往后搬移覆盖被删除的位置 for (let i index; i this.size - 1; i) { this.items[i] this.items[i 1]; } this.size--; this.items[this.size] undefined; // 清掉尾部残留引用 return removed; } // 当前元素个数 length() { return this.size; } // 内部用检查索引是否合法 _checkIndex(index) { if (index 0 || index this.size) { throw new Error(索引越界); } } }这个版本总共不到70行但完整覆盖了四个关键操作尾部添加、按下标访问、任意位置插入、任意位置删除。你可能会问push方法很简单为什么要用this.items[this.size]而不是this.items.push因为这里已经预先用new Array(capacity)创建了固定长度的空间直接按下标赋值更贴近“手动管理底层容器”的语义。反过来如果用了原生push扩容的那个逻辑就名存实亡了。3.3 扩容原理与复杂度分析为什么倍数扩容是标准答案面试官问“ArrayList是怎么扩容的”标准回答是默认容量不够时扩大到原来的1.5倍或2倍然后把旧元素复制到新数组。但为什么是倍数而不是每次固定增加10个位置这背后是均摊复杂度的概念。假设初始容量为1每次扩容多1个空间。push第2个元素时要扩容拷贝1个push第3个时扩容拷贝2个push第4个时拷贝3个……push第n个时总共拷贝了123...(n-1) ≈ n²/2次单次push的均摊代价是O(n)。也就是说固定大小扩容会让n次push的总成本退化成O(n²)。如果用“每次容量翻倍”的策略假设容量从1涨到2、4、8、16……到容量为n时总拷贝次数是124...n/2 ≈ n-1所以n次push的总成本是O(n)单次均摊下来就是O(1)。这是倍增扩容最经典的优势。那在实现里为什么给的是2倍而不是1.5倍实际上2倍实现最简单因为整数位移一位就是乘以2。但2倍的缺点是空间浪费相对严重你存了1000个元素底层数组可能是4096的长度浪费率超过75%。Java的ArrayList选择1.5倍是空间和时间的一个折中。我在这里选2倍纯粹是为了让代码更易读也方便理解“均摊O(1)”这个结论。3.4 与原生Array的性能差异实测手撸的ArrayList和原生Array相比到底差多少我做一个公平的对照实验都执行100万次尾插。const list new ArrayList(); let t1 Date.now(); for (let i 0; i 1000000; i) { list.push(i); } console.log(自定义ArrayList耗时:, Date.now() - t1, ms); const arr []; let t2 Date.now(); for (let i 0; i 1000000; i) { arr.push(i); } console.log(原生Array耗时:, Date.now() - t2, ms);在我本机多次运行后的平均结果大约是实现100万次尾插耗时原生Array12ms左右自定义ArrayList28ms~35ms自定义版本慢一倍左右原因主要有三个一是push方法增加了函数的调用栈二是每次插入都要做一次size capacity的判断三是new Array(capacity)的初始化本身有开销。但这些差距在刷题的数据规模下基本可以忽略因为算法题的数据量一般在10万以内耗时差异只有几毫秒。真正拉开差距的是在“中间插入”的场景。原生Array的splice和我们的insertAt都需要O(n)的搬移两个版本表现接近。所以自研ArrayList的主要价值不在性能超越原生而是在于让你搞清楚底层的代价到底发生在哪儿。4. 在刷题场景里什么情况下真的需要手写“ArrayList”4.1 典型场景一需要严格控制容量的模拟有时候刷题会遇到这样的场景给定一个上限为N的动态列表你需要不断往里添加数据但是又明确知道最大不会超过某个值。如果直接用原生Array的push底层可能扩容很多次每次扩容都有一次新建数组和拷贝的过程。虽然均摊代价低但如果你恰好被卡在时间边界上这些小开销也可能成为压垮性能的最后一根稻草。用自实现的ArrayList你可以直接指定初始容量const records new ArrayList(N);这样一来如果添加的总数不超过N就一次扩容都不会发生。我在做模拟题的时候经常用这个技巧效果非常直接。而且因为容量上限是已知的扩容逻辑完全不会触发。4.2 典型场景二需要一个“稀疏但有序”的结构还有其他一些场景比如你需要一个只按下标访问、但中间会有“空洞”的容器。原生Array的稀疏数组行为在引擎里是一个不透明决策性能可能骤降而自实现的ArrayList可以很明确地采用“用undefined占位、维护size”的策略让行为完全可控。比如模拟哈希表的开放寻址法时你希望数组的下标直接映射到槽位这时用固定容量的ArrayList就非常顺手。当然这种场景不常见但它能帮你建立一种确定性思维数据结构的行为和性能应当是可预测的而不是把命运交给引擎内部的优化策略。4.3 三种替代方案对比原生Array、自写ArrayList、TypedArray在刷题中到底用什么存储结构我列一个对比表方便你直接决策方案适合场景限制与坑原生Array绝大多数算法题的默认选择内部优化不可控稀疏时性能退化自定义ArrayList需要预分配容量、需要确定性的扩容行为代码需要自己维护原生方法不可用TypedArray如Int32Array知道元素类型和最大数量上限长度固定无法push/pop需手动维护sizeTypedArray这个方案值得单独说两句。如果你确定要存的是整数而且最大数量已知那么用new Int32Array(100000)就比原生Array省一半以上的内存而且访问速度更快。缺点是没有push和pop需要自己维护一个length变量模拟压栈和弹栈。这正是很多底层算法库的做法。4.4 如果面试官问“为什么不用原生Array而自己实现ArrayList”怎么答这个问题我觉得比较好的回答思路是先承认原生Array在绝大多数场景下是更好的选择然后从两个角度补充价值。第一是原理层面自己实现ArrayList的过程能说明白动态数组的扩容策略、均摊复杂度和插入删除的代价模型第二是工程层面在需要预分配容量、行为确定性的场景下自研容器反而能提供更可控的性能表现。这样可以避免给人“为了手写而手写”的感觉。5. 实现中的常见问题和调试技巧5.1 越界访问JS不报错反而让你的bug更难找原生Array在访问越界索引时直接返回undefined不会抛异常。这在日常开发中很方便但在自己实现数据结构时会掩盖大量逻辑错误。比如const arr [1, 2, 3]; console.log(arr[5]); // undefined不报错如果ArrayList的get也这样设计那调用方很难发现自己为什么拿到了一个undefined而且这个undefined还可能一路传到下游逻辑中最后表现为一个非常难排查的异常。所以我在实现里把_checkIndex做成了显式抛错让“越界”在一开始就炸出来。提示刷题时如果想模拟这种严格检查可以在数组前面包一层自己的访问函数或者在调试期给Array.prototype加一个临时的getter打印。不过记住改完要还原不然会影响全局。5.2 引用类型与扩容拷贝的陷阱_resize里用的拷贝方式是for (let i 0; i this.size; i) { newItems[i] this.items[i]; }这是浅拷贝。如果数组中存的是对象新旧数组对应的元素会指向同一个对象。这本身没问题因为ArrayList的设计就是只拷贝引用。但有一个容易踩的坑是new Array(capacity)会创建包含空槽的数组而不是用undefined填满的数组。在未写入的位置读取会得到undefined但如果直接执行Array.from或者map空槽会被跳过行为跟常规数组不一致。所以在我自己的实现里所有空间预留都用的是new Array(capacity)配合显式下标写入避免调用会遍历空槽的map之类的方法。5.3 性能剖析的基本方法如果你真的想确认自己的ArrayList或者原生Array在哪一步产生了性能问题我推荐用Chrome DevTools的Performance面板而不是console.time。console.time只能测出总耗时但Performance面板可以精确地看到每一次函数调用的耗时分布、GC停顿以及内存变化曲线。方法很简单在代码入口处设置console.profile(test)退出时console.profileEnd(test)然后去Performance标签页看火焰图。我经常用这个方式来定位“到底是扩容拷贝慢还是GC回收旧数组慢”。实测经验当ArrayList扩容次数很多时火焰图里会看到明显的_resize长条如果GC频繁可以看到内存占用成锯齿状波动。这些都是直接用console.time看不到的。6. 后续可以继续扩展的方向与个人心得这篇文章写到这里ArrayList的主体实现已经完成了。如果后续要继续深挖我有两个很自然的扩展方向。第一个方向是给ArrayList加上迭代器接口让它支持for...of循环。实现思路是在类内部写一个[Symbol.iterator]方法用yield逐项返回值这样就能无缝嵌入到现有的循环语法里。第二个方向是增加容量收缩逻辑当size远小于capacity时把底层数组压缩到一半以避免内存浪费。加上这两个能力之后这个容器就更像一个真正可投入使用的“迷你原生结构”了。我在实际刷题过程中最大的体会是很多所谓的高难度题目拆到最底层都是数组和字符串的基本功堆叠。动态数组的扩容原理、字符串不可变性的代价、索引访问与搬移元素的开销这些概念没有打通之前看很多题解都会觉得“代码看懂了但为什么这么写”说不清楚。集中花一两个小时把ArrayList自己手写一遍再把字符串拼接的坑测试一遍远比多刷十道题更值。最后再分享一个小技巧如果你用JS刷题建议把常用的数组工具方法封装成自己的一套辅助函数比如带比较器的排序、去重、二分查找左边界这类。封装时不追求一次性写完完美版本而是每写一道题就把通用部分抽出来补进去这样你的解题工具箱会越来越顺手。