一、引言一道经久不衰的面试题在 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等方法时语义应当是一致的。ListString arrayList new ArrayList(); ListString 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 ArrayListE extends AbstractListE implements ListE, RandomAccess, Cloneable, java.io.SerializableLinkedList 的继承关系如下public class LinkedListE extends AbstractSequentialListE implements ListE, DequeE, Cloneable, java.io.Serializable这里有一个非常关键的差异ArrayList 实现了RandomAccess接口而 LinkedList 没有。这个接口本身没有任何方法它是一个标记接口用来告诉算法实现者“这个 List 支持快速随机访问”。JDK 中的很多工具类比如Collections.binarySearch会根据是否实现RandomAccess来选择不同的算法策略。理解了这一点你也就能理解为什么遍历 LinkedList 时不建议使用基于下标的get(i)循环。另一个值得注意的点是LinkedList 实现了Deque接口这意味着它不仅是一个 List还是一个双端队列。你可以把它当作队列、栈来使用这为它的适用场景增加了更多可能性。三、底层数据结构动态数组与双向链表3.1 ArrayList基于动态数组ArrayList 的底层其实就是一个对象数组。这个数组在 JDK 源码中对应字段elementDatatransient Object[] elementData;所谓“动态”是指当数组容量不足以容纳新元素时ArrayList 会自动创建一个更大的数组把旧数组的元素复制过去再用新数组替换旧数组。这个过程称为“扩容”。因为数组是连续的内存空间所以通过下标计算地址后可以在 O(1) 时间内直接读取元素但插入和删除时往往需要移动后续元素成本较高。3.2 LinkedList基于双向链表LinkedList 的底层是一个双向链表。链表中的每个节点是一个内部类Nodeprivate static class NodeE { E item; NodeE next; NodeE prev; Node(NodeE prev, E element, NodeE 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表示默认初始容量为 10elementData是真正存放元素的数组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 NodeE first; transient NodeE last;它只维护了size、first和last三个字段。前者记录元素个数后两者分别指向头节点和尾节点。每个节点持有元素值以及前后两个引用因此整个结构是一个双向链表。5.2 头部与尾部添加链表的强项LinkedList 在头尾添加元素的方法有多个变体例如addFirst、addLast、offerFirst、offerLast但核心实现都类似。以下以尾部添加为例void linkLast(E e) { final NodeE l last; final NodeE 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。NodeE node(int index) { if (index (size 1)) { NodeE x first; for (int i 0; i index; i) x x.next; return x; } else { NodeE 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, NodeE succ) { final NodeE pred succ.prev; final NodeE 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 (NodeE x first; x ! null; x x.next) { if (x.item null) { unlink(x); return true; } } } else { for (NodeE x first; x ! null; x x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }5.6 LinkedList 作为队列和栈由于实现了Deque接口LinkedList 可以非常方便地充当队列或栈DequeString deque new LinkedList(); deque.offerLast(a); // 入队 deque.offerLast(b); String head deque.pollFirst(); // 出队 DequeString stack new LinkedList(); stack.push(x); // 入栈 stack.push(y); String top stack.pop(); // 出栈不过在实际工程中如果只需要队列或栈能力更推荐使用ArrayDeque。它基于环形数组实现内存效率和性能通常优于基于链表节点的 LinkedList。这一点后文会再次提到。六、时间复杂度全景对比为了便于记忆和面试表达这里给出两者的时间复杂度对照表。需要格外注意“按位置插入/删除”这一行的结论LinkedList 并非完全的 O(1)。操作ArrayListLinkedList说明按索引访问 get(int)O(1)O(n)LinkedList 需遍历查找节点尾部追加 add(E)均摊 O(1)O(1)ArrayList 偶尔扩容头部插入 addFirstO(n)O(1)ArrayList 需整体搬移中间按位置插入 add(int, E)O(n)O(n)LinkedList 定位就需要 O(n)按位置删除 remove(int)O(n)O(n)同理LinkedList 先定位按元素删除 remove(Object)O(n)O(n)都需要先查找再删除修改 set(int, E)O(1)O(n)LinkedList 先定位节点遍历 for(int i)O(n)O(n²)LinkedList 每次 get 都是 O(n)增强 for / 迭代器O(n)O(n)迭代器会保存当前节点引用是否支持随机访问是 RandomAccess否影响 JDK 工具类算法选择从上表可以得出一个重要结论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 一个可直接运行的内存对比思路下面这段代码可以用jolJava 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) { ArrayListInteger arrayList new ArrayList(100_000); LinkedListInteger 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 缓存中下一次访问第 i1 个元素时它很可能已经在缓存里无需再访问主存。因此顺序遍历数组时缓存命中率极高数据访问速度很快。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; ListInteger arrayList new ArrayList(); ListInteger 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; ListInteger arrayList new ArrayList(); ListInteger 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; ListInteger arrayList new ArrayList(); for (int i 0; i n; i) arrayList.add(i); ListInteger 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(ListInteger a, ListInteger 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 做严格基准上面的朴素测试适合观察趋势但如果要得到严谨结论推荐使用 JMHJava 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; ListInteger arrayList; ListInteger 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。DequeString 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 与 StackVector是 ArrayList 的线程安全版本但锁粒度粗、性能差基本属于历史遗留类型。Stack继承自Vector提供了栈操作但其实现同样因为继承 Vector 而臃肿。现代开发中栈应优先使用ArrayDeque。13.2 CopyOnWriteArrayListCopyOnWriteArrayList是并发场景下的一种选择。它在每次写操作时都会复制一份底层数组因此写成本很高但读操作完全无锁。它最典型的适用场景是读多写极少的场景例如监听器列表、黑名单、配置项列表等。需要注意它的迭代器是弱一致性快照迭代过程中看到的是一份创建迭代器时的数据快照。ListString listeners new CopyOnWriteArrayList(); listeners.add(监听器A); for (String listener : listeners) { // 读操作无锁写操作会复制数组 System.out.println(listener); }13.3 Arrays.asList 返回的 ListArrays.asList返回的是一个固定大小的ArrayList不过它是java.util.Arrays的内部类和java.util.ArrayList不是同一个类。这个列表不支持add和remove调用会抛UnsupportedOperationException但可以通过set修改元素且修改会反映到原数组上。需要可变列表时应该像下面这样转换ListString fixed Arrays.asList(a, b, c); ListString mutable new ArrayList(fixed); mutable.add(d);13.4 Collections.synchronizedListCollections.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。记住这个优先级能帮你避开大多数误用场景。