企业官网建设流程全解析

一、引言：一道经久不衰的面试题

在 Java 后端开发面试中，有一道题几乎遍布各大公司的基础轮次：「ArrayList 和 LinkedList 有什么区别？实际开发中应该怎么选？」。很多候选人会脱口而出：“ArrayList 查询快，LinkedList 增删快，所以读多写少用 ArrayList，写多读少用 LinkedList。”这句话听起来似乎很有道理，但如果你真的把它当作工程选型的依据，很可能会在性能敏感的系统里踩坑。

这篇文章的目标，不是给你一个可以背下来的“标准答案”，而是带你从底层数据结构、JDK 源码、时间复杂度、内存布局、CPU 缓存、性能实测、常见误区等角度，把 ArrayList 和 LinkedList 彻底讲透。我们会用大量可运行的 Java 代码进行验证，并在最后给出可落地的选型决策清单。全文较长，建议先收藏，再按章节阅读。

在开始之前，先明确本文讨论的 JDK 版本。除非特别说明，源码分析主要以JDK 8和JDK 17的 OpenJDK 实现为参照，两个版本在 ArrayList 和 LinkedList 的核心实现上差异不大。文中的性能测试建议在 JDK 17 环境下复现，并注意关闭 JIT 预热偏差带来的影响。

二、先认识这两个集合：接口与继承体系

ArrayList 和 LinkedList 都是 Java 集合框架中List接口的实现类。我们先从它们的公共接口和继承关系入手，建立整体认知。

2.1 List 接口的契约

List接口定义了一组有序集合的契约：元素有下标，允许重复元素，允许插入null，并且元素的顺序就是插入顺序。无论底层是数组还是链表，使用者通过List接口调用add、get、remove等方法时，语义应当是一致的。

List<String> arrayList = new ArrayList<>(); List<String> linkedList = new LinkedList<>(); // 对调用方而言，两者的基本 API 是一致的 arrayList.add("Java"); linkedList.add("Java"); String a = arrayList.get(0); String b = linkedList.get(0);

正是因为接口一致，很多开发者在使用时并不关心底层实现，从而忽略了它们在性能特征上的巨大差异。理解这些差异，是写出高性能 Java 代码的前提。

2.2 继承体系对比

ArrayList 的继承关系如下：

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

LinkedList 的继承关系如下：

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable

这里有一个非常关键的差异：ArrayList 实现了RandomAccess接口，而 LinkedList 没有。这个接口本身没有任何方法，它是一个标记接口，用来告诉算法实现者“这个 List 支持快速随机访问”。JDK 中的很多工具类，比如Collections.binarySearch，会根据是否实现RandomAccess来选择不同的算法策略。理解了这一点，你也就能理解为什么遍历 LinkedList 时不建议使用基于下标的get(i)循环。

另一个值得注意的点是：LinkedList 实现了Deque接口，这意味着它不仅是一个 List，还是一个双端队列。你可以把它当作队列、栈来使用，这为它的适用场景增加了更多可能性。

三、底层数据结构：动态数组与双向链表

3.1 ArrayList：基于动态数组

ArrayList 的底层其实就是一个对象数组。这个数组在 JDK 源码中对应字段elementData：

transient Object[] elementData;

所谓“动态”，是指当数组容量不足以容纳新元素时，ArrayList 会自动创建一个更大的数组，把旧数组的元素复制过去，再用新数组替换旧数组。这个过程称为“扩容”。因为数组是连续的内存空间，所以通过下标计算地址后可以在 O(1) 时间内直接读取元素；但插入和删除时，往往需要移动后续元素，成本较高。

3.2 LinkedList：基于双向链表

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 内部维护了指向头节点和尾节点的引用first和last。插入和删除元素时，只需要修改前后节点的指针引用，不需要移动其他元素，因此在链表头部或尾部的插入删除非常高效。但是，链表节点在内存中通常不是连续分布的，想要访问第 i 个元素，必须从头或尾开始沿着指针逐个查找，随机访问成本为 O(n)。

四、ArrayList 源码级深度解析

这一节我们直接打开 JDK 源码，看 ArrayList 的字段、扩容机制和核心方法到底做了什么。只有理解了源码，才能避免停留在“背诵复杂度”的层面。

4.1 核心字段与构造器

ArrayList 的核心字段如下：

private static final int DEFAULT_CAPACITY = 10; private static final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; transient Object[] elementData; private int size;

