Java集合List源码深度剖析：ArrayList、LinkedList与Vector选型指南

作为Java从业者，集合框架是每天都要打交道的基础设施，而List接口的三个经典实现——ArrayList、LinkedList、Vector，看似简单，但真要说出它们的底层差异、扩容机制、迭代器行为，很多人却只能答个大概。这篇文章我直接深入到JDK源码层面，把这三个类的核心机制逐一拆开揉碎，读完你不仅能知道它们“是什么”，更能明白“为什么”，以及在实际项目中到底该怎么选。

1. 先看清整体：三个类解决了什么问题

很多人用List就是new ArrayList<>()一把梭，偶尔在“头部插入频繁”的场景换LinkedList，但很少去想这三个类背后的设计哲学。说到底，它们都实现了List接口，都保证元素有序且可重复，但底层数据结构截然不同，这决定了它们在内存布局、时间复杂度和迭代行为上的巨大差异。

• ArrayList：基于动态数组（Object[]），支持随机访问，扩容时整倍增长。
• LinkedList：基于双向链表（Node prev/next），不连续存储，插入删除只动指针。
• Vector：ArrayList的线程安全版本，方法级别加锁，扩容策略略有不同。

1.1 数据结构决定一切

这三者的核心区别可以用一句话概括：数组 vs 链表 vs 加锁的数组。数组在内存中是连续空间，CPU缓存友好，但扩容需要搬运；链表每个节点分散在堆内存中，逻辑相邻但物理不一定相邻，遍历时会有缓存未命中；Vector则是把数组操作的每个方法都用synchronized包裹，任何单线程场景下都在为锁付出代价。

实际开发中，我见过不少典型案例：有人在循环里对LinkedList做get(i)操作，结果性能惨不忍睹，因为每次get都要从头或从尾遍历到第i个节点，时间复杂度是O(n)，整个循环就成了O(n²)。这就是对“数据结构决定复杂度”缺乏直观感受的典型后果。

1.2 源码版本说明

我这里剖析的源码基于JDK 8，这是目前生产环境最主流的版本基线。JDK 9+在底层实现上大体相似，但有些细微变化，比如ArrayList的private方法拆分、Vector的spliterator等，我会在相应位置标注说明。读源码这件事，版本一致性很重要，否则你会发现自己看到的源码和网上文章对不上号。

2. ArrayList源码深挖：动态数组的扩容与迭代器机制

2.1 核心字段：elementData与size

ArrayList有三个核心字段，源码注释得很清楚：

// 存储元素的数组缓冲区，ArrayList的容量就是该数组的长度 transient Object[] elementData; // 实际元素个数 private int size; // 默认容量为10 private static final int DEFAULT_CAPACITY = 10; // 空实例共享的空数组 private static final Object[] EMPTY_ELEMENTDATA = {}; // 默认空实例与EMPTY_ELEMENTDATA区分使用 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

注意transient关键字：elementData被标记为transient，意味着默认序列化不会直接序列化整个数组，而是通过自定义的writeObject方法仅序列化实际元素。这个细节很多人没注意到，但它是ArrayList序列化高效性的关键——如果直接序列化elementData，那数组中的null空洞也会被写入，浪费存储空间。

2.2 扩容机制源码逐行解读

扩容是ArrayList最核心的行为，也是面试必考题。看下面这段JDK 8源码：

private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) { int oldCapacity = elementData.length; 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); }

关键点在于oldCapacity + (oldCapacity >> 1)，即扩容为原来的1.5倍。这里用右移一位代替除以2，效率更高。为什么要1.5倍而不是2倍？这是时间与空间的折中：

• 扩容倍数越大，扩容次数越少，但浪费的闲置容量越多。
• 1.5倍是经验值，既控制了拷贝频率，又不至于过度浪费内存。

modCount++是另一个值得关注的点。它是AbstractList定义的结构性修改计数器，每次改变列表大小（add、remove等）都会自增。当迭代器创建时会记录这个值，迭代过程中如果发现modCount被修改，立刻抛出ConcurrentModificationException。这就是fail-fast机制——宁可快速失败，也不在错误的状态下继续运行。

2.3 add与remove的真实开销

add(E e)方法本身很简单：

public boolean add(E e) { ensureCapacityInternal(size + 1); elementData[size++] = e; return true; }

但add(int index, E element)就不同了：

public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // 关键：从index开始的所有元素右移一位 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }

