从源码深挖 ArrayList 与 LinkedList 的性能差异
在 Java 集合框架中，ArrayList 和 LinkedList 作为 List 接口的两个典型实现，经常被拿来对比。很多开发者仅停留在'ArrayList 基于数组、LinkedList 基于链表'的表层认知，却忽略了底层源码设计对性能的决定性影响。本文将从源码出发，从初始化、增删改查、内存占用等多维度拆解两者的性能差异，帮你在实际开发中精准选型。
底层结构：数组 vs 双向链表
要理解性能差异，首先得从两者的底层数据结构说起，这是一切性能表现的根源。
ArrayList：动态扩容的 Object 数组
ArrayList 的核心是一个 transient Object[] elementData 数组，Java 源码中定义如下：
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer.
*/
transient Object[] elementData; // non-private to simplify nested class access
数组的特性是内存连续存储，这让随机访问可以通过下标直接定位，时间复杂度为 O(1)；但也带来了扩容成本和插入删除时的元素移动开销。
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;
}
}
同时维护了首尾节点指针：
transient Node<E> first;
transient Node<E> last;
链表的节点在内存中分散存储，通过指针关联，插入删除仅需改变指针指向，但随机访问需要遍历链表，时间复杂度为 O(n)。
核心操作性能对比
接下来我们从源码角度，逐一分析增、删、改、查四大核心操作的性能差异。
查找：ArrayList 完胜，O(1) vs O(n)
ArrayList 的随机访问：直接通过数组下标定位，源码非常简洁：
public E get(int index) {
Objects.checkIndex(index, size);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
只要下标合法，就能在常数时间内获取元素，这是数组天生的优势。
LinkedList 的随机访问：需要从首节点或尾节点开始遍历，源码如下：
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
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;
}
}
虽然做了优化（判断 index 靠近头部还是尾部，减少遍历次数），但最坏情况下仍需遍历半个链表，时间复杂度为 O(n)。
结论：频繁随机访问场景，ArrayList 性能碾压 LinkedList。
新增：头部/中间插入 LinkedList 优，尾部插入 ArrayList 更稳
新增操作的性能差异，主要体现在是否需要移动元素和扩容成本。
ArrayList 新增元素：
- 尾部新增：如果数组未扩容，直接赋值，时间复杂度 O(1)；如果需要扩容，会触发
grow()方法，将原数组复制到新数组，时间复杂度变为 O(n)。
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;
}
- 中间/头部新增：需要将插入位置后的所有元素向后移动一位，时间复杂度 O(n)，源码如下：
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;
}
LinkedList 新增元素：
- 尾部新增：直接将新节点设为 last，原 last 的 next 指向新节点，时间复杂度 O(1)
public boolean add(E e) {
linkLast(e);
return true;
}
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++;
}
- 中间/头部新增：只需找到对应节点，改变前后指针指向，无需移动元素，时间复杂度 O(1)（但查找插入位置需要 O(n) 时间）
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size) linkLast(element);
else linkBefore(element, node(index));
}
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++;
}
结论：
- 频繁在列表头部/中间插入元素，LinkedList 更优（前提是已找到插入位置）；
- 仅在尾部新增元素，ArrayList 性能更稳定（无扩容时 O(1)，扩容时 O(n)）。
删除：逻辑与新增对称，LinkedList 仍有优势
删除操作的性能逻辑和新增类似，核心差异还是元素移动 vs 指针修改。
ArrayList 删除元素：
- 尾部删除：直接将对应位置置为 null，时间复杂度 O(1)；
- 中间/头部删除：需要将删除位置后的元素向前移动一位，时间复杂度 O(n)，源码如下：
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked")
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; // clear to let GC do its work
}
LinkedList 删除元素：只需改变对应节点的前后指针，时间复杂度 O(1)（同样，查找待删除节点需要 O(n) 时间）：
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null; // help GC
size--;
modCount++;
return element;
}
结论：删除操作的性能差异与新增一致，LinkedList 在非尾部删除时更有优势。
修改：ArrayList O(1)，LinkedList O(n)
修改操作的核心是定位元素 + 赋值：
- ArrayList 直接通过下标定位元素，赋值即可，时间复杂度 O(1)；
- LinkedList 需要先遍历找到对应节点，再修改 item 值，时间复杂度 O(n)。
ArrayList 修改源码：
public E set(int index, E element) {
Objects.checkIndex(index, size);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
LinkedList 修改源码：
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
结论：修改操作 ArrayList 性能远优于 LinkedList。
内存占用：ArrayList 更紧凑，LinkedList 节点开销大
内存占用也是选型的重要参考，尤其是在存储大量数据时。
ArrayList：连续内存，浪费可控
ArrayList 的内存开销主要是数组本身的占用 + 少量扩容预留空间。数组是连续存储的，没有额外指针开销，内存利用率高。即使扩容时会预留一些空间（默认扩容为原容量的 1.5 倍），但这个浪费是可控的。
LinkedList：每个节点额外存储两个指针
LinkedList 的每个节点都要存储 prev 和 next 两个指针，对于存储大量小对象（如 Integer、Short 等）的场景，指针的内存开销甚至会超过数据本身。例如存储 1000 个 Integer 对象，ArrayList 仅需存储 1000 个对象引用，而 LinkedList 需要存储 1000 个对象引用 + 2000 个指针，内存开销明显更大。
选型建议：场景优先，拒绝教条
看完以上分析，我们可以结合实际场景给出选型建议：
优先选择 ArrayList 的场景
- 频繁进行随机访问（get/set 操作）；
- 数据量较大，对内存占用敏感；
- 元素主要在尾部新增/删除，或新增删除操作较少；
- 需要与数组进行频繁转换（ArrayList 的
toArray()方法效率很高）。
优先选择 LinkedList 的场景
- 频繁在列表头部或中间进行新增/删除操作；
- 不需要随机访问，仅需按顺序遍历（迭代器遍历两者性能相近）；
- 数据量较小，且需要频繁调整元素位置（如队列、栈场景，LinkedList 可直接实现 Deque 接口）。
总结：底层结构决定性能上限
ArrayList 和 LinkedList 的性能差异，本质是数组和双向链表两种数据结构的特性差异。数组的连续存储带来了高效的随机访问，但也有扩容和元素移动的开销；链表的分散存储让增删操作更灵活，但随机访问效率低下，且内存开销更大。
在实际开发中，不要迷信'ArrayList 比 LinkedList 快'的教条，而是要结合具体场景的核心操作（是随机访问多还是增删多）、数据量大小等因素综合判断。希望本文的源码分析能帮你打破认知误区，在 Java 集合选型上做到胸有成竹。