其中DEFAULT_CAPACITY表示默认初始容量为 10，elementData是真正存放元素的数组，size表示当前实际元素个数。注意区分size和elementData.length：前者是已经存入的元素数量，后者是数组当前能够容纳的最大元素数量。

ArrayList 有三个构造器：

public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); } } public ArrayList(Collection<? extends E> c) { Object[] a = c.toArray(); if ((size = a.length) != 0) { if (c.getClass() == ArrayList.class) { elementData = a; } else { elementData = Arrays.copyOf(a, size, Object[].class); } } else { elementData = EMPTY_ELEMENTDATA; } }

无参构造器在 JDK 8 之后采用了“懒初始化”策略：一开始数组是空的，只有当第一次真正添加元素时才会被分配为默认容量 10。这样做可以节省大量只创建不使用的空集合带来的内存浪费。

4.2 add 方法与扩容机制

先看最简单的尾部追加方法：

public boolean add(E e) { modCount++; add(e, elementData, size); return true; } private void add(E e, Object[] elementData, int s) { if (s == elementData.length) elementData = grow(); elementData[s] = e; size = s + 1; }

每次添加前都会检查size是否已经等于数组长度。如果相等，说明数组已满，需要扩容。扩容的核心方法如下：

private Object[] grow() { return grow(size + 1); } private Object[] grow(int minCapacity) { int oldCapacity = elementData.length; if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { int newCapacity = ArraysSupport.newLength(oldCapacity, minCapacity - oldCapacity, oldCapacity >> 1); return elementData = Arrays.copyOf(elementData, newCapacity); } else { return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)]; } }

这里有两层信息。第一，如果当前数组是空数组，则新容量取DEFAULT_CAPACITY和minCapacity中较大者，所以无参构造的 ArrayList 第一次添加元素后容量至少是 10。第二，正常情况下，新容量是在旧容量的基础上增加约一半，也就是常说的1.5 倍扩容。更准确地说，ArraysSupport.newLength会优先取oldCapacity + oldCapacity >> 1，如果仍不足以容纳minCapacity，则直接取minCapacity。

扩容过程中，Arrays.copyOf底层调用的是System.arraycopy，这是一个 native 方法，通常会按整块内存进行拷贝，效率远高于逐元素循环复制。尽管如此，扩容依然是一项相对昂贵的操作，尤其是当元素数量很大时，会涉及大量内存分配和复制。

4.3 get 与 set：数组的看家本领

public E get(int index) { Objects.checkIndex(index, size); return elementData(index); } E elementData(int index) { return (E) elementData[index]; } public E set(int index, E element) { Objects.checkIndex(index, size); E oldValue = elementData(index); elementData[index] = element; return oldValue; }

get 和 set 的实现非常直接：先做下标越界检查，然后直接通过数组下标访问。由于数组元素在内存中连续存储，JVM 可以直接根据首地址、元素宽度和下标计算出目标元素的内存地址，时间复杂度为 O(1)，而且这个 O(1) 的常数非常小。这也是 ArrayList 在随机访问场景下碾压 LinkedList 的根本原因。

4.4 按位置 add 与 remove：元素搬家的代价

在指定位置插入元素的方法如下：

public void add(int index, E element) { rangeCheckForAdd(index); modCount++; final int s; Object[] elementData; if ((s = size) == (elementData = this.elementData).length) elementData = grow(); System.arraycopy(elementData, index, elementData, index + 1, s - index); elementData[index] = element; size = s + 1; }

可以看到，在中间位置插入元素时，需要把index及其之后的所有元素整体向后移动一位，这个移动操作的成本与需要移动的元素个数成正比。如果是在头部插入，几乎要移动整个数组，复杂度为 O(n)；如果是在尾部追加，则通常只需要 O(1)，偶尔触发扩容。

删除操作与之类似：

public E remove(int index) { Objects.checkIndex(index, size); final Object[] es = elementData; E oldValue = (E) es[index]; fastRemove(es, index); return oldValue; } private void fastRemove(Object[] es, int i) { modCount++; final int newSize; if ((newSize = size - 1) > i) System.arraycopy(es, i + 1, es, i, newSize - i); es[size = newSize] = null; es[size] = null; }

删除中间元素后，需要把后续所有元素向前移动一位，并把原来最后一个位置置为null，帮助 GC 回收不再被引用的对象。同样，删除尾部元素的成本接近 O(1)，删除头部元素成本为 O(n)。

这里有一个细节值得注意：remove(Object o)按值删除时，会先线性查找目标元素，再执行搬移，所以整体复杂度依然是 O(n)。