System.arraycopy是native方法，底层是内存拷贝，效率极高。但即便如此，在中间位置插入的代价依然是O(n)——你插入一个元素，后面所有元素都得挪位置。而且这里有个隐患：arraycopy是浅拷贝，对引用类型只是复制引用，但对基本类型数组（比如ArrayList<Integer>）由于Integer是不可变的，倒没什么影响；可如果你的List存的是可变对象，插入时只是引用移动，对象本身没变，这一点在逻辑上反而是好事。

remove方法的开销类似：

public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // 显式置null，帮助GC回收 return oldValue; }

最后一行elementData[--size] = null很关键。如果不置null，数组中这个位置仍然引用着被删除的对象，即使size已经减小，这个对象也不会被垃圾回收，等于内存泄漏。JDK源码里这种细节体现了严谨性，也是我们在自定义集合时应当效仿的。

2.4 迭代器与fast-fail机制

ArrayList的迭代器是Itr内部类，它持有三个关键字段：

private class Itr implements Iterator<E> { int cursor; // 下一个元素的索引 int lastRet = -1; // 上次返回元素的索引，-1表示无 int expectedModCount = modCount; // 期望的modCount }

迭代器每次调用next()都会检查modCount：

final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); }

这意味着，如果在迭代过程中调用list.remove()或list.add()，就会改变modCount，导致迭代器检测到不一致并抛出异常。但迭代器自身的remove()方法是安全的，因为它会同步更新expectedModCount：

public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } }

实战中，如果你要在遍历时删除符合条件的元素，必须用迭代器的remove()，或者用Java 8的removeIf，而不是list.remove()。后者几乎必然触发ConcurrentModificationException。

注意：单线程环境下同样可能触发ConcurrentModificationException，并不是只有并发场景才会出现。只要在迭代期间通过非迭代器方式修改了结构性字段，就会触发fail-fast。

3. LinkedList源码深挖：双向链表的节点与指针操作

3.1 Node内部类与链表结构

LinkedList的底层是一个双向链表，每个节点是一个Node：

private static class Node<E> { E item; // 实际元素 Node<E> next; // 后继节点 Node<E> prev; // 前驱节点 Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }

LinkedList内部维护三个关键字段：

transient int size = 0; transient Node<E> first; // 头节点 transient Node<E> last; // 尾节点

注意，LinkedList的字段也是transient，序列化时通过writeObject遍历链表逐个写入节点数据，而不是序列化整个链表结构。

3.2 头部插入与尾部插入的对称性

LinkedList的插入操作非常优雅，它提供了private的linkFirst和linkLast方法：

private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; } void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }

两个方法的逻辑完全对称：创建新节点，维护first或last指针，如果原链表为空则同时更新另一个指针，否则更新相邻节点的prev或next。复杂度都是O(1)，不涉及任何元素移动。

在指定位置插入时，LinkedList会先通过node(int index)方法定位：

Node<E> node(int index) { // 如果索引小于size的一半，从头往后找；否则从尾往前找 if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }

这个二分为查找做了优化，时间复杂度从O(n)降到了O(n/2)的平均水平，但仍然是线性复杂度。因此“LinkedList插入是O(1)”这个说法需要限定条件：只有在头部或尾部插入才是O(1)，在中间插入仍然需要先O(n)定位到目标位置。

3.3 get方法与索引访问的代价

LinkedList的get(int index)方法：

public E get(int index) { checkElementIndex(index); return node(index).item; }

核心就是node(index)这个O(n/2)的遍历查找。所以如果你写这么一段代码：

for (int i = 0; i < linkedList.size(); i++) { Object obj = linkedList.get(i); }

总时间复杂度是O(n²/2)，n越大越慢。这几乎是LinkedList最常见的误用场景，我见过不止一次有人在这种写法下排查性能问题，最后把锅甩给了LinkedList。

3.4 内存布局与性能特征

LinkedList每个节点至少有三个字段：item（引用8字节）、next（引用8字节）、prev（引用8字节），再加上对象头，在64位JVM且开启压缩指针的情况下，单节点约24字节。存储1万个元素，光节点开销就是24万字节。对比ArrayList，elementData是连续数组，1万个引用大约8万字节（压缩指针下），内存效率高得多。

缓存友好性方面，ArrayList的连续内存被CPU缓存命中的概率极高，遍历时几乎全部命中；LinkedList的节点散落堆中，每次访问都有可能触发缓存未命中，需要从主内存加载。实际测试中，ArrayList遍历比LinkedList快一个数量级是很正常的。

4. Vector源码深挖：官方线程安全实现为何失宠

4.1 字段与构造器：默认容量10，扩容翻倍

Vector的底层其实和ArrayList几乎一样，也是Object[] elementData：

protected Object[] elementData; protected int elementCount; protected int capacityIncrement; // 容量增量，0表示扩容翻倍 public Vector() { this(10); // 默认容量10，和ArrayList的默认容量一致 } public Vector(int initialCapacity, int capacityIncrement) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); this.elementData = new Object[initialCapacity]; this.capacityIncrement = capacityIncrement; }

扩容逻辑：

private void grow(int minCapacity) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); }

