从源码看 ArrayList 与 LinkedList 的性能差异
本文通过源码分析对比了 Java 中 ArrayList 与 LinkedList 的底层结构、核心操作性能及内存占用。ArrayList 基于动态数组,随机访问快但增删需移动元素;LinkedList 基于双向链表,增删快但随机访问慢且内存开销大。建议根据场景选择:频繁随机访问或尾部操作选 ArrayList,频繁头部/中间增删选 LinkedList。

本文通过源码分析对比了 Java 中 ArrayList 与 LinkedList 的底层结构、核心操作性能及内存占用。ArrayList 基于动态数组,随机访问快但增删需移动元素;LinkedList 基于双向链表,增删快但随机访问慢且内存开销大。建议根据场景选择:频繁随机访问或尾部操作选 ArrayList,频繁头部/中间增删选 LinkedList。

在 Java 集合框架中,ArrayList 和 LinkedList 作为 List 接口的两个典型实现,经常被拿来对比。很多开发者仅停留在'ArrayList 基于数组、LinkedList 基于链表'的表层认知,却忽略了底层源码设计对性能的决定性影响。本文将从源码出发,从初始化、增删改查、内存占用等多维度拆解两者的性能差异,帮你在实际开发中精准选型。
要理解性能差异,首先得从两者的底层数据结构说起,这是一切性能表现的根源。
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 的底层是双向链表结构,每个节点用 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 的随机访问:直接通过数组下标定位,源码非常简洁:
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。
新增操作的性能差异,主要体现在是否需要移动元素和扩容成本。
ArrayList 新增元素:
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;
}
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 新增元素:
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++;
}
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++;
}
结论:
删除操作的性能逻辑和新增类似,核心差异还是元素移动 vs 指针修改。
ArrayList 删除元素:
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 修改源码:
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 的内存开销主要是数组本身的占用 + 少量扩容预留空间。数组是连续存储的,没有额外指针开销,内存利用率高。即使扩容时会预留一些空间(默认扩容为原容量的 1.5 倍),但这个浪费是可控的。
LinkedList 的每个节点都要存储 prev 和 next 两个指针,对于存储大量小对象(如 Integer、Short 等)的场景,指针的内存开销甚至会超过数据本身。例如存储 1000 个 Integer 对象,ArrayList 仅需存储 1000 个对象引用,而 LinkedList 需要存储 1000 个对象引用 + 2000 个指针,内存开销明显更大。
看完以上分析,我们可以结合实际场景给出选型建议:
toArray() 方法效率很高)。ArrayList 和 LinkedList 的性能差异,本质是数组和双向链表两种数据结构的特性差异。数组的连续存储带来了高效的随机访问,但也有扩容和元素移动的开销;链表的分散存储让增删操作更灵活,但随机访问效率低下,且内存开销更大。
在实际开发中,不要迷信'ArrayList 比 LinkedList 快'的教条,而是要结合具体场景的核心操作(是随机访问多还是增删多)、数据量大小等因素综合判断。希望本文的源码分析能帮你打破认知误区,在 Java 集合选型上做到胸有成竹。

微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具,Keycode 信息在线工具,online
JavaScript 字符串转义/反转义;Java 风格 \uXXXX(Native2Ascii)编码与解码。 在线工具,Escape 与 Native 编解码在线工具,online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具,JavaScript / HTML 格式化在线工具,online
Terser 压缩、变量名混淆,或 javascript-obfuscator 高强度混淆(体积会增大)。 在线工具,JavaScript 压缩与混淆在线工具,online
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online