4.5 迭代器与 fail-fast 机制

ArrayList 的迭代器Itr内部维护了一个expectedModCount。在迭代过程中，如果集合被其他方式结构化修改，导致modCount与expectedModCount不一致，就会抛出ConcurrentModificationException。这就是 fail-fast 机制。

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

需要注意，fail-fast 只能作为“尽力而为”的错误检测手段，不能依赖它来保证并发安全。如果需要线程安全地遍历和修改同一集合，应该使用CopyOnWriteArrayList或者显式加锁。

4.6 为什么 elementData 用 transient 修饰

很多面试题会问：elementData既然是 ArrayList 真正保存数据的地方，为什么还要用transient修饰？原因在于，如果直接使用默认序列化，会把数组中所有空位也一并序列化，导致空间浪费。ArrayList 重写了writeObject和readObject，只序列化size个实际元素，而不是整个数组长度个元素。

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { int expectedModCount = modCount; s.defaultWriteObject(); s.writeInt(size); for (int i = 0; i < size; i++) { s.writeObject(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } }

这样设计既能保证序列化内容的正确性，又能控制序列化后的体积。

五、LinkedList 源码级深度解析

5.1 核心字段与节点结构

LinkedList 的核心字段非常少：

transient int size = 0; transient Node<E> first; transient Node<E> last;

它只维护了size、first和last三个字段。前者记录元素个数，后两者分别指向头节点和尾节点。每个节点持有元素值以及前后两个引用，因此整个结构是一个双向链表。

5.2 头部与尾部添加：链表的强项

LinkedList 在头尾添加元素的方法有多个变体，例如addFirst、addLast、offerFirst、offerLast，但核心实现都类似。以下以尾部添加为例：

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

整个过程只涉及创建新节点、修改原尾节点的next指针、更新last引用，不涉及任何元素搬移。因此，在头部或尾部进行插入删除，时间复杂度是 O(1)。

5.3 按位置定位：先判断从哪头找

LinkedList 没有下标访问能力，任何按位置操作都需要先找到目标节点。它的查找逻辑有一个重要优化：根据index距离头尾的远近，选择从头还是从尾开始遍历，从而把平均查找次数缩小到 n/2。

Node<E> node(int index) { 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)。当数据量达到十万、百万级时，这种遍历会付出极高的 CPU 和缓存代价。

5.4 按位置插入与删除：先找到节点，再动指针

在指定位置插入元素时，首先要调用node(index)找到目标位置的节点，然后再修改指针：

public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); }

linkBefore的实现如下：

void linkBefore(E e, Node<E> succ) { final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }

可以看到，真正的指针修改只花费 O(1)，但前提是必须通过node(index)先定位到目标位置，这一步是 O(n)。所以，“LinkedList 中间插入是 O(1)”这种说法是不准确的，完整过程其实是 O(n)。只有在已经拿到目标节点引用的情况下，修改指针才是 O(1)，而普通 API 并不会把节点引用暴露给调用者。

5.5 删除操作的两种形式

LinkedList 的remove(int index)同样是先定位再解链：

public E remove(int index) { checkElementIndex(index); return unlink(node(index)); }

而remove(Object o)需要从头开始逐个比较并找到第一个相等的元素：

public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }

5.6 LinkedList 作为队列和栈

由于实现了Deque接口，LinkedList 可以非常方便地充当队列或栈：

Deque<String> deque = new LinkedList<>(); deque.offerLast("a"); // 入队 deque.offerLast("b"); String head = deque.pollFirst(); // 出队 Deque<String> stack = new LinkedList<>(); stack.push("x"); // 入栈 stack.push("y"); String top = stack.pop(); // 出栈

不过在实际工程中，如果只需要队列或栈能力，更推荐使用ArrayDeque。它基于环形数组实现，内存效率和性能通常优于基于链表节点的 LinkedList。这一点后文会再次提到。

六、时间复杂度全景对比

为了便于记忆和面试表达，这里给出两者的时间复杂度对照表。需要格外注意“按位置插入/删除”这一行的结论：LinkedList 并非完全的 O(1)。

从上表可以得出一个重要结论：LinkedList 相对 ArrayList 的绝对优势，主要集中在头部或尾部的插入删除；而在随机访问、遍历、按位置修改等场景中，LinkedList 几乎全面落后。这一结论与很多人“写多用 LinkedList”的直觉并不一致，后面我们会用测试数据进一步验证。

七、空间复杂度与内存模型