如果capacityIncrement>0，每次扩容增加指定增量；否则扩容为原来的2倍。这和ArrayList的1.5倍不同，造成Vector在扩容时更浪费内存，但扩容次数更少。

4.2 方法级别的synchronized

Vector的每个公共方法都加了synchronized：

public synchronized boolean add(E e) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = e; return true; } public synchronized E get(int index) { if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index); return elementData(index); }

锁的粒度是方法级别，这意味着任何调用Vector方法的线程都必须获取同一个锁。单线程场景下，锁的获取和释放本身有开销（即便是无竞争的偏向锁，也有一定成本），所以Vector在单线程下通常比ArrayList慢。更尴尬的是，这种方法级别的同步并不能保证复合操作的原子性。比如：

if (!vector.contains(e)) { vector.add(e); }

contains和add是各自同步的，但复合操作“检查和添加”并不原子。两个线程可能同时通过contains检查，然后都执行add，导致重复元素。所以Vector的线程安全是一种“伪安全”——它只能保证单个方法不被打断，无法保证多个方法组合的业务逻辑安全。

4.3 Vector与ArrayList的关键差异汇总

Vector的另一个槽点是遗留方法，比如elements()返回Enumeration，这几乎是Java 1.0时代的化石API。在现代化开发中，完全可以用Collections.synchronizedList包装ArrayList，或者用CopyOnWriteArrayList替代。从实践角度看，Vector基本已经没有存在的必要，理解它的价值更多在于历史对照和面试准备。

5. 三大实现横向对垒：场景选型与性能结论

5.1 查询、插入、删除的时间复杂度对比

这里有个重要概念：ArrayList的尾部add是“摊还O(1)”。因为扩容时确实需要O(n)拷贝，但扩容次数大约log1.5(n)次，每次扩大量是递增的，所以平均到每个add操作上是常数量级。

5.2 实战选型建议

• 默认选择ArrayList。90%的场景，ArrayList就是最优解。随机访问快、遍历快、内存友好、代码可读性高。
• 仅在频繁头部插入且不要求随机访问时选LinkedList。比如实现FIFO队列或撤销栈时，LinkedList是天然选项。但要注意，ArrayDeque在很多场景比LinkedList更优，因为它用循环数组实现，内存友好且无节点开销。
• Vector不要用。线程安全用CopyOnWriteArrayList（读多写少）或Collections.synchronizedList（写多读少）。
• 复制代码中看到的LinkedList要审视。很多代码从旧版本继承而来，当初选型是否合理值得重新评估，尤其当只有尾部追加和遍历操作时，直接换成ArrayList通常能获得立竿见影的性能提升。

5.3 为什么说“选择工具决定性能下限”

数据结构的选择决定了算法的复杂度上界和下界。你用ArrayList还是LinkedList，不是微调，而是数量级的差异。举个例子，在一个拥有10万条记录的列表头部循环插入1万条记录：

• ArrayList：每次插入都整体右移，总代价约10万 × 1万 = 10亿次元素移动（实际由arraycopy加速，但仍是O(n²)级）。
• LinkedList：每次插入是O(1)的指针操作，总代价O(n)。

反过来，随机访问1万次：

• ArrayList：每次O(1)，总共O(n)。
• LinkedList：每次O(n/2)，总共O(n²)。

所以选型错了不是慢一点的问题，是能不能跑完的问题。

6. 源码之外的实战陷阱：modCount、subList与并发隐患

6.1 subList视图的隐藏炸弹

ArrayList.subList(int fromIndex, int toIndex)返回的是SubList内部类视图，它和原List共享同一个elementData引用。对这个视图的任何结构性修改，都会同步反映到原List，反之亦然。但更坑的是，如果你修改了原List的结构（比如add或remove），随后再操作SubList视图，会抛出ConcurrentModificationException：

List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c", "d")); List<String> sub = list.subList(1, 3); System.out.println(sub); // [b, c] list.add("e"); System.out.println(sub); // ConcurrentModificationException

因为SubList的parentModCount记录的是创建视图时的modCount，原list.add会改modCount，两者不一致就触发异常。实际项目中，如果对subList做了保留引用又修改了原List，排查这个问题需要相当敏锐。

经验：subList只适合“即时使用”，不要长期持有引用并在其他线程或代码段修改原List。另外，subList中调用remove如果“连坐”移除元素时，注意边界问题。

