Javajava算法
从源码看 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