除了时间性能，内存占用也是选型时不能忽略的维度。很多人认为 ArrayList 因为预留容量而浪费内存，而 LinkedList 存多少用多少；但实际上，LinkedList 的每个节点都需要额外存储两个引用和一个对象头，开销可能远超想象。

7.1 ArrayList 的内存估算

ArrayList 的主要内存来自elementData数组。数组本身需要一段连续空间，大小等于elementData.length * referenceSize。在开启压缩指针的 64 位 JVM 中，每个引用通常占 4 字节。除了数组本身，数组对象还包含对象头和数组长度字段等固定开销。

如果创建 ArrayList 时预留了过大容量但实际元素很少，确实会浪费内存；但如果你能预估数据量并使用合适的初始容量，ArrayList 的空间效率是非常高的，因为它的空间几乎完全用于存储元素引用。

7.2 LinkedList 的内存估算

LinkedList 的每个元素都对应一个Node对象。一个Node至少包含：对象头（开启压缩指针后通常为 12 字节）、一个元素引用、一个next引用、一个prev引用。粗略估算，每个节点需要 12 + 4 + 4 + 4 = 24 字节，还不包括对齐填充。如果存储 100 万个元素，仅节点自身就会占用约 24 MB，而同规模 ArrayList 的数组引用部分只需要约 4 MB。

当然，这个估算会受 JVM 配置影响，例如是否开启-XX:+UseCompressedOops，以及对象对齐填充规则。但无论怎样，在元素数量相同的情况下，LinkedList 通常会比容量设置合理的 ArrayList 占用更多内存。

7.3 一个可直接运行的内存对比思路

下面这段代码可以用jol（Java Object Layout）工具精确打印对象布局。你可以在pom.xml中引入org.openjdk.jol:jol-core后运行：

import org.openjdk.jol.info.GraphLayout; import java.util.ArrayList; import java.util.LinkedList; public class MemoryFootprintDemo { public static void main(String[] args) { ArrayList<Integer> arrayList = new ArrayList<>(100_000); LinkedList<Integer> linkedList = new LinkedList<>(); for (int i = 0; i < 100_000; i++) { Integer v = i; arrayList.add(v); linkedList.add(v); } System.out.println("ArrayList footprint: " + GraphLayout.parseInstance(arrayList).totalSize() + " bytes"); System.out.println("LinkedList footprint: " + GraphLayout.parseInstance(linkedList).totalSize() + " bytes"); } }

在典型 64 位 JVM 配置下，LinkedList 的总占用会显著高于 ArrayList。这个实验可以帮助你建立直观印象：链表的“按需分配”并不等于“省内存”，每个节点的引用和对象头才是隐藏大头。

八、CPU 缓存与局部性原理

时间复杂度只能描述算法随数据规模增长的趋势，却无法解释常数项的巨大差异。在实际运行中，ArrayList 和 LinkedList 的性能差距，很大程度上还受到 CPU 缓存友好性的影响。

8.1 数组为什么缓存友好

ArrayList 的底层数组是一块连续内存。现代 CPU 会以缓存行（Cache Line，通常是 64 字节）为单位从主存加载数据。当你访问数组中第 i 个元素时，CPU 会顺势把相邻的一段数据加载到 L1/L2 缓存中；下一次访问第 i+1 个元素时，它很可能已经在缓存里，无需再访问主存。因此，顺序遍历数组时，缓存命中率极高，数据访问速度很快。

8.2 链表为什么会缓存不友好

LinkedList 的节点分配在堆的各个位置，彼此之间没有地址连续性。即使你按顺序遍历链表，下一个节点也可能位于完全不同的内存页，导致频繁的缓存未命中。每次缓存未命中都可能带来几十到上百个 CPU 周期的延迟。当链表越长，这种延迟累积得越明显。

这也是为什么即便两者在“遍历”上的渐近复杂度相同，实际测试中 ArrayList 的遍历速度往往比 LinkedList 快数倍甚至数十倍。

8.3 缓存友好性带来的工程启示

在做性能敏感开发时，不能只盯着大 O 复杂度，还要考虑数据结构的内存布局。对于需要频繁顺序扫描的数据，数组或基于数组的结构通常优于链表；链表更适合“频繁在头尾增删、且总体规模不大、很少随机访问”的场景。理解缓存行为，会让你的性能判断更接近真实世界。

九、性能实测：用数据说话

理论分析终归要落到测试。下面我们从随机访问、遍历、头部/中部/尾部插入删除等维度，对 ArrayList 和 LinkedList 做一组基准测试。为了让数据尽量可靠，示例会给出可运行的普通 Java 测试代码，并讨论如何避免 JIT 优化带来的误差。

