🚀 Java 中的 ArrayList 和 LinkedList 区别详解(源码级理解)
在日常 Java 开发中,ArrayList
和 LinkedList
是我们经常用到的两种 List 实现。虽然它们都实现了 List
接口,但在底层结构、访问效率、插入/删除操作、扩容机制等方面差异明显。
本文从实际源码出发,结合内存结构与操作成本,详细分析二者的异同,帮助你更合理地做出选型。
📦 1. ArrayList —— 基于数组的动态列表
✅ 底层结构
ArrayList
的底层是一个 动态对象数组Object[] elementData
- 内存中是 连续存储
- 元素个数由
size
字段控制,和数组容量 (elementData.length
) 分开管理
transient Object[] elementData; // 存储元素的数组
private int size; // 实际元素个数
🚀 访问性能
- 由于数组结构内存连续,可以通过 起始地址 + 下标 × 元素大小 直接定位
- 访问效率为 O(1),非常快
🧱 添加元素的逻辑
默认容量为 10,首次添加时触发初始化
如果容量不足,会执行 扩容(grow)操作
- 扩容策略:原容量的 1.5 倍
- 核心操作是新建数组 + 拷贝旧数据(
System.arraycopy
)
int newCapacity = oldCapacity + (oldCapacity >> 1);
System.arraycopy(elementData, 0, newArray, 0, size);
🧹 删除元素的逻辑
- 如果删除的是中间位置,需要将后面的元素全部 前移一位
- 删除最后一个元素后,会将该位置置为
null
,防止内存泄露
System.arraycopy(elementData, index + 1, elementData, index, size - index - 1);
elementData[--size] = null;
- ❌ 不会自动缩容,避免频繁扩容/缩容带来的性能波动(可以手动
trimToSize()
)
⚠️ ArrayList 的缺点
- 插入/删除中间元素时会频繁移动数组,效率低(O(n))
- 扩容需要申请新数组并复制,性能有开销
🔗 2. LinkedList —— 基于双向链表的列表结构
✅ 底层结构
LinkedList
是典型的 双向链表- 每个节点是一个
Node
对象,包含prev
,next
,item
- 元素在内存中 不连续存储
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
}
🧱 插入/删除性能优势
- 插入/删除某个位置时,只需修改相邻节点的指针,效率高
- ❌ 不需要扩容,也不会拷贝数组
🐢 访问性能劣势
- 链表无法通过下标快速定位元素
- 访问第 n 个元素需要从头或尾遍历(O(n))
⚠️ LinkedList 的缺点
- 每个元素多占用 2 个引用(prev 和 next)
- 访问性能差,尤其在需要频繁随机读取场景下
🧮 ArrayList 与 LinkedList 对比总结
特性 | ArrayList(动态数组) | LinkedList(双向链表) |
---|---|---|
底层结构 | 连续 Object[] 数组 |
不连续的 Node 链表 |
访问速度 | 快,O(1) 随机访问 | 慢,需要遍历,O(n) |
插入删除 | 慢,需要移动数组元素 | 快,仅需改指针 |
扩容机制 | 支持,扩容为 1.5 倍 | 无需扩容 |
内存使用 | 少(只存数据) | 多(每节点多两个引用) |
应用场景 | 读多写少,随机访问场景 | 写多读少,插入删除频繁场景 |
✅ 最佳实践建议
- 读多写少、频繁按下标访问 ➤ 用
ArrayList
- 写多读少、频繁插入/删除中间元素 ➤ 用
LinkedList
- 如果你在处理的是“队列”或“栈”场景 ➤ 也可以考虑
Deque
或ArrayDeque
🔚 总结
理解 ArrayList
和 LinkedList
的底层结构,能帮助你在性能、内存、复杂度方面做出更合理的设计选择。切记:
不要被接口迷惑,底层结构决定一切。