从源码看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 NodeE { E item; NodeE next; NodeE prev; Node(NodeE prev, E element, NodeE next) { this.item element; this.next next; this.prev prev; } }同时维护了首尾节点指针Java复制transient NodeE first; transient NodeE 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; } NodeE node(int index) { // assert isElementIndex(index); if (index (size 1)) { NodeE x first; for (int i 0; i index; i) x x.next; return x; } else { NodeE 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 NodeE l last; final NodeE 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, NodeE succ) { // assert succ ! null; final NodeE pred succ.prev; final NodeE 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(NodeE x) { // assert x ! null; final E element x.item; final NodeE next x.next; final NodeE 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); NodeE x node(index); E oldVal x.item; x.item element; return oldVal; }结论修改操作ArrayList性能远优于LinkedList。 内存占用ArrayList更紧凑LinkedList节点开销大内存占用也是选型的重要参考尤其是在存储大量数据时。ArrayList连续内存浪费可控插入广告各行各业学习千款源码就上svipm.com.cnArrayList的内存开销主要是数组本身的占用少量扩容预留空间。数组是连续存储的没有额外指针开销内存利用率高。即使扩容时会预留一些空间默认扩容为原容量的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集合选型上做到胸有成竹。