9.1 一个朴素的性能测试框架

下面代码通过多次运行和平均值来减少偶然误差。测试前会先做一次预热，让 JIT 编译生效。注意，这种朴素测试不如 JMH 严谨，但足够帮助我们观察趋势。

import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class ListBenchmark { public static void main(String[] args) { measureRandomAccess(); measureIteration(); measureInsertion(); } private static void measureRandomAccess() { int n = 200_000; List<Integer> arrayList = new ArrayList<>(); List<Integer> linkedList = new LinkedList<>(); for (int i = 0; i < n; i++) { arrayList.add(i); linkedList.add(i); } warmUp(arrayList, linkedList); long start = System.nanoTime(); long sum = 0; for (int i = 0; i < n; i++) { sum += arrayList.get(i); } long arrayTime = System.nanoTime() - start; start = System.nanoTime(); for (int i = 0; i < n; i++) { sum += linkedList.get(i); } long linkedTime = System.nanoTime() - start; System.out.println("随机访问 ArrayList: " + arrayTime / 1_000_000 + " ms, sum=" + (sum & 1)); System.out.println("随机访问 LinkedList: " + linkedTime / 1_000_000 + " ms, sum=" + (sum & 1)); } private static void measureIteration() { int n = 300_000; List<Integer> arrayList = new ArrayList<>(); List<Integer> linkedList = new LinkedList<>(); for (int i = 0; i < n; i++) { arrayList.add(i); linkedList.add(i); } long start = System.nanoTime(); long sum = 0; for (Integer v : arrayList) { sum += v; } long arrayTime = System.nanoTime() - start; start = System.nanoTime(); for (Integer v : linkedList) { sum += v; } long linkedTime = System.nanoTime() - start; System.out.println("迭代器遍历 ArrayList: " + arrayTime / 1_000_000 + " ms, sum=" + (sum & 1)); System.out.println("迭代器遍历 LinkedList: " + linkedTime / 1_000_000 + " ms, sum=" + (sum & 1)); } private static void measureInsertion() { int n = 100_000; List<Integer> arrayList = new ArrayList<>(); for (int i = 0; i < n; i++) arrayList.add(i); List<Integer> linkedList = new LinkedList<>(); for (int i = 0; i < n; i++) linkedList.add(i); long start = System.nanoTime(); for (int i = 0; i < 10_000; i++) { arrayList.add(0, i); } long arrayHeadInsert = System.nanoTime() - start; start = System.nanoTime(); for (int i = 0; i < 10_000; i++) { linkedList.add(0, i); } long linkedHeadInsert = System.nanoTime() - start; System.out.println("头部插入 ArrayList: " + arrayHeadInsert / 1_000_000 + " ms"); System.out.println("头部插入 LinkedList: " + linkedHeadInsert / 1_000_000 + " ms"); } private static void warmUp(List<Integer> a, List<Integer> b) { for (int i = 0; i < 20_000; i++) { a.get(i); b.get(i); } } }

9.2 随机访问：差距是数量级的

在随机访问测试中，当数据量为 20 万时，ArrayList 的get(i)通常只需要几毫秒，而 LinkedList 可能需要数秒。这个差距还会随着数据量增长而进一步扩大，因为前者是 O(1)，后者是 O(n)，且每次get(i)还需要一次从链表头或尾出发的遍历。

9.3 遍历：用 get(i) 是 LinkedList 的大忌

很多初学者在遍历 LinkedList 时习惯写：

for (int i = 0; i < list.size(); i++) { System.out.println(list.get(i)); }

对 ArrayList 来说，这段代码没有问题；但对 LinkedList 来说，每次get(i)都是 O(n)，整体遍历就退化为 O(n²)。当数据量达到几万时，程序会明显变慢。这就是为什么遍历 LinkedList 必须使用增强 for 循环或显式迭代器，让迭代器内部保存当前节点引用，实现 O(n) 遍历。

// 推荐写法：迭代器顺序遍历，时间复杂度 O(n) for (Integer v : linkedList) { System.out.println(v); }

9.4 插入与删除：位置决定结论

插入删除的测试必须区分位置：

• 头部插入：LinkedList 是 O(1)，优势非常明显，尤其是元素很多时。
• 尾部追加：两者差距不大。ArrayList 均摊 O(1)，LinkedList 的add也是 O(1)。在某些实现上，ArrayList 反而可能更快。
• 中间插入：ArrayList 需要搬移元素，LinkedList 需要先遍历定位。实测中，只有当插入位置非常靠前时 LinkedList 才有明显优势；随着位置靠近尾部，ArrayList 往往反超。

