从源码看ArrayList与LinkedList的性能差异
从源码深挖ArrayList与LinkedList的性能差异
在Java集合框架中，ArrayList和LinkedList作为List接口的两个典型实现，经常被拿来对比。很多开发者仅停留在“ArrayList基于数组、LinkedList基于链表”的表层认知，却忽略了底层源码设计对性能的决定性影响。本文将从源码出发，从初始化、增删改查、内存占用等多维度拆解两者的性能差异，帮你在实际开发中精准选型。
📦 底层结构：数组 vs 双向链表
要理解性能差异，首先得从两者的底层数据结构说起，这是一切性能表现的根源。
ArrayList：动态扩容的Object数组
ArrayList的核心是一个transient Object[] elementData数组，Java源码中定义如下：
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类封装：
Java
复制
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; } }
同时维护了首尾节点指针：
Java
复制
transient Node<E> first; transient Node<E> last;
链表的节点在内存中分散存储，通过指针关联，插入删除仅需改变指针指向，但随机访问需要遍历链表，时间复杂度为O(n)。
⚡ 核心操作性能对比
接下来我们从源码角度，逐一分析增、删、改、查四大核心操作的性能差异。
🔍 查找：ArrayList完胜，O(1) vs O(n)
ArrayList的随机访问： 直接通过数组下标定位，源码非常简洁：
Java
复制
public E get(int index) { Objects.checkIndex(index, size); return elementData(index); } E elementData(int index) { return (E) elementData[index]; }
只要下标合法，就能在常数时间内获取元素，这是数组天生的优势。
LinkedList的随机访问： 需要从首节点或尾节点开始遍历，源码如下：
Java
复制
public E get(int index) { checkElementIndex(index); return node(index).item; } Node<E> node(int index) { // assert isElementIndex(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)。
Java
复制
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)，源码如下：
Java
复制
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)
Java
复制
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)时间）
Java
复制
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) { // assert succ != null; 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)，源码如下：
Java
复制
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)时间）：
Java
复制
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } E unlink(Node<E> x) { // assert x != null; 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修改源码：
Java
复制
public E set(int index, E element) { Objects.checkIndex(index, size); E oldValue = elementData(index); elementData[index] = element; return oldValue; }
LinkedList修改源码：
Java
复制
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：连续内存，浪费可控
插入广告：各行各业学习千款源码就上：svipm.com.cn
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集合选型上做到胸有成竹。
