很多学 Java 的人第一次接触数据结构都是从数组开始的。数组用起来确实简单声明一个类型、指定一个长度剩下的事就交给 JVM。可一旦面对动态增长中间插一条数据删除某条记录后还要保持连续这类需求数组就有点使不上劲了。这时候就该顺序表登场了。说白了顺序表就是基于数组的一种数据结构它把元素依次存在一块连续的内存空间里核心能力是自动扩容、按索引访问、有序存储。Java 里最常见的 ArrayList底层就是一个自动扩容的顺序表。可以说只要搞懂了顺序表你就同时对 Java 集合框架最基础的一块基石、考研数据结构的第一章、大厂 Java 面试里算法题的常用手感一并打了底。这篇文章适合三类人刚开始学 Java 数据结构的新手、期末要考数据结构的大学生、准备 Java/算法面试的开发者。我会从存储原理讲起带你手工实现一个能用的顺序表类把所有增删改查的细节、扩容策略、迭代器设计全部写一遍最后再聊聊我实际踩过的坑和面试中容易被追问的点。看完之后你自己就能写出 ArrayList 的核心逻辑也能回答为什么 ArrayList 查询快、插入慢这种经典问题。1. 顺序表从数组到动态容器的第一课1.1 顺序表到底是什么顺序表全称是顺序存储结构的线性表。线性表是数据结构里最基础的一类结构元素之间是一对一的线性关系排队排成一条直线。顺序表就是线性表采用顺序存储方式的实现底层用一块连续的物理内存来存放这些元素。举个例子你在内存里申请了一块可以放 8 个整数的空间地址是连续的比如从 1000 到 1032一个 int 占 4 字节。如果有 5 个元素依次存进去那么第一个元素在 1000第二个在 1004第三个在 1008……每个元素的位置都可以通过起始地址 索引 × 单个元素大小直接算出来。这就是顺序表最本质的特征逻辑上相邻的元素物理上也相邻。有个容易混淆的概念是链表。链表虽然也是线性表但它的每个节点可以分布在内存任意位置靠指针/引用串起来。顺序表可以像数组一样 O(1) 时间通过下标找到元素链表想找第 n 个节点只能从头开始走O(n)。反过来顺序表在中间插入或删除元素需要搬运后面所有数据O(n)链表只需要改指针O(1)。这两种特性决定了它们各自的适用场景完全不同。1.2 为什么先学顺序表很多人问Java 里都有 ArrayList 了直接学它不就行了吗为什么还要自己写顺序表因为 ArrayList 只是个成品而顺序表是零件。你只有亲手把零件拆开、组装一遍才知道它为什么这样设计。比如扩容时为什么用 1.5 倍而不是固定加几个位置为什么删除元素后要把尾巴上的引用置为 null为什么迭代器要记一个 modCount这些细节在源码里都有但你没写过一遍看过也就忘了。另外顺序表几乎是所有进阶数据结构的基础。栈可以用顺序栈实现队列可以用顺序队列实现堆排序需要一个数组风格的容器快排和归并也离不开数组操作。408 考研里数据结构第一章十有八九考顺序表的插入、删除、查找的复杂度分析Java 面试题里ArrayList 和 LinkedList 的区别更是高频中的高频。把这些基础打牢后面学什么都能串起来。2. 动手设计顺序表骨架从零构建动态数组2.1 申请一块连续空间的底层逻辑Java 里创建数组new Object[10]本质上就是在堆内存里申请一块连续的空间JVM 会保证这块空间的地址是连续的。我们自己实现顺序表核心思路就是维护这样一个数组引用同时记录当前存了多少个有效元素。设计上有两个要点第一存储的数组应该用什么类型。直接用Object[]最简单但取出来需要强转用起来很啰嗦。更好的做法是用泛型定义一个MyArrayListE内部维护E[] data。但 Java 泛型有个众所周知的坑不能直接new E[10]因为泛型在运行时会被擦除。标准解法是(E[]) new Object[10]虽然有 unchecked 警告但在自己实现的容器类里完全可接受。第二容量和大小要分开。data.length是容器能容纳的物理容量size是已经存放的逻辑元素个数。初学者最容易犯的错就是把size和data.length混在一起一看到数组长度就用data.length结果遍历时候把 null 元素也当成有效数据。类的基本骨架长这样public class MyArrayListE { private static final int DEFAULT_CAPACITY 10; private E[] data; private int size; public MyArrayList() { this(DEFAULT_CAPACITY); } SuppressWarnings(unchecked) public MyArrayList(int capacity) { if (capacity 0) { throw new IllegalArgumentException(容量不能为负数: capacity); } data (E[]) new Object[capacity]; size 0; } }2.2 扩容策略到底扩多少倍才合理数组的物理空间是固定的元素放满时唯一的办法就是重新开一块更大的空间把旧数据搬过去然后扔掉旧数组。扩容倍数这个设计很有意思。先说结论实际工程里常见的有两种ArrayList 是 1.5 倍HashMap 的 resize 是 2 倍。为什么不是固定加 10 个位置呢假设初始容量 10每次固定新增 10 个位置那么插入第 1 到第 10 个元素不需要扩容第 11 到 20 个需要搬一次第 21 到 30 需要搬一次……总共搬了大概n² / 20次元素。要是每次翻倍1、2、4、8、16 这样扩总共只需搬2n次左右。当 n 很大时翻倍策略的平均单次插入成本几乎是常数级这就是均摊复杂度 O(1) 的由来。为什么用 1.5 倍而不是 2 倍如果倍数太大比如 2 倍扩容一次申请的内存浪费比较多明明只放了 11 个元素却占了 20 个位置如果倍数太小比如 1.2虽然空间省了但扩容次数频繁搬数据累加起来反而慢。1.5 是个比较熟练的折中。你问我怎么记住的不需要记newCapacity oldCapacity (oldCapacity 1)右移一位就是除以 2原值加一半就是 1.5 倍。写扩容逻辑时最省事的做法是调用Arrays.copyOfprivate void ensureCapacity(int minCapacity) { if (minCapacity data.length) { return; } int oldCapacity data.length; int newCapacity oldCapacity (oldCapacity 1); if (newCapacity minCapacity) { newCapacity minCapacity; } data Arrays.copyOf(data, newCapacity); }2.3 一个能用的基础骨架有了上面这些我们可以把最小可用的顺序表结构完整写出来。这里我在实现时保留了容量不足时扩容size 与长度分离越界校验三个基本要素后面的增删改查方法都基于这套骨架import java.util.Arrays; public class MyArrayListE { private static final int DEFAULT_CAPACITY 10; private E[] data; private int size; public MyArrayList() { this(DEFAULT_CAPACITY); } SuppressWarnings(unchecked) public MyArrayList(int capacity) { if (capacity 0) { throw new IllegalArgumentException(容量不能为负数: capacity); } data (E[]) new Object[capacity]; size 0; } public int size() { return size; } public boolean isEmpty() { return size 0; } private void ensureCapacity(int minCapacity) { if (minCapacity data.length) { return; } int oldCapacity data.length; int newCapacity oldCapacity (oldCapacity 1); if (newCapacity minCapacity) { newCapacity minCapacity; } data Arrays.copyOf(data, newCapacity); } private void checkIndex(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(索引越界: index , size size); } } }这里我特意没有把所有方法都堆出来是因为骨架设计阶段最需要确认的是不变式size永远表示有效元素个数data.length永远大于等于size。后面的所有方法都必须维持这两个约束越界检查、扩容检查都从这两个约束推导。3. 增删改查写稳核心方法的关键细节3.1 尾插和指定位置插入顺序表最自然的插入是尾插直接把新元素放到data[size]然后size。如果当前容量不够先扩容再放。这个操作平均下来 O(1)因为扩容并没有每次都发生。指定位置插入就麻烦一点比如在 index2 的位置插入一个新元素原本下标 2 及之后的元素都要往后挪一位。注意循环遍历的方向必须从最后一个元素开始往前搬。如果你从前往后搬第一个元素先覆盖了第二个位置后续数据全乱套。public boolean add(E element) { ensureCapacity(size 1); data[size] element; return true; } public void add(int index, E element) { if (index 0 || index size) { throw new IndexOutOfBoundsException(插入索引越界: index , size size); } ensureCapacity(size 1); // 从后往前搬避免覆盖 System.arraycopy(data, index, data, index 1, size - index); data[index] element; size; }这里System.arraycopy是本地方法底层是内存块的直接拷贝比 for 循环一个一个赋值快得多。写代码时顺手就用它面试时这也是个可以提的加分点。3.2 删除元素时为什么要置 null删除指定位置的元素逻辑上就是把这个位置后面的元素整体往前挪一位然后 size--。但有一个细节很多人根本不 care被删掉的那个位置上还残留着一个没有任何引用的对象引用。比如data [A, B, C, D]删除 B 后数组变成data [A, C, D, D]size 3。最后一个下标 3 的位置仍然指向 D。如果这个 D 是个大对象本来是打算被垃圾回收的但此时因为数组还引用着它GC 就不会立刻回收。如果你不断往集合里加加删删不知不觉中一堆本该回收的对象还在被引用内存占用越来越高。解决办法很简单删除后把最后一个位置置为 nullpublic E remove(int index) { checkIndex(index); E oldValue data[index]; int moved size - index - 1; if (moved 0) { System.arraycopy(data, index 1, data, index, moved); } data[--size] null; // 方便 GC避免内存泄漏 return oldValue; }注意data[--size] null这一行既让 size 减少又清空了该位置。如果你删除的是最后一个元素moved 0不需要搬数据只执行置空一行就够了。这个细节在 ArrayList 源码里也存在JDK 开发者不会平白无故写一行无用代码。3.3 查询、修改和时间复杂度一览查询和修改没什么玄机就是数组按下标访问public E get(int index) { checkIndex(index); return data[index]; } public E set(int index, E newValue) { checkIndex(index); E oldValue data[index]; data[index] newValue; return oldValue; }到这里顺序表的核心复杂度可以总结成下面这张表操作时间复杂度说明按下标访问O(1)数组直接寻址无需遍历尾插均摊 O(1)不触发扩容时 O(1)扩容偶尔 O(n)指定位置插入O(n)需要搬运后续元素删除O(n)需要搬运后续元素按下标修改O(1)数组直接写入按值查找O(n)只能逐个比较看到这张表你就该明白为什么面试常问ArrayList 适合什么场景它是读多写少场景的王者。你频繁按索引查询、改某个位置的值它非常快但在头部频繁插入删除或者大量在中间插入那就不如 LinkedList其实 LinkedList 更适合头尾操作中间插入也得 O(n) 找位置。不过我个人的经验是项目里 90% 的集合需求用 ArrayList 都够了链表的缓存命中率还低真实跑起来不见得占便宜。4. 遍历与迭代器站位逻辑决定代码质量4.1 三种遍历方式的对比顺序表遍历有三种常见姿势普通 for 循环、增强 for 循环、迭代器。它们背后的逻辑不太一样。普通 for 最直白for (int i 0; i size; i)访问 data[i]。增强 for 本质上会偷偷调用迭代器而迭代器会检查并发修改标记 modCount。也就是说你用增强 for 或者迭代器遍历时如果在循环体内调用list.remove()这一类的结构性修改方法大概率会跑出一个ConcurrentModificationException。这不是 bug而是 Java 集合框架的一种安全设计防止你在遍历过程中结构突然变了导致数据错乱或者死循环。为什么 for 循环用(int i 0; i size; i)就不会报错因为它每次循环都重新读 size如果循环体里删除了一个元素size 变小了遍历次数就变少看起来没报错其实只是把数据悄悄跳过了。这个问题比异常更隐蔽。4.2 实现 Iterable 并理解 fail-fast 机制如果要让我们的顺序表也支持增强 for就得实现IterableE并提供一个迭代器。自己写迭代器时有个字段特别关键expectedModCount。对应的容器类要维护一个modCount每次做结构性修改插入、删除、扩容时自增一次。迭代器创建时把当时的modCount记下来之后每次调用next()都检查一次如果modCount ! expectedModCount说明容器在迭代过程被别人改了立刻抛出异常。这就是所谓的 fail-fast 机制快速失败。它不保证一定检测出所有并发修改只是尽可能早地暴露问题。迭代器内部站在哪个位置也是一个容易出错的设计点。常见做法是记录下一个要返回的下标 cursor初始为 0。hasNext()就是cursor ! sizenext()返回data[cursor]。remove()必须移除的是刚刚 next 返回的元素所以还得记一个lastRet表示上次返回的下标如果不存在就直接抛IllegalStateException。Override public java.util.IteratorE iterator() { return new Itr(); } private class Itr implements java.util.IteratorE { int cursor 0; int lastRet -1; int expectedModCount modCount; public boolean hasNext() { return cursor ! size; } SuppressWarnings(unchecked) public E next() { checkForComodification(); int i cursor; if (i size) { throw new java.util.NoSuchElementException(); } E element data[i]; cursor i 1; lastRet i; return element; } public void remove() { if (lastRet 0) { throw new IllegalStateException(); } checkForComodification(); MyArrayList.this.remove(lastRet); cursor lastRet; // 删除后下一个要访问的位置就是被删位置本身 lastRet -1; expectedModCount modCount; } private void checkForComodification() { if (modCount ! expectedModCount) { throw new java.util.ConcurrentModificationException(); } } }注意MyArrayList.remove()方法内部每次都要modCount。加在哪里呢所有改变元素个数或者移动元素的方法里包括 add、add(index)、remove。get 和 set 不算结构性修改只改值不改结构不需要动 modCount。我写过一版代码把 set 也 modCount 了结果用增强 for 只读不写也报异常找了好久才反应过来。4.3 如果就是要边遍历边删该怎么做实际业务里经常需要遍历列表并删除满足条件的元素。这时候如果你在增强 for / 迭代器里直接调用list.remove(index)会触发并发修改异常。正确姿势是方案一用迭代器的iterator.remove()上面代码已经支持了。方案二先收集要删除的元素遍历结束后再统一 removeAll。方案三倒着用普通 for 循环删for (int i size - 1; i 0; i--)因为删除的是后面的元素不会影响前面还没遍历到的下标天然安全。我个人最推荐方案一因为 Java 8 也可以直接写list.removeIf(Predicate)底层容器自己优化。不过既然是手写轮到表掌握迭代器 remove 的原理才是正经。5. 进阶优化与避坑实录5.1 扩容时数据拷贝的正确姿势扩容这个方法我前面写过简化版实际实现时有一个容易犯错的地方Arrays.copyOf(data, newCapacity)的返回类型是Object[]需要用泛型强转。如果写data (E[]) new Object[newCapacity];然后手动循环拷贝旧数据性能会打折扣但也不能说错只是代码更啰嗦。更隐蔽的坑是你如果调用System.arraycopy(data, 0, newData, 0, size)拷贝的元素个数应该用 size而不是 data.length。size 是有效元素data.length 是物理容量两者在已经扩容过的情况下往往不相等。拷贝了全长度也没问题因为空位置本来就是 null但白拷贝一些 null 没意义。另外扩容时机要避免用完再扩。如果 add 里先判断size data.length再扩容看起来没问题但存在一个边界size 1可能溢出吗正常业务不会但严谨一点ensureCapacity(size 1)里的size 1如果 size 已经是Integer.MAX_VALUE会溢出成负数后面的判断就全乱套。JDK 源码里其实有一个hugeCapacity的兜底逻辑我们自己实现不用较真但知道这回事面试聊起来可以装一下。5.2 要不要支持缩容ArrayList 默认不主动缩容数组减容并没有默认机制。那我们自己实现要不要做我的看法是不要自动缩容但可以提供手动trimToSize()。为什么因为顺序表的使用场景大多不确定今天删掉一半明天可能又插入很多如果每删一次就缩一次容等于反复搬运数组性能白损失。工程上常见的做法是如果内存敏感在长期不再写入之前手动调用一次trimToSize把容量降到和 size 一样大释放多余空间。SuppressWarnings(unchecked) public void trimToSize() { if (size data.length) { data Arrays.copyOf(data, size); } }这里有个小细节size 为 0 的时候Arrays.copyOf(data, 0)会得到一个长度 0 的数组下次 add 时就会扩容到 10。听起来合理但如果你持有这个顺序表很久期间反复 add/clear每次清空都缩到 0再次写入又要扩容效率反而差。所以要么不缩要么缩到最小容量 MINIMUM_CAPACITY比如 10。5.3 顺序表线程安全吗顺序表默认不解决线程安全。你的contains是无锁读但多个线程同时 add 和 remove数据就会乱。我亲历过一个 bug一个全局订单缓存用的 ArrayList多线程往里 add结果 size 比实际添加的少。原因很简单两个线程同时执行data[size] element一个读到同样的 size后写覆盖了先写。这不是 ArrayList 的问题是 shared mutable state 的问题。解决思路无非是几个用Collections.synchronizedList包装方法级锁简单但粗粒度。用CopyOnWriteArrayList读多写少的场景性能极好写时复制数组。自己加锁或者用并发容器按业务场景选。手写顺序表时务必要意识到它只适合单线程访问多线程场景不要直接裸奔。这一点面试时经常被追问你的 ArrayList 在多线程下会怎么样答案就是可能丢数据、size 不一致、还会因为 modCount 问题触发迭代异常。6. 从会写到会考顺序表相关的高频问题与练习建议6.1 面试最爱追问的扩展点面试官看你会写顺序表不会只停留在实现增删改查他会顺着往下问一串问题第一问扩容的均摊复杂度是怎么算的答从 1 扩到 22 扩到 44 扩到 8每次都复制之前所有元素。n 次插入总共复制的次数大约是1 2 4 ... n ≈ 2n均摊到 n 次插入就是 O(1)。注意均摊和平均不一样均摊是看整个操作序列的总耗时平均到每个操作。第二问为什么 ArrayList 比 LinkedList 更省内存因为顺序表只需要一个数组引用元素紧凑排列而链表每个节点还要额外存储前后指针Java 里对象还有对象头链表的额外开销通常很可观。而且数组是连续内存遍历时 CPU 缓存命中率高链表节点乱跳缓存不友好实际性能差距比理论复杂度更大。第三问自定义顺序表时泛型数组怎么处理答(E[]) new Object[capacity]并解释泛型擦除。这段我上面代码已经演示了。第四问迭代器为什么抛 ConcurrentModificationException答modCount 机制fail-fast 设计。顺带可以把我们手写的迭代器代码讲出来比背概念强得多。6.2 刷题从哪里入手顺序表最大的练手价值有两个方向。第一个方向用手写顺序表去实现简单功能比如求解一般集合的并集问题——这是很多学校数据结构实验课给的任务。两个集合求并集最简单粗暴的做法就是把 A 全部放进结果顺序表然后遍历 B如果 B 里的元素不在结果里就 add。这里可以顺便练习按值查找的 equals 判断。写的过程中你会意识到课堂上讲的集合如果用顺序表存去重判断是 O(nm) 的所以才需要后面学的 HashSet哈希表。第二个方向做一些经典的数组题这些题本质上就是顺序表上的操作。比如合并两个有序数组、删除有序数组中的重复项、把数组中的零移动到末尾、反转字符串等。这些都是 LeetCode 简单/中等题但做起来你会对数组中搬数据从后往前遍历双指针这些手感和概念有更深体会尤其是覆盖代替删除从后向前填充避免覆盖这类技巧用得很频繁。我一直觉得刷算法题之前把类似顺序表这种最基础的数据结构手写一遍收益远大于拿 PPT 背一百个概念。下课之后你自己敲一遍里面最关键的内置方法、边界逻辑、modCount 的来龙去脉才会在大脑里留痕。最后再分享一个我自己的实操习惯写数据结构代码时我从不一上来就堆功能。我会先把类骨架和不变式写出来然后只实现一个 add立刻跑到 IDE 里用断点看数组变化确认没问题再继续加 remove、迭代器。每加一个方法就检查一遍 size 是否永远等于有效元素个数。这比全部写完再 debug 高效得多你要是把扩容 插入 删除 迭代器一股脑写完再调试出了 bug 你根本分不清是扩容逻辑坏了还是 size 没更新。另外一个小技巧测试顺序表时不要只用默认构造非要传入一个很小的容量比如 3然后一口气 add 8 个元素强制多次扩容。这样扩容边界、数据拷贝是否正确一测就暴露。我见过很多人写代码时扩容逻辑看起来没问题一跑就丢元素就是因为 copy 时用了 data.length 而不是 size或者搬数据的方向写反了。这些小坑不亲手测一遍真的发现不了。顺序表这块学完其实你已经把 Java 集合框架最大的秘密拆开了一半。后面不管学 LinkedList、Stack、Queue还是学 HashMap 的扩容和扰动函数都会觉得亲切很多。数据结构没有那么多玄学核心就是找到合适的存储方式把时间复杂度和空间复杂度算明白然后老老实实把边界处理好。