这说明“LinkedList 增删快”必须加上严格的位置限定，否则会得出错误结论。

9.5 为什么建议使用 JMH 做严格基准

上面的朴素测试适合观察趋势，但如果要得到严谨结论，推荐使用 JMH（Java Microbenchmark Harness）。JMH 可以处理 JIT 预热、死代码消除、伪共享、测试方法内联等问题，让测试结果更可信。以下是一个基于 JMH 的随机访问基准示例：

import org.openjdk.jmh.annotations.*; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.concurrent.TimeUnit; @BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.MICROSECONDS) @State(Scope.Thread) @Warmup(iterations = 3, time = 1) @Measurement(iterations = 5, time = 1) @Fork(1) public class JmhListBenchmark { @Param({"1000", "10000", "100000"}) int size; List<Integer> arrayList; List<Integer> linkedList; @Setup(Level.Trial) public void setup() { arrayList = new ArrayList<>(size); linkedList = new LinkedList<>(); for (int i = 0; i < size; i++) { arrayList.add(i); linkedList.add(i); } } @Benchmark public long arrayListRandomAccess() { long sum = 0; for (int i = 0; i < size; i++) { sum += arrayList.get(i); } return sum; } @Benchmark public long linkedListRandomAccess() { long sum = 0; for (int i = 0; i < size; i++) { sum += linkedList.get(i); } return sum; } }

运行 JMH 测试你会看到：随着size增大，ArrayList 随机访问的平均时间基本保持稳定，而 LinkedList 的平均时间近似线性增长。这种数据趋势比任何口头结论都更有说服力。

十、常见误区与反直觉结论

10.1 误区一：LinkedList 中间插入删除是 O(1)

这个误区来源于只看到指针修改的部分。实际上，通过公共 API 在中间位置插入或删除时，必须先调用node(index)找到目标位置的节点，这一步是 O(n)。所以完整操作是 O(n)。只有在你自己实现链表并已经持有目标节点引用时，指针修改才是 O(1)。

10.2 误区二：写多读少就一定用 LinkedList

如果“写”指的是尾部追加，ArrayList 的均摊成本同样是 O(1)，且经常因为缓存友好而更快；如果“写”指的是中间随机插入，LinkedList 的定位成本也不能忽略。只有频繁在头部插入删除，或者明确使用队列的头部出队、尾部入队语义时，LinkedList 的优势才稳定成立。

10.3 误区三：遍历 LinkedList 用 for 加 get 没关系

这是一个灾难性的性能误区。正如前文分析，for (int i; i < list.size(); i++) { list.get(i); }会把 LinkedList 的遍历退化为 O(n²)。当用户量较大、列表较长时，这会让服务响应时间急剧恶化，而且很难一眼从代码里看出来。正确做法是使用增强 for 循环或迭代器。

10.4 误区四：ArrayList 默认容量是 10，所以空列表也占 10 个位置

在较新的 JDK 版本中，无参构造的 ArrayList 采用懒初始化，创建后elementData是一个空数组，只有第一次添加元素时才会分配容量。因此“创建 1000 个空 ArrayList 就浪费 10000 个引用空间”的说法在现行实现下并不成立。

10.5 误区五：链表在内存上更省

链表的节点除了存储元素引用，还需要next和prev两个引用以及对象头，整体内存成本通常高于容量设置合理的数组。链表省下的是“不需要预先分配连续大块内存”，而不是“总内存更少”。

十一、如何选择：一份可落地的决策清单

综合以上分析，我们可以把 ArrayList 和 LinkedList 的选型拆解成具体场景。以下清单可以直接用于实际工程判断。

11.1 优先选择 ArrayList 的场景

• 随机访问频繁：需要通过下标频繁读取元素的场景，如分页查询中的索引定位、实现自定义列表、按位置取值等。
• 顺序遍历为主：几乎所有以遍历、批量处理为主的数据集合，ArrayList 的缓存友好性会带来明显性能优势。
• 尾部追加为主：日志缓冲、结果集收集、流式写入等尾部追加场景，ArrayList 均摊 O(1)，性能稳定。
• 需要排序和二分查找：Collections.sort、binarySearch对实现了RandomAccess的 ArrayList 有专门优化。
• 数据规模可预估：能预估元素数量时，可以通过构造器指定初始容量，减少扩容次数，空间效率很高。
• 作为方法的通用 List 返回类型：大多数业务方法默认返回ArrayList即可满足需求，语义更清晰。

