1. 引言顺序表Sequential List是一种最基本、最常用的线性数据结构它的核心思想是用一段物理地址连续的存储单元依次存储线性表的数据元素。在 Java 中顺序表的典型实现就是ArrayList它是对数组的封装与增强实现了变长存储、动态扩容等特性。本文将从基础概念入手深入ArrayList的源码实现涵盖核心操作方法、性能优化、高级话题以及常见面试陷阱带你完成从“会用”到“精通”的进阶。无论你是 Java 初学者还是准备面试的开发者都能在这篇教学里收获系统化的知识体系。2. 顺序表基础概念顺序表是线性表的顺序存储结构具有以下特点逻辑相邻物理也相邻所有数据元素在内存中连续存放支持通过下标进行随机访问。存储密度高只需存储数据本身不像链表需要额外的指针字段空间利用率更高。插入/删除效率较低在非尾部位置插入或删除元素时需要移动大量元素平均时间复杂度为 O(n)。顺序表的抽象操作包括初始化、增(add)、删(remove)、改(set)、查(get)、获取大小(size)等。在 Java 标准库中java.util.ArrayList正是基于动态数组实现的顺序表它允许存储任意类型的对象并且能够根据元素的增删自动调整内部数组的大小。3. Java中的顺序表ArrayListArrayList位于java.util包下实现了ListE、RandomAccess、Cloneable、Serializable等接口。它具备以下能力有序存储元素按插入顺序存放。可重复允许存储相同的元素。容量可动态增长无需手动指定大小内部数组会根据需要自动扩容。支持泛型可以指定元素类型避免类型转换和ClassCastException。基本使用示例如下import java.util.ArrayList; import java.util.List; public class ArrayListDemo { public static void main(String[] args) { // 创建一个空的顺序表默认容量为10 ListString list new ArrayList(); list.add(Java); list.add(顺序表); list.add(实战); System.out.println(list); // [Java, 顺序表, 实战] } }由于实现了RandomAccess接口ArrayList支持高效的随机访问这一点在遍历或查找时可以明显体现出来。4. ArrayList内部实现原理4.1 底层数组结构ArrayList的核心是一个Object[]类型的数组名为elementData。源码声明如下transient Object[] elementData; // non-private to simplify nested class access使用transient修饰是为了在序列化时通过自定义的writeObject来优化避免序列化未使用的数组空间。另外还有一个size字段表示当前列表中实际存储的元素个数它总是 ≤elementData.length。4.2 构造方法ArrayList提供了三个构造器无参构造器创建一个空列表并将elementData初始化为一个共享的空数组实例DEFAULTCAPACITY_EMPTY_ELEMENTDATA。第一次添加元素时才会扩容到默认容量 10。指定初始容量ArrayList(int initialCapacity)如果initialCapacity 0则直接创建指定大小的数组为 0 则使用空数组负数则抛出异常。通过集合构造ArrayList(Collection? extends E c)将传入集合转为数组并赋值给elementData同时保证数组的实际类型为Object[]。4.3 扩容机制扩容是顺序表实现变长存储的核心。当调用add(E e)时如果size elementData.length就会触发扩容。流程如下private void grow(int minCapacity) { int oldCapacity elementData.length; // 新容量 旧容量 旧容量 1即扩容为原来的 1.5 倍 int newCapacity oldCapacity (oldCapacity 1); if (newCapacity - minCapacity 0) { newCapacity minCapacity; } if (newCapacity - MAX_ARRAY_SIZE 0) { newCapacity hugeCapacity(minCapacity); } // 复制数组到新数组 elementData Arrays.copyOf(elementData, newCapacity); }需要注意的是扩容操作会涉及数组拷贝因此如果能够预估数据量最好在初始化时就指定一个合适的容量避免频繁扩容带来的性能开销。5. 核心操作方法详解本节深入分析ArrayList中最常用的增删改查操作并结合源码理解其时间复杂度和潜在陷阱。5.1 添加元素尾部追加add(E e)先确保容量足够ensureCapacityInternal然后将元素放入elementData[size]。时间复杂度均摊 O(1)仅在扩容时产生 O(n) 的拷贝。指定位置插入add(int index, E element)检查索引范围然后调用System.arraycopy将从 index 开始的元素整体后移一位再赋值。时间复杂度O(n)因为需要移动后续元素。5.2 获取元素get(int index)直接返回elementData[index]时间复杂度 O(1)。得益于有序存储和数组下标访问随机读取速度极快。5.3 修改元素set(int index, E element)先检查索引然后将新值放入数组并返回旧值。同样为 O(1)。5.4 删除元素按索引删除remove(int index)会使用System.arraycopy将 index 之后的所有元素向前移动一位然后置空最后一个元素方便 GC并size--。时间复杂度 O(n)。按对象删除remove(Object o)内部分为null和非null两种比较遍历找到第一个相等元素后按索引删除时间复杂度 O(n)。5.5 查找元素indexOf(Object o)和contains(Object o)都是通过正向顺序遍历数组来检查相等性时间复杂度 O(n)。5.6 遍历方式推荐三种遍历方式// 1. 普通 for 循环随机访问快 for (int i 0; i list.size(); i) { System.out.println(list.get(i)); } // 2. 增强 for 循环 for (String s : list) { System.out.println(s); } // 3. 迭代器 IteratorString it list.iterator(); while (it.hasNext()) { System.out.println(it.next()); }其中普通 for 循环最适合ArrayList因为它可以利用get(i)的 O(1) 随机访问增强 for 和迭代器底层也是基于Iterator模式但内部会检查modCount防止并发修改异常适合只读遍历。不要在增强 for 循环中直接调用list.remove()否则会抛出ConcurrentModificationException。6. 性能分析与最佳实践6.1 时间复杂度总结操作平均时间复杂度add(E e)O(1)均摊add(int index, E e)O(n)get(int index)O(1)set(int index, E e)O(1)remove(int index)O(n)remove(Object o)O(n)indexOf / containsO(n)iterator.remove()O(n)6.2 扩容性能影响频繁扩容会导致大量的数组拷贝尤其是在向空列表逐个添加大量元素时。建议通过new ArrayList(expectedSize)指定初始容量可以有效减少扩容次数。例如int expectedSize 10000; ListString list new ArrayList(expectedSize);6.3 线程安全问题ArrayList不是线程安全的。多线程并发修改同一个ArrayList时可能发生数据错乱、数组下标越界甚至抛出ConcurrentModificationException。如果需要在并发环境下使用有三种常见方案使用Collections.synchronizedList(new ArrayList())包装一个同步列表。使用CopyOnWriteArrayList适用于读多写少的场景。使用显式锁如ReentrantLock或synchronized块手动控制并发。6.4 最佳实践建议预估容量已知元素数量时务必指定初始容量。尾部添加为主尽量在末尾追加元素减少移动开销。删除时从后往前如果需要在遍历中删除建议从后向前遍历避免索引错乱。使用迭代器删除在避免索引混乱的场景下使用iterator.remove()代替list.remove(index)。减少扩容预留可以使用list.ensureCapacity(int minCapacity)在批量添加前一次性扩容。7. ArrayList与LinkedList对比ArrayList和LinkedList都是List接口的实现但底层实现完全不同适用场景也有显著差异。特性ArrayListLinkedList底层结构动态数组双向链表随机访问(get)O(1)O(n)头部插入/删除O(n)需要移动元素O(1)尾部插入/删除均摊 O(1)O(1)维护尾指针中间插入/删除O(n)移动元素O(n)定位节点内存占用连续空间空间浪费在预留的容量上需要额外存储前后节点指针缓存友好性高数组连续CPU缓存命中率高低节点随机分布在堆中一般情况下如果业务以随机读取和尾部追加为主优先选择ArrayList如果需要频繁在头部或中部插入/删除可以考虑LinkedList但也要注意链表在遍历定位时仍然是 O(n)并非所有情况下插入删除都比数组快。8. 高级话题自定义泛型顺序表为了更好地理解顺序表的原理我们可以手动实现一个泛型动态数组模拟ArrayList的核心行为。import java.util.Arrays; public class MyArrayListE { private static final int DEFAULT_CAPACITY 10; private Object[] elementData; private int size; public MyArrayList() { elementData new Object[DEFAULT_CAPACITY]; } public MyArrayList(int initialCapacity) { if (initialCapacity 0) { elementData new Object[initialCapacity]; } else if (initialCapacity 0) { elementData new Object[]{}; } else { throw new IllegalArgumentException(Illegal Capacity: initialCapacity); } } public int size() { return size; } public boolean isEmpty() { return size 0; } private void ensureCapacity(int minCapacity) { if (minCapacity elementData.length) { int newCapacity elementData.length (elementData.length 1); if (newCapacity minCapacity) { newCapacity minCapacity; } elementData Arrays.copyOf(elementData, newCapacity); } } public boolean add(E e) { ensureCapacity(size 1); elementData[size] e; return true; } public void add(int index, E e) { if (index 0 || index size) { throw new IndexOutOfBoundsException(Index: index , Size: size); } ensureCapacity(size 1); System.arraycopy(elementData, index, elementData, index 1, size - index); elementData[index] e; size; } SuppressWarnings(unchecked) public E get(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(); } return (E) elementData[index]; } SuppressWarnings(unchecked) public E set(int index, E e) { E oldValue (E) elementData[index]; elementData[index] e; return oldValue; } public E remove(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(); } SuppressWarnings(unchecked) E oldValue (E) elementData[index]; int numMoved size - index - 1; if (numMoved 0) { System.arraycopy(elementData, index 1, elementData, index, numMoved); } elementData[--size] null; // clear to let GC do its work return oldValue; } Override public String toString() { StringBuilder sb new StringBuilder([); for (int i 0; i size; i) { sb.append(elementData[i]); if (i size - 1) sb.append(, ); } sb.append(]); return sb.toString(); } }通过这个精简版实现你可以更直观地理解ArrayList的容量管理、数组拷贝和泛型擦除原理。源码中的很多细节如modCount、fast-fail 迭代器、子列表视图等都可以在此基础上进一步展开。9. 常见面试题与陷阱9.1 为什么说 ArrayList 是线程不安全的举例说明。当多个线程同时对同一个ArrayList进行增删操作时elementData和size的变化可能交叉导致数据覆盖、null元素出现甚至数组下标越界。例如一个线程正在执行add扩容另一个线程正在读取可能读到旧数组的部分数据。9.2 Array 和 ArrayList 的区别数组是固定长度的ArrayList可以动态扩容。数组可以存储基本数据类型ArrayList只能存储对象但可以借助封装类。数组没有提供丰富的 APIArrayList提供了大量便捷方法。9.3 ArrayList 的扩容为何是 1.5 倍这是一种经验值1.5 倍既避免了频繁扩容又不会造成过多的空间浪费。如果倍率太大如2倍可能造成大量内存闲置如果倍率太小扩容次数会显著增加。9.4 如何在遍历中安全删除元素必须使用iterator.remove()或在普通 for 循环中从后向前删除。绝对不能使用for-each直接调用list.remove()它会触发ConcurrentModificationException。9.5 subList 的陷阱list.subList(fromIndex, toIndex)返回的是视图对子列表的修改会反映到原列表反之亦然。另外对原列表进行结构性修改后子列表将会失效并抛出异常。10. 总结与学习资源本文系统梳理了 Java 顺序表的核心知识从基础概念、ArrayList源码实现到性能优化和面试高频考点构建了一条完整的进阶路径。掌握这些内容后你将能够在日常开发中合理选用和优化顺序表也能从容应对相关面试问题。推荐继续深入学习阅读 JDK 源码中的ArrayList、AbstractList和List接口注释。理解modCount与ConcurrentModificationException的实现机制。研究CopyOnWriteArrayList在并发场景下的写入时复制策略。动手实现一个支持迭代器的动态泛型数组并添加单元测试。顺序表是数据结构和 Java 集合框架的基石掌握它你就离“精通 Java”更近了一步。