从JS数组到手写ArrayList：扩容机制与刷题字符串处理技巧

1. 为什么JS里有了Array，还要自己实现ArrayList

1.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清单：哪些好用，哪些有坑

先列一个我刷题实战中最常用到的数组方法，以及它们的关键边界条件：

这里最值得单独拎出来说的坑是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个时总共拷贝了1+2+3+...+(n-1) ≈ n²/2次，单次push的均摊代价是O(n)。也就是说，固定大小扩容，会让n次push的总成本退化成O(n²)。

如果用“每次容量翻倍”的策略，假设容量从1涨到2、4、8、16……，到容量为n时，总拷贝次数是1+2+4+...+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');

在我本机多次运行后的平均结果大约是：

自定义版本慢一倍左右，原因主要有三个：一是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

在刷题中，到底用什么存储结构，我列一个对比表，方便你直接决策：

TypedArray这个方案值得单独说两句。如果你确定要存的是整数，而且最大数量已知，那么用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刷题，建议把常用的数组工具方法封装成自己的一套辅助函数，比如带比较器的排序、去重、二分查找左边界这类。封装时不追求一次性写完完美版本，而是每写一道题就把通用部分抽出来补进去，这样你的解题工具箱会越来越顺手。