11.2 可以考虑 LinkedList 的场景

• 频繁在头部插入或删除：例如需要维护一个“最近使用”列表，每当访问某项就把它移到头部，这种场景 LinkedList 的 O(1) 头插头删优势明显。
• 需要双端队列语义：需要在头部和尾部同时进行增删操作时，LinkedList 提供 O(1) 的双端操作。
• 几乎不做随机访问：如果业务只依赖迭代器顺序处理，并且频繁在列表中段附近增删且规模不大，LinkedList 才能勉强体现出价值。
• 作为教学或算法练习：理解链表结构时，使用 LinkedList 并配合迭代器是很好的学习路径。

11.3 如果只需要队列或栈，请考虑 ArrayDeque

这是很多开发者容易忽略的一点：当你的核心诉求是 FIFO 队列或 LIFO 栈，而不是一个 List 时，ArrayDeque通常是比 LinkedList 更好的选择。ArrayDeque 基于可变环形数组，头尾操作都是 O(1)，而且没有链表节点带来的内存和缓存开销。只有当你必须依赖List接口，并且确实需要高频头尾操作时，才选择 LinkedList。

Deque<String> queue = new ArrayDeque<>(); queue.offerLast("任务1"); queue.offerLast("任务2"); String task = queue.pollFirst();

11.4 决策口诀

如果只能用一句话概括，可以是：默认用 ArrayList；只有明确存在“高频头部增删”或“需要 List 语义下的双端队列”时，才考虑 LinkedList；如果只需要队列或栈，优先用 ArrayDeque。不要再用一句模糊的“读多写少”来做选型判断。

十二、面试高频追问与解析

在实际面试中，当你说出两者的基本区别后，面试官往往会继续追问细节。以下整理了常见追问和答题要点。

12.1 追问：ArrayList 扩容为什么是 1.5 倍？

扩容倍数的选择是空间和时间的折中。倍数为 1 意味着每次只加一点点，扩容太频繁，拷贝开销大；倍数太高（如 2 倍）虽然扩容次数少，但可能造成较多空闲空间。1.5 倍是在实践中得到较好平衡的一个经验值，既控制了扩容次数，又不会造成过多容量浪费。从数学上看，1.5 倍扩容还能让“历史上分配并释放过的内存总量”保持在可接受的范围内，减少内存碎片压力。

12.2 追问：为什么 elementData 要用 transient 修饰？

因为elementData数组的实际长度通常大于元素个数size。如果不加transient并自定义序列化逻辑，默认序列化会把数组中的空位也写入序列化结果，造成体积膨胀。ArrayList 通过重写writeObject和readObject，只序列化前size个元素。

12.3 追问：ArrayList 的 fail-fast 是怎么实现的？

ArrayList 内部维护modCount结构修改计数器，迭代器创建时会记录当前的expectedModCount。每次迭代都检查二者是否一致，不一致就抛出ConcurrentModificationException。它只能检测迭代期间的并发结构修改，不能保证线程安全。

12.4 追问：为什么 LinkedList 实现了 Deque 而不是只实现 List？

因为 LinkedList 底层是双向链表，天然适合在两端进行 O(1) 插入删除，实现Deque可以直接提供队列和栈的操作，扩展其用途。而 ArrayList 在头部插入删除成本高，不适合实现Deque。

12.5 追问：RandomAccess 接口有什么用？

它是一个标记接口，表示实现类支持快速随机访问。JDK 中的算法工具会根据该接口选择更优策略，例如Collections.binarySearch在支持随机访问时直接按下标折半，否则会退化为基于迭代器的二分查找。我们自己写通用工具时，也可以在遍历前用instanceof RandomAccess判断遍历方式。

12.6 追问：ArrayList 和 Vector 的区别？

两者底层都是动态数组，但Vector是线程安全的，几乎所有读写方法都用synchronized修饰，性能较差；ArrayList 是线程不安全的，在单线程或已由外部加锁保证安全的环境中性能更好。此外，Vector 默认扩容是 2 倍，可以通过构造器指定增量。现代开发中，基本不推荐使用 Vector，需要线程安全时优先考虑CopyOnWriteArrayList或Collections.synchronizedList。

十三、其他常见 List 实现对比

理解 ArrayList 和 LinkedList 之后，再把视野放宽到其他常见 List 实现，会有助于在更丰富的场景下做选择。