6.2 遍历中删除的正确姿势

三种遍历中安全删除的方式：

// 方式1：显式迭代器 Iterator<String> it = list.iterator(); while (it.hasNext()) { String item = it.next(); if (item.startsWith("x")) { it.remove(); } } // 方式2：lambda removeIf（JDK 8+） list.removeIf(item -> item.startsWith("x")); // 方式3：反向索引删除 for (int i = list.size() - 1; i >= 0; i--) { if (list.get(i).startsWith("x")) { list.remove(i); } }

其中方式2最优雅、性能也最好，因为removeIf内部用迭代器遍历并逐个调用remove，不会产生modCount冲突。方式3的原理是：从尾部删除，每次删除只影响当前位置之前的元素，已经遍历过的索引不受影响。

6.3 并发场景下ArrayList的三大诡异现象

ArrayList不是线程安全的，并发读写时可能出现：

1. 并发修改异常：迭代时其他线程修改list，抛出ConcurrentModificationException。
2. 脏读：一个线程读取元素时，另一个线程修改了同一位置，读到旧值或null。
3. 数据覆盖：两个线程同时add到相同索引，后写的元素覆盖先写的，size没有正确递增（因为size++不是原子操作），导致部分元素丢失。

另外还有一个极少关注但实际存在的“ArrayIndexOutOfBoundsException风险”：并发add导致扩容时两个线程同时触发grow，可能拿到不同容量的新数组，最终覆盖elementData，出现数组越界或元素丢失。

解决这类问题的标准方案：

• 读多写少：CopyOnWriteArrayList。
• 写多或复合操作用锁：Collections.synchronizedList + 手动同步复合操作。
• Java 8+可用并发集合替代。

6.4 初始容量与扩容次数

ArrayList扩容涉及数组拷贝，拷贝量是O(oldCapacity)。如果你能预估容量，务必在构造时指定：

new ArrayList<>(expectedSize)

这样可以显著减少扩容次数。假设插入100万个元素：

• 初始容量10：扩容次数约log1.5(100000) ≈ 28次，总拷贝量约为原始容量的3倍多点。
• 直接指定100万初始容量：一次拷贝都没有。

很多性能分析报告显示，指定初始容量在高吞吐场景下可以把ArrayList构建阶段耗时降低近一个数量级。

7. 实操总结：一份可以直接抄的List选型与使用清单

7.1 什么时候用哪个类

7.2 三个必须养成的习惯

1. 用接口类型声明变量：List<String> list = new ArrayList<>();而不是ArrayList<String> list = ...。这样换实现时只改一行。
2. 遍历时不要直接list.remove：始终用迭代器、removeIf或反向循环。
3. 大集合创建时指定初始容量：无论ArrayList还是HashMap，这个习惯能大幅减少扩容的隐藏开销。

7.3 我踩过的一个坑，分享给你

曾经在某项目里，我用LinkedList维护一个“最近浏览记录”，想着头部插入是O(1)，每次插入都addFirst，然后定期removeLast清理过期记录。功能没问题，但后期需要按索引随机展示部分记录，我直接用get(i)，数据量5万条，页面响应从50ms直接飙升到3秒。排查后才发现get(i)的O(n)遍历是罪魁祸首。最后的方案是改成ArrayDeque加数组快照，问题立解。

这个经历告诉我：数据结构选型不是一劳永逸的，随着业务需求变化，要随时回头审视当初的选择是否仍然合理。读源码的意义，正在于让你有足够的能力去审视和纠正这些选择。

8. 后续扩展建议：往深水区再走一步

这三个类的源码读透之后，建议按这个顺序继续深入：

• AbstractList和AbstractCollection：理解骨架方法，看看哪些方法是基于其他方法实现的模板模式。
• ListIterator：对比ListIterator和普通Iterator的差异，特别是previous()和set()方法。
• RandomAccess接口：这是一个标记接口，ArrayList实现了它而LinkedList没有。Collections.indexOf等工具方法会检查这个标记来选择二分查找或线性遍历策略。
• Spliterator（JDK 8+）：并行流遍历的底层支撑，理解它才能理解Stream的并行性能。

我个人在实际使用中最深的一点体会是：读集合源码不要只看“它怎么实现”，更要看“为什么这么设计”。ArrayList把底层数组设为transient、Vector设计capacityIncrement、LinkedList的node方法做二分定位，每一个看似不起眼的决策背后都有明确的设计意图和性能考量。把这些意图参透了，你在自己的项目里遇到类似问题，自然就能做出更合理的判断。