企业官网建设流程全解析

很多学 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[]最简单，但取出来需要强转，用起来很啰嗦。更好的做法是用泛型，定义一个MyArrayList<E>，内部维护E[] data。但 Java 泛型有个众所周知的坑：不能直接new E[10]，因为泛型在运行时会被擦除。标准解法是(E[]) new Object[10]，虽然有 unchecked 警告，但在自己实现的容器类里完全可接受。

第二，容量和大小要分开。data.length是容器能容纳的物理容量，size是已经存放的逻辑元素个数。初学者最容易犯的错就是把size和data.length混在一起，一看到数组长度就用data.length，结果遍历时候把 null 元素也当成有效数据。

类的基本骨架长这样：

public class MyArrayList<E> { 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.copyOf：

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); }

2.3 一个能用的基础骨架

有了上面这些，我们可以把最小可用的顺序表结构完整写出来。这里我在实现时保留了"容量不足时扩容""size 与长度分离""越界校验"三个基本要素，后面的增删改查方法都基于这套骨架：

import java.util.Arrays; public class MyArrayList<E> { 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)，因为扩容并没有每次都发生。

指定位置插入就麻烦一点：比如在 index=2 的位置插入一个新元素，原本下标 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 就不会立刻回收。如果你不断往集合里加加删删，不知不觉中一堆本该回收的对象还在被引用，内存占用越来越高。

解决办法很简单，删除后把最后一个位置置为 null：

public 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; }

到这里，顺序表的核心复杂度可以总结成下面这张表：

看到这张表，你就该明白为什么面试常问"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，就得实现Iterable<E>，并提供一个迭代器。自己写迭代器时，有个字段特别关键：expectedModCount。对应的，容器类要维护一个modCount，每次做"结构性修改"（插入、删除、扩容）时自增一次。迭代器创建时把当时的modCount记下来，之后每次调用next()都检查一次：如果modCount != expectedModCount，说明容器在迭代过程被别人改了，立刻抛出异常。

这就是所谓的 fail-fast 机制，快速失败。它不保证一定检测出所有并发修改，只是尽可能早地暴露问题。

迭代器内部站在哪个位置，也是一个容易出错的设计点。常见做法是记录"下一个要返回的下标 cursor"，初始为 0。hasNext()就是cursor != size，next()返回data[cursor++]。remove()必须移除的是"刚刚 next 返回的元素"，所以还得记一个lastRet表示上次返回的下标，如果不存在就直接抛IllegalStateException。

@Override public java.util.Iterator<E> iterator() { return new Itr(); } private class Itr implements java.util.Iterator<E> { 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 扩到 2，2 扩到 4，4 扩到 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 的扩容和扰动函数，都会觉得亲切很多。数据结构没有那么多玄学，核心就是找到合适的存储方式，把时间复杂度和空间复杂度算明白，然后老老实实把边界处理好。