13.1 Vector 与 Stack

Vector是 ArrayList 的线程安全版本，但锁粒度粗、性能差，基本属于历史遗留类型。Stack继承自Vector，提供了栈操作，但其实现同样因为继承 Vector 而臃肿。现代开发中，栈应优先使用ArrayDeque。

13.2 CopyOnWriteArrayList

CopyOnWriteArrayList是并发场景下的一种选择。它在每次写操作时都会复制一份底层数组，因此写成本很高，但读操作完全无锁。它最典型的适用场景是读多写极少的场景，例如监听器列表、黑名单、配置项列表等。需要注意，它的迭代器是弱一致性快照，迭代过程中看到的是一份创建迭代器时的数据快照。

List<String> listeners = new CopyOnWriteArrayList<>(); listeners.add("监听器A"); for (String listener : listeners) { // 读操作无锁，写操作会复制数组 System.out.println(listener); }

13.3 Arrays.asList 返回的 List

Arrays.asList返回的是一个固定大小的ArrayList，不过它是java.util.Arrays的内部类，和java.util.ArrayList不是同一个类。这个列表不支持add和remove，调用会抛UnsupportedOperationException；但可以通过set修改元素，且修改会反映到原数组上。需要可变列表时，应该像下面这样转换：

List<String> fixed = Arrays.asList("a", "b", "c"); List<String> mutable = new ArrayList<>(fixed); mutable.add("d");

13.4 Collections.synchronizedList

Collections.synchronizedList可以包装一个普通 List 为线程安全列表，但它的锁粒度同样较粗，且迭代时需要外部同步。除非业务非常简单且不追求高并发，否则更推荐使用并发容器或显式锁来保证正确性和性能。

十四、把知识落到工程实践：一份自查清单

理论学习之后，我们需要把它转化为日常开发的习惯。下面这些检查点，建议你在每次创建或使用 List 时快速过一遍。

• 是否真的需要 List？如果只是键值对，应该用 Map；如果只是去重集合，应该用 Set；如果只是队列或栈，优先考虑 ArrayDeque。
• 数据规模是否可预估？如果使用 ArrayList，传入合理的初始容量，避免反复扩容；容量也不要过大，避免内存浪费。
• 访问模式是什么？随机访问为主选 ArrayList；头部/尾部操作为主再考虑 LinkedList。
• 是否依赖下标遍历？如果是 LinkedList，坚决避免get(i)循环，改用增强 for 或迭代器。
• 是否存在并发访问？读多写少考虑 CopyOnWriteArrayList，否则用显式锁或并发容器。
• 返回类型是否依赖具体实现？尽量以List接口作为方法签名，降低调用方对具体实现的耦合。

十五、总结：从背结论到建立判断力

回到文章开头的那个问题：ArrayList 还是 LinkedList？经过前文的层层剖析，答案已经不再是简单的一句话。

ArrayList基于动态数组，随机访问快、遍历快、缓存友好，尾部追加均摊 O(1)，但中间插入删除需要搬移元素，扩容时会产生一次较大的复制开销。它是绝大多数业务场景下的默认选择。

LinkedList基于双向链表，头尾插入删除为 O(1)，同时实现了 Deque，可以作为队列和栈使用；但它的随机访问、按位置插入删除、空间效率和缓存友好性都明显落后于 ArrayList。它真正的适用场景，是“高频在头部操作”或“需要在 List 语义下进行双端队列操作”的少数情况。

更重要的是，我们要学会用数据结构和计算机体系结构的角度去理解集合类，而不是死记结论。数组与链表的选择，本质上是连续内存与离散节点、缓存友好与指针灵活、搬移成本与查找成本之间的权衡。当你建立起这种判断力后，无论是面试还是真实系统设计，都能给出有理有据的答案。

最后留给大家三个可以动手验证的实验方向：第一，用 JMH 复现本文的随机访问与遍历基准，观察 LinkedList 随机访问随规模增长的曲线；第二，用 jol 打印 10 万级元素下两者的内存占用，直观感受链表节点开销；第三，写一个“最近使用”列表体感的头插场景，对比 ArrayList 和 LinkedList 在头插 1 万次时的耗时差异。相信做完这三个实验，你对这个问题的理解会比读十篇只给结论的文章更深刻。

一句话速记：默认使用 ArrayList；高频头部增删或需要 List 语义的双端队列时，才考虑 LinkedList；只需要队列或栈时，优先选择 ArrayDeque。记住这个优先级，能帮你避开大多数误用场景。