聊到 JavaScript 刷题数组、字符串和 ArrayList 的简单实现大概是很多前端开发者在算法入门阶段最先遇到的一组基础题目。早些时候我帮一个学弟梳理面试题发现一个很有意思的现象数组的 API 大家都会背字符串的方法也能列个七七八八但一旦被问到底层实现——比如“ArrayList 是怎么扩容的”“为什么字符串拼接那么慢”——不少人就卡住了。这其实暴露了一个问题刷题的时候只看到了语言给我们提供的便利没有去理解数据结构本身的工作原理。这篇内容就是围绕这三个核心对象展开的从刷题视角出发先讲清楚数组和字符串在 JavaScript 里的真实特性再手写一个简易的 ArrayList把动态数组的容量管理、扩容策略、边界处理这些平时藏在底层的东西翻到台面上来。不管你是刚开始刷题的新手还是想补数据结构的同学这篇文章都能让你重新认识这些“老朋友”。1. 刷题视角下的数组与字符串它们到底在考什么1.1 核心需求不只是语法而是数据结构思维很多人在刷题初期会陷入一种误区看到题目标签写着“数组”就以为只要会用forEach、map、filter就够了看到“字符串”就想着字符串方法多背几个总能套上。但刷题平台真正想考察的从来不是某个方法的拼写而是你对数据组织方式的理解。数组的连续内存、随机访问、动态扩容字符串的不可变性、字符索引、子串操作这背后隐藏的是一整套关于时间复杂度和空间复杂度的思考方式。我举一个最常见的例子unshift和shift。面试官指尖一动出一道“用数组实现一个队列”的题很多人的第一反应是push进队、shift出队逻辑完全正确。可如果追问一句“这个队列的出队操作时间复杂度是多少”能答出 O(n) 的人就少了一半。原因是 JavaScript 的数组是动态数组shift会让所有剩余元素向前移动一位数据量大时性能衰减得极快。这种从“能用”到“用得明白”的差距才是刷题真正需要补齐的。所以本文的第一个目的是把数组和字符串从“语法糖堆”中拉出来放到数据结构这个坐标系里重新审视。你会看到为什么数组适合随机访问、为什么在头部增删元素那么昂贵、为什么字符串拼接会引发性能灾难。对初学者来说这是一个建立底层认知的好机会对已经刷过一些题的同学来说这篇文章能帮你把零散的经验串成体系。1.2 JavaScript 的数组和 Java 的 ArrayList 到底有什么关系这里有必要先厘清一个概念JavaScript 的Array并不是传统意义上的“数组”。在很多经典教材里“数组”指的是一块连续内存、固定长度、元素类型一致的结构就像 C 语言里的int arr[10]。但 JavaScript 的Array本质上是一个动态数组它内部是连续存储的数值索引集合同时抛出了一大堆面向操作的方法比如push、pop、slice、splice。换句话讲JS 内置数组几乎就是一个“自带方法的 ArrayList”平时我们用起来没什么感觉是因为语言已经帮我们处理了扩容和迁移。真正把两者区分开的是它们在题目中扮演的角色。在 Java 刷题时很多人会刻意使用ArrayList来替代原生数组因为它的add、remove、get方法更友好且可以动态增长。而在 JavaScript 中我们直接拿Array当动态列表用需要add就push需要remove就splice几乎没有心理负担。但这带来一个问题因为太方便大家就忽略了动态数组底层发生了什么。ArrayList 的简单实现之所以值得手写一遍不是让你在项目里替换原生数组而是让你切身体会三个核心机制容量不足时如何申请新内存数据如何从旧容器迁移到新容器扩容因子growth factor如何影响整体性能理解了这三件事你再回来看 JS 的push和pop就能明白为什么push在均摊意义下是 O(1)而在某些边界条件下会有一次 O(n) 的扩容开销。这种认识在解决大数据量的题目时非常关键比如实现一个动态的哈希表底槽、手写 LRU 缓存、或者模拟一个大数组的分块存储。2. JavaScript 数组的常用操作与性能隐患2.1 常用方法分类与选用建议数组的 API 少说也有三十多个但在刷题场景里最常用的就那十几个。我习惯把它们按操作类型分成三组这样记忆和理解会更清晰。第一组是尾部操作push和pop。这两个方法只影响数组末尾都不会移动其他元素所以时间复杂度是 O(1)。大量题目依赖这两个方法比如括号匹配的栈模拟、深度优先搜索里的路径回溯、单调栈维护等等。第二组是头部操作unshift和shift。它们的时间复杂度是 O(n)因为插入或删除头部元素后后面的所有元素都要整体平移。很多人在刷“用数组模拟队列”的题目时会掉进这个坑频繁shift导致超时。替代方案是用两个栈模拟队列或者干脆维护一个头指针headIndex只在逻辑上“删除”头部元素这就把时间复杂度降到了 O(1)。第三组是中间操作和查询操作splice、slice、indexOf、includes、find、filter等。splice用于增删改任意位置本质上是先截取再拼接最坏情况 O(n)slice是浅拷贝一个范围不会改动原数组适合用来做不可变操作indexOf和includes是线性查找O(n)如果频繁使用并且数据量大就需要考虑换成哈希表结构。我把刷题时最高频的几组操作整理成了一张表方便对比操作方法时间复杂度是否改变原数组典型场景尾部添加pushO(1) 均摊是栈、队列模拟尾部删除popO(1)是栈、回溯头部添加unshiftO(n)是尽量避免头部删除shiftO(n)是队列的朴素模拟任意位置插入/删除spliceO(n)是需要中间操作时切片复制sliceO(n)否获取子数组查找元素indexOf / includesO(n)否线性搜索批量生成新数组map / filter / reduceO(n)否数据处理流水线这张表看起来简单但很多性能问题都出在“选错方法”上。比如你想把数组反转如果只是为了遍历可以直接从尾部循环而不是先reverse()再遍历。多一次 O(n) 操作在数据量大时就是成倍的耗时。2.2 “看似简单”的性能陷阱有些数组操作的性能问题藏得很深不仔细分析代码根本发现不了。我举两个刷题中很常见的例子。第一个是“删除数组中的重复项”。很多人会怎么写用一个for循环每遇到一个重复项就调用一次splice。代码很短逻辑全对但一旦数组长度上了万性能立刻裂开。因为每splice一次剩余元素就要整体搬移一次最坏情况下是 O(n^2)。正确的做法是用双指针或者filter保留不重复的元素一次性过滤把整体复杂度压回 O(n)。第二个是“循环队列”或“滑动窗口”类题目中的头部淘汰。典型写法是queue.shift()看着舒服结果一提交发现超时。原因还是那个 O(n) 平移。常见优化思路是使用双端队列但在 JavaScript 里没有原生双端队列一种做法是维护一个指针start不真正删除元素用指针标记窗口的起始位置另一种做法是使用数组模拟环形队列用head和tail两个索引配合取模运算。这两种方案都能让头部“删除”变成 O(1)。再补充一个容易被忽略的细节数组的length属性并不一定代表实际存储元素的数量在稀疏数组的情况下length可能大于实际元素个数。刷题时我们很少构造稀疏数组但如果你用new Array(n)来预分配空间会得到一个全是空洞的数组。遍历时如果不对空洞做处理map和forEach会直接跳过这些空位而for循环会得到undefined。这会导致结果和预期不一致。比较稳妥的做法是用Array.from({ length: n })或Array(n).fill(0)来初始化确保所有位置都有确定的值。3. 字符串不可变性与刷题中的常见误区3.1 不可变字符串改变你的操作方式JavaScript 里的字符串是不可变的。这句听起来像常识的话在实际刷题中会带来很实质的影响。不可变意味着你做的任何一个“修改”操作——比如拼接、替换、删除字符——实际上都不会改动原字符串而是生成一个全新的字符串对象。最典型的性能陷阱是循环拼接。看你有没有写过这样的代码let s ; for (let i 0; i 100000; i) { s a; }这段代码在数据量小的时候运行无感但在十万次甚至百万次循环里会变得非常慢。为什么因为每一次s a都不是“在尾部追加”而是“创建一个新字符串把旧内容全部复制过去再追加一个字符”。单次 O(n)循环下来就是 O(n^2)。这就像抄一本 100 页的书每加一页都要把全书重新抄一遍成本高得离谱。正确的做法是先用数组收集片段最后用join一次性拼接const parts []; for (let i 0; i 100000; i) { parts.push(a); } const s parts.join();join的内部实现会对所有片段做一次总长度计算然后只分配一次空间整体开销是 O(n)。刷题时遇到字符串逐字符构造的场景比如实现字符串压缩、模拟文本编辑、构建编码结果都应该默认使用“数组收集 join 输出”这个模式实测下来在长字符串场景里能快一个数量级。字符串和数组的双向转换也是高频操作。用split()把字符串拆成字符数组处理完再用join()拼回去是刷题里的标准套路。比如反转字符串里的单词、判断回文串、对字符串内部字符排序基本都是先转数组再操作。需要提醒的是split()会把代理对代理对指码点超出基本多语言平面的字符比如某些生僻字或 emoji 字符按两个码元拆开导致结果乱码。如果题目明确涉及这类字符需要改用Array.from(s)或[...s]它们能正确按 Unicode 码点拆分。3.2 字符串方法选择与边界处理字符串的方法不比数组少但刷题时真正高频的就是那十几个。我按用途分一下查看与搜索charAt、indexOf、lastIndexOf、includes、startsWith、endsWith。截取与切片slice、substring、substr。大小写转换toLowerCase、toUpperCase。正则相关match、replace、search、split。修剪与填充trim、padStart、padEnd、repeat。这里面最容易出错的是三个截取方法的区分。slice和substring在参数都是非负数时表现基本一致都是取start到end不含end之间的字符但substring会自动交换两个参数如果start大于end而slice支持负数索引表示从末尾倒数。substr的第二个参数是长度而不是结束位置这个语义差异在刷题时非常坑我建议能不用就不用统一用slice最省心。大小写相关的坑也不少。经典的回文串判断很多人会直接s.toLowerCase().replace(/[^a-z0-9]/g, )然后反转比较。这本身没问题但如果题目包含非英文字母的字符比如带重音的法语字符或 Unicode 字符toLowerCase()的行为会受当前语言环境的影响导致大小写折叠结果和我们预期不一致。稳妥做法是明确限定题目给出的字符集或者用toLocaleLowerCase(en-US)这类指定语言环境的方法。还有一种常被忽略的边界情况空字符串和单字符串。比如判断两个字符串是否互为排列很多人会先排序再比较但如果你没有处理空串某些使用哈希计数的方法会在统计时产生undefined值比较导致意外的结果。我通常在开头就写好if (s.length ! t.length) return false;这种基础守卫条件避免后面做无意义的计算。正则表达式在字符串题目里是双刃剑。replace配合正则确实能写出很简洁的代码但正则的回溯在长字符串上可能非常慢极端情况下会直接打崩判题时限。我见过不少同学在“字符串解码”“单词替换”这类题中尝试用正则通配结果不仅代码难调试性能也不理想。建议只把正则用在字符集清理和格式匹配上真正需要逻辑判断的解析工作老老实实写状态机或手写循环。4. 手写一个简易 ArrayList从零理解动态数组4.1 为什么刷题时值得手写一遍 ArrayList动态数组的简单实现看起来是一个“玩具级”练习但它包含的知识密度其实很高。手写一遍 ArrayList你至少要回答下面几个问题底层用什么存数据数组但 JavaScript 的数组本身已经是动态的那我还需要自建数组吗答案是为了模拟底层行为我们用普通对象或定长数组来模拟固定容量存储。容量满了怎么办申请一块更大的连续存储空间把旧数据逐个搬过去。扩容扩多少每次扩一倍还是扩 1.5 倍还是扩固定大小选择不同会带来不同的均摊复杂度。缩容吗如果大量删除元素容器是否主动释放空间如果不缩容内存浪费怎么控制。越界访问如何处理比如get(-1)或get(100)应该报错还是返回undefined。这些问题在语言内置的数组里都被隐藏了但它们在算法题里会以各种变形出现。比如哈希表链地址法的底层存储、邻接表的动态添加边、模拟稀疏矩阵的列索引这些场景都需要我们自己管理一个动态数组。提前把底层机制想清楚再去看这些数据结构就顺滑很多。另外在很多公司的算法面试里“手写一个支持动态扩容的数组/列表”是一道经典题目。它考察的正是你对内存管理、容量计算、均摊复杂度这些基础概念的掌握程度。所以无论从学习角度还是求职角度用 JavaScript 实现一个简易 ArrayList 都很有价值。4.2 完整实现代码与逐步拆解下面这版实现是我比较常用的一个基础版保留了动态数组最核心的行为去掉了过于工程化的细节方便读者对照理解。class SimpleArrayList { constructor(initialCapacity 8) { if (initialCapacity 0) { throw new Error(容量必须为正数); } this.capacity initialCapacity; this.data new Array(initialCapacity); this.size 0; } // 返回当前元素个数 length() { return this.size; } // 获取指定位置的元素 get(index) { this._checkIndex(index); return this.data[index]; } // 设置指定位置的元素 set(index, value) { this._checkIndex(index); this.data[index] value; } // 尾部追加 add(value) { if (this.size this.capacity) { this._resize(this.capacity * 2); } this.data[this.size] value; this.size; } // 指定位置插入 insert(index, value) { if (index 0 || index this.size) { throw new Error(索引越界); } if (this.size this.capacity) { this._resize(this.capacity * 2); } for (let i this.size; i index; i--) { this.data[i] this.data[i - 1]; } this.data[index] value; this.size; } // 删除指定位置的元素并返回它 removeAt(index) { this._checkIndex(index); const removed this.data[index]; for (let i index; i this.size - 1; i) { this.data[i] this.data[i 1]; } this.size--; // 可选缩容策略 if (this.size this.capacity / 4 this.capacity 8) { this._resize(Math.max(8, Math.floor(this.capacity / 2))); } return removed; } // 内部索引检查 _checkIndex(index) { if (index 0 || index this.size) { throw new Error(索引越界); } } // 内部扩容/缩容函数 _resize(newCapacity) { const newData new Array(newCapacity); for (let i 0; i this.size; i) { newData[i] this.data[i]; } this.data newData; this.capacity newCapacity; } // 转成普通数组方便调试 toArray() { return this.data.slice(0, this.size); } }下面逐段拆解几个核心点。构造函数部分我默认初始容量是 8。这个数字不是随便定的让初始容量太小会导致前期频繁扩容太大则浪费内存。8 对我们手写练习足够也符合很多语言标准库的默认选择。add方法里最先判断的是size capacity。这一步的意义是提前确认数组是否还有剩余空间。注意这里有个细节size表示已存储的元素个数capacity表示底层数组的物理容量。当两者相等时代表当前数组已经“装满”必须先扩容再写入。如果不判断直接data[size] value就会写入一个越界位置后续访问会得到undefined。_resize方法是整个实现的灵魂。newCapacity 传入时我们创建一个新的定长数组然后把旧数组里的size个元素逐个复制过去最后替换this.data并更新this.capacity。为什么需要逐个复制因为数组的连续存储特性决定了新数组和旧数组的内存地址并不相同必须通过搬移来保持数据连续性。这也是动态数组扩容时最主要的性能开销。再说扩容因子的选择。我的实现里是capacity * 2也就是每次扩容翻倍。把扩容因子设为 2 的好处是均摊时间复杂度为 O(1)。简单解释一下假设初始容量为 1依次添加 n 个元素扩容操作的总搬移次数大约为 1 2 4 ... n/2 n合计不到 2n是 O(n) 量级。所以平均到每次add上额外开销只有常数级。如果容量只增加固定值而不是翻倍比如每次多 8 个空位那么总搬移次数就是 1 2 3 ... n变成 O(n^2)单次add的均摊成本就不是常数了。这个差别在千万级数据量上非常明显。不过扩容因子翻倍也并非百利而无一害。翻倍意味着底层数组可能比实际存储量多出一倍的空白位置在内存敏感的场景下是浪费。有的标准实现会选择 1.5 倍扩容在“搬移次数”和“空间浪费”之间取得平衡。我们手写练习时不必纠结哪个更好二倍扩容更容易理解和推导就先用它。removeAt里的缩容策略是很多实现容易遗漏的部分。如果只扩容不缩容一个存过 10 万元素后来被清空的列表会一直占着 10 万容量的内存空间。我采用的策略是当size capacity / 4时触发缩容一次性缩到原来的一半。这个阈值既有延迟又有余量避免元素在边界反复增删时频繁触发扩容和缩容降低了性能抖动。注意缩容时也不能缩到小于初始容量 8这是防止列表被“缩没了”。4.3 几种边界情况的处理细节手写动态数组的过程中最让人头疼的不是主线逻辑而是各种边界情况。我在调试过程中总结出了几个高频翻车点。第一个是索引检查的时机和范围。_checkIndex只用于get、set、removeAt这类必须访问已有元素的操作允许的索引范围是0 index size。但insert不一样它允许在末尾追加所以合法范围是0 index size。很多人在实现insert时习惯性地写index this.size就抛异常结果发现无法在末尾插入逻辑就乱了。第二个是扩容判断的位置。insert里的扩容判断要和add一样在搬移元素之前执行。如果先搬移再扩容就会出现旧空间根本装不下新元素的情况导致搬移时越界写入。这个顺序一旦搞错bug 极难排查因为只在容量刚好满了的时候暴露出来。第三个是缩容导致的下界问题。我在缩容条件里加了this.capacity 8这个守卫避免容量越缩越小。如果不加你可能会遇到一个极端情况数组里只剩 1 个元素缩容还是触发结果底层容量被缩到 2、1最后插入新元素时又被迫立即扩容来回震荡。这个问题在读取密集型任务中尤其痛苦性能损耗被无限放大。第四个是调试时容易忽略的toArray实现。返回this.data.slice(0, this.size)而不是直接返回this.data是为了避免把底层空位也暴露出来。如果直接返回整个底层数组调用方可能误以为那些undefined是列表的一部分还会得到与length()不一致的错误印象。5. 实现过程中的踩坑记录与刷题建议5.1 真实场景中的常见问题速查表手写 ArrayList 也好刷数组字符串题目也好总会遇到一些让人头皮发麻的问题。我把踩过的坑整理成了一张速查表每个问题后面都附了最常见的原因以及对应的排查思路供你对照参考。现象常见原因排查与处理访问data[index]返回 undefined索引越界或数组存在空洞先检查索引是否在[0, size)内初始化时用fill或Array.from补全add写入后旧的最后一项被覆盖扩容判断写在了写入之后确保size capacity时先_resize再赋值insert在末尾插入时报错索引允许范围写成了index size将合法范围调整为index 0 index size删除元素后数组长度不减少removeAt只搬移数据没有size--在removeAt末尾补上this.size--内存占用居高不下只扩容不缩容增加缩容策略比如size capacity / 4时缩为一半缩容后反复触发扩容缩容下界没控制缩容后的容量不能小于初始容量如Math.max(8, ...)大量shfit操作导致判题超时头部删除是 O(n)改用双栈模拟队列或维护头指针代替真实 shift字符串循环拼接性能极差字符串不可变每次拼接复制全文先收集到数组最后一次性join()split()处理 emoji 或生僻字结果乱代理对被拆成两个码元改用Array.from(s)或展开运算符[...s]不指定语言环境的toLowerCase结果异常方法受语言环境影响的边界需要稳定结果时用toLocaleLowerCase(en-US)这张表里的内容大多不是某个题目的特定解而是一类问题的通用解法。刷题时如果反复掉进同一个坑我建议把对应的行抄在笔记本上下次遇到类似提示就直接翻这里的结论能节省大量排查时间。5.2 日常刷题中如何高效使用这三种结构基于我自己的刷题经验给出一套比较顺手的选型建议。先说数组。在 JavaScript 里数组是你在刷题时使用频率最高的容器。当题目描述里出现“索引”“顺序”“子数组”“滑动窗口”这类关键词时直接考虑数组。但注意优先使用push和pop减少shift和unshift的使用次数。如果题目要求频繁从头部取元素你要么换一种数据结构要么在思路上调整成“从尾部取 反转顺序”把 O(n) 的头部操作变成 O(1) 的尾部操作。其次是字符串。字符串相关的题目我的习惯是“能不动就不动动就转数组”。对于字符级操作比如翻转、排序、统计频次先用Array.from(s)把字符串转成字符数组操作完再join回来。对于子串匹配、字符统计这类需要快速访问的问题直接用charCodeAt(i)配合编码差值来计数效率比charAt更高也更容易配合数组索引使用。比如判断字母异位词时用s.charCodeAt(i) - 97作为频率数组的索引既简洁又高效。最后说手写 ArrayList 的定位。它不是一个需要你在每道题里都拿出来用的工具而是帮助你理解动态数组内部机制的“解剖课”。当你需要优化一个动态扩容的容器、或者分析某个 API 的时间复杂度时脑子里能自动浮现出我们刚才写过的_resize过程这比背任何结论都管用。有时候我会故意在本地用SimpleArrayList替换原生数组跑同一套测试用例看看两种实现的结果规模和耗时差异这种对比能让你对语言内置结构产生更直观的感知。在实际刷题过程中我自己还有一个习惯每做完一道数组题都会在题解里补一句“如果用别的数据结构实现复杂度会怎么变化”。这种多问一步的训练比盲目刷题对能力提升大得多。比如把滑动窗口的数组实现换成链表实现虽然逻辑可能差不多但你能借此理解连续存储与链式存储在缓存友好性上的区别这在真实项目里处理大数据时相当重要。我个人在实际操作中的体会是数组、字符串、ArrayList 这三者越早串起来学后面遇到复杂数据结构就越不慌。很多看起来高级的算法比如并查集、线段树、Trie 树底层其实都在用数组做存储只是加上了不同的索引规则和操作逻辑。把数组和动态数组吃透相当于给后续的数据结构学习打了一个极结实的地基。最后再分享一个小技巧写这些基础实现的代码不用追求一次成型拿几个典型题目反复跑边跑边观察哪里性能不对劲这个过程比最终代码本身更有价值。