ArrayList vs LinkedList：底层原理、性能对决与扩容机制全解析
ArrayList vs LinkedList：底层原理、性能对决与扩容机制全解析
1. 引言
在 Java 开发中，ArrayList和LinkedList是最常用的两种List实现。面试官常常抛出这样一个问题：“ArrayList 和 LinkedList 有什么区别？” 如果你只回答“数组 vs 链表，查询快增删慢”，显然不够深入。真正的理解需要结合底层数据结构、内存布局、时间复杂度以及实际场景的选型。
本文将从源码级别剖析两者差异，并详细解读ArrayList的动态扩容机制（包括 1.5 倍扩容的由来），配合流程图和性能对比表，让你彻底掌握这两个集合类的本质。
2. 架构概览（UML 类图）
ArrayList基于数组实现，LinkedList基于双向链表实现。两者都实现了List接口，但内部结构决定了它们截然不同的性能特征。
3. ArrayList 与 LinkedList 核心区别
| 对比维度 | ArrayList | LinkedList |
|---|---|---|
| 底层数据结构 | 动态数组（Object[]） | 双向链表（Node 节点） |
| 随机访问（get/set） | O(1) 极快 | O(n) 需要遍历 |
| 插入/删除 | 尾部 O(1)（无需移动），中间 O(n)（需要移动元素） | 头尾 O(1)，中间 O(n)（需定位到位置） |
| 内存占用 | 数组有预留空间（可能浪费），但每个元素只存引用 | 每个节点额外存储两个指针（prev/next），内存开销更大 |
| 线程安全 | 非线程安全（需外部同步） | 非线程安全 |
| 迭代性能 | 连续内存，CPU 缓存友好 | 节点分散，缓存不友好 |
| 适用场景 | 随机访问多、尾部插入多 | 频繁头部/尾部操作、中间插入删除少 |
3.1 详细解读
3.1.1 为什么 ArrayList 查询快？
ArrayList底层是一个连续的内存数组。通过索引访问元素时，只需计算baseAddress + index * elementSize，直接定位到内存地址，时间复杂度 O(1)。而LinkedList需要通过指针逐个遍历，即使获取中间元素也要从头部或尾部开始移动，复杂度 O(n)。
3.1.2 为什么 LinkedList 增删快？（特指头部/尾部）
对于LinkedList，在头部或尾部添加/删除元素只需修改几个指针引用，时间复杂度 O(1)。但在中间位置插入或删除，仍然需要先遍历到该位置（O(n)），然后修改指针，总体仍是 O(n)。相比之下，ArrayList在中间插入/删除需要移动后续所有元素，成本极高。
// ArrayList 中间插入源码示意publicvoidadd(intindex,Eelement){// 检查越界// 扩容// 使用 System.arraycopy 移动元素System.arraycopy(elementData,index,elementData,index+1,size-index);elementData[index]=element;size++;}3.1.3 性能测试（参考数据）
| 操作 | ArrayList (10w条) | LinkedList (10w条) |
|---|---|---|
| 尾部添加 | ~2ms | ~3ms |
| 头部添加 | ~50ms | ~2ms |
| 中间添加 | ~35ms | ~20ms（定位+插入） |
| 随机访问 | ~1ms | ~150ms |
| 迭代 | 快 | 较慢（节点跳跃） |
结论：日常开发中 90% 的场景使用
ArrayList即可；只有需要频繁在头部或尾部插入/删除（如实现队列、栈）时，才考虑LinkedList。
4. ArrayList 自动扩容机制深度剖析
ArrayList的底层数组长度是固定的，当添加的元素超过当前数组容量时，必须进行扩容。理解扩容机制对于优化内存和性能至关重要。
4.1 扩容流程
4.2 扩容规则源码解读（JDK 8+）
// ArrayList 中的 grow 方法privatevoidgrow(intminCapacity){// 旧容量intoldCapacity=elementData.length;// 新容量 = 旧容量 + 旧容量 >> 1（即 1.5 倍）intnewCapacity=oldCapacity+(oldCapacity>>1);// 如果新容量仍小于所需最小容量，则使用 minCapacityif(newCapacity-minCapacity<0)newCapacity=minCapacity;// 如果新容量超过 MAX_ARRAY_SIZE，则调用 hugeCapacityif(newCapacity-MAX_ARRAY_SIZE>0)newCapacity=hugeCapacity(minCapacity);// 复制数组elementData=Arrays.copyOf(elementData,newCapacity);}关键点：
- 初始容量：无参构造时，
elementData指向一个空数组{}，第一次add时才会扩容到默认的DEFAULT_CAPACITY = 10。 - 扩容倍数：
oldCapacity + (oldCapacity >> 1)=oldCapacity * 1.5。右移一位相当于除以 2，再加上原值得到 1.5 倍。 - 为什么是 1.5 倍？权衡空间与时间：太小（如 1.1 倍）会导致频繁扩容，影响性能；太大（如 2 倍）可能浪费内存。1.5 倍是一个经验值，既减少扩容次数，又不会造成过多空间浪费。
4.3 示例：扩容过程演示
假设初始容量为 10，添加第 11 个元素时触发扩容：
| 操作次数 | 当前容量 | 元素个数 | 是否扩容 | 新容量 |
|---|---|---|---|---|
| 1~10 | 10 | 0→10 | 首次 add 时从 0 扩容到 10 | 10 |
| 11 | 10 | 11 | 是 | 10 + 10>>1 = 15 |
| 16 | 15 | 16 | 是 | 15 + 7 = 22 |
| 23 | 22 | 23 | 是 | 22 + 11 = 33 |
| … | … | … | … | … |
每次扩容都会发生一次Arrays.copyOf，这是一个 O(n) 操作，因此尽量在创建 ArrayList 时指定合适的初始容量，可避免多次扩容带来的性能损耗。
// 预估需要存储 10000 个元素List<String>list=newArrayList<>(10000);4.4 容量相关方法
ensureCapacity(int minCapacity)：手动预分配容量（提前扩容）。trimToSize()：将数组容量收缩到当前实际元素个数，释放多余内存（适合大量添加后不再增加的情况）。
5. 对比总结与选型建议
5.1 决策流程图
5.2 性能黄金法则
- 读多写少→
ArrayList - 队列/栈（头尾操作）→
LinkedList（或ArrayDeque更优） - 无法预估数据量且频繁追加→
ArrayList并指定初始容量 - 需要线程安全→
Vector（已过时）或Collections.synchronizedList或CopyOnWriteArrayList
5.3 特别注意
LinkedList并不适合所有“增删快”场景：中间插入仍需遍历，且内存开销大，在多数实际业务中ArrayList表现更好。ArrayList的扩容是一个代价较高的操作，大数据量下务必预分配容量。
6. 常见面试题
Q1: ArrayList 初始容量是 10 吗？
答：无参构造时，初始容量为 0，第一次add时才扩容到 10。可以通过new ArrayList(10)直接指定初始容量。
Q2: 为什么 ArrayList 扩容是 1.5 倍，而不是 2 倍？
答：1.5 倍是时间与空间的折中。过大的扩容因子（如 2 倍）会导致内存浪费；过小的因子（如 1.1 倍）会导致频繁扩容。1.5 倍经过实践检验，性能较好。
Q3: LinkedList 实现了 Deque 接口，能否作为双端队列使用？
答：可以。LinkedList实现了Deque，提供addFirst、addLast、pollFirst、pollLast等方法。但如果是纯队列场景，ArrayDeque性能通常更优（基于循环数组，无节点开销）。
Q4: ArrayList 的System.arraycopy和Arrays.copyOf有什么区别？
答：System.arraycopy是 native 方法，直接复制内存区域；Arrays.copyOf内部调用了System.arraycopy，但会先创建新数组。两者都是高效的浅拷贝。
7. 总结
ArrayList：基于数组，随机访问 O(1)，中间插入删除 O(n)，扩容 1.5 倍。LinkedList：基于双向链表，头尾操作 O(1)，随机访问 O(n)，内存开销大。- 扩容机制：首次添加时扩容到 10，之后每次扩容为当前的 1.5 倍（
oldCapacity + oldCapacity >> 1）。 - 选型建议：绝大多数情况选
ArrayList，只有明确需要频繁头尾操作且不需要随机访问时才考虑LinkedList。
记住一句话：“数组紧凑链表散，随机选 Array，队尾队首看 List。”