ArrayList vs LinkedList 终极对决：从源码到 CPU 缓存，一篇彻底搞懂 List 性能调优

别再背八股了从动态扩容到双向链表从时间复杂度到内存占用这篇带你真正理解该用谁在 Java 集合框架中List接口的两个最常用实现——ArrayList和LinkedList——是面试中出场率最高的“兄弟阋墙”问题。很多开发者只知道“ArrayList 查询快、增删慢LinkedList 增删快、查询慢”但一旦被追问“为什么”“具体快多少”“内存占用差几倍”就答不上来了。今天这篇文章我们从底层数据结构源码级、时间复杂度精确 Big-O、内存占用字节级、CPU 缓存行影响、遍历陷阱和最佳实践六个维度彻底把这对“冤家”讲透。一、先上结论一张表看懂核心区别对比维度ArrayListLinkedList底层数据结构动态数组Object[]双向链表Node节点随机访问get(int index)O(1)数组下标直接寻址O(n)从 head/tail 遍历末尾插入add(E e)O(1)摊销偶尔扩容O(1)直接 linkLast中间插入add(int index, E e)O(n)元素整体后移O(n)遍历找节点 O(1) 插入中间删除remove(int index)O(n)元素整体前移O(n)遍历找节点 O(1) 删除内存占用低仅存储元素引用 少量数组头部开销高每个节点额外存储 2 个指针prev/next 对象头实现接口List、RandomAccess、Cloneable、SerializableList、Deque、Cloneable、SerializableCPU 缓存友好性✅高度友好连续内存❌不友好节点分散在堆中线程安全❌ 不安全可用Vector或Collections.synchronizedList❌ 不安全黄金选型原则绝大多数场景查多改少直接用ArrayList90% 以上的情况适用。只在一种场景用LinkedList频繁在头部addFirst或中间用迭代器插入/删除且不需要随机访问。如果数据量极大且对性能敏感考虑ArrayDeque替代LinkedList做队列/栈或CopyOnWriteArrayList读多写少并发场景。二、底层数据结构与源码深度剖析1.ArrayList动态数组源码核心JDK 8/11publicclassArrayListEextendsAbstractListEimplementsListE,RandomAccess,Cloneable,java.io.Serializable{// 默认初始容量privatestaticfinalintDEFAULT_CAPACITY10;// 底层存储数组transient 表示不自动序列化transientObject[]elementData;// 实际元素个数privateintsize;// 核心方法get(int index) —— O(1)publicEget(intindex){rangeCheck(index);returnelementData(index);// 直接数组下标访问}// 核心方法add(E e) —— 均摊 O(1)publicbooleanadd(Ee){ensureCapacityInternal(size1);// 检查并扩容elementData[size]e;// 末尾赋值returntrue;}}扩容机制重点// 当容量不足时新容量 oldCapacity (oldCapacity 1)即 1.5 倍intnewCapacityoldCapacity(oldCapacity1);elementDataArrays.copyOf(elementData,newCapacity);// 复制数组开销大默认初始容量10。扩容因子1.5 倍JDK 6 是 1.5 倍 1现在基本都是 1.5 倍。扩容触发Arrays.copyOf()将原数组全部复制到新数组时间复杂度 O(n)。2.LinkedList双向链表源码核心JDK 8/11publicclassLinkedListEextendsAbstractSequentialListEimplementsListE,DequeE,Cloneable,java.io.Serializable{// 节点个数transientintsize0;// 头节点transientNodeEfirst;// 尾节点transientNodeElast;// 内部节点类静态内部类privatestaticclassNodeE{Eitem;NodeEnext;NodeEprev;Node(NodeEprev,Eelement,NodeEnext){this.itemelement;this.nextnext;this.prevprev;}}// 核心方法get(int index) —— O(n)publicEget(intindex){checkElementIndex(index);returnnode(index).item;}// 根据索引查找节点从头部或尾部开始遍历取离得近的一端NodeEnode(intindex){if(index(size1)){NodeExfirst;for(inti0;iindex;i)xx.next;returnx;}else{NodeExlast;for(intisize-1;iindex;i--)xx.prev;returnx;}}// 核心方法add(E e) —— O(1)publicbooleanadd(Ee){linkLast(e);returntrue;}voidlinkLast(Ee){finalNodeEllast;finalNodeEnewNodenewNode(l,e,null);lastnewNode;if(lnull)firstnewNode;elsel.nextnewNode;size;modCount;}}关键点LinkedList的get(index)会从离头/尾更近的一端遍历但时间复杂度依然是 O(n)只是常数项减半。三、时间复杂度精确对比面试必背操作ArrayListLinkedListget(int index)O(1)O(n)从 head/tail 遍历set(int index, E e)O(1)O(n)先遍历找到节点add(E e)末尾O(1)摊销偶尔扩容 O(n)O(1)add(int index, E e)中间O(n)后移元素O(n)找节点O(1)插入remove(int index)O(n)前移元素O(n)找节点O(1)删除remove(Object o)O(n)查找 前移O(n)查找 删除addFirst(E e)O(n)整体后移O(1)头插removeFirst()O(n)整体前移O(1)头删真相暴击很多人误以为“LinkedList 插入比 ArrayList 快”但这只发生在头部插入或已经持有节点引用如迭代器时。如果你在中间位置插入LinkedList 要先花O(n)遍历找到那个位置然后才做O(1)的指针修改。总耗时依然是 O(n)而且由于遍历时指针跳跃CPU 缓存不友好实际可能比 ArrayList 还慢四、内存占用深度对比字节级呼应 GC 篇1.ArrayList内存占用对象头12-16 字节elementData数组引用4/8 字节size4 字节 对齐填充。elementData数组连续内存每个槽位存一个引用4/8 字节。总内存≈对象头 数组引用 容量 × 引用大小 数组对象头。举例存储 10 万个String引用压缩指针开启引用 4 字节数组占用 ≈100000 × 4 400KB加上数组对象头约 16 字节几乎可以忽略。总内存 ≈400KB 少量对象头。2.LinkedList内存占用每个元素都会被包装成一个Node对象。每个Node对象包含对象头12-16 字节 item4/8 字节 next4/8 字节 prev4/8 字节 对齐填充。在 64 位 JVM 开启压缩指针时一个Node对象约24 字节。举例存储 10 万个String引用压缩指针开启每个节点占24 字节对象头 12B 3 个引用 12B 对齐 0B。节点总内存 ≈100000 × 24 2.4MB。ArrayList仅 400KB vsLinkedList2.4MB内存占用差 6 倍3. 内存布局对 CPU 缓存的影响极客加分项ArrayListelementData是一块连续内存。CPU 加载数据时会一次性把整条缓存行Cache Line64 字节读入。遍历ArrayList时缓存命中率极高。LinkedList节点在堆中随机分配不连续。遍历时每次都要从内存中加载不同地址的节点缓存命中率极低Cache Miss 严重。这也是为什么实际测试中LinkedList的遍历速度远慢于理论值。五、遍历方式与性能陷阱1. 遍历ArrayList随机访问快ListIntegerlistnewArrayList(1000000);// ✅ 方式1普通 for 循环最快利用随机访问for(inti0;ilist.size();i){Integernumlist.get(i);}// ✅ 方式2增强 for / 迭代器也很快但略慢于普通 forfor(Integernum:list){// ...}2. 遍历LinkedList千万不能用get(index)ListIntegerlistnewLinkedList();// ❌ 错误O(n²) 时间复杂度每个 get 都从头开始遍历for(inti0;ilist.size();i){Integernumlist.get(i);// 总时间复杂度 O(n²)}// ✅ 正确使用增强 for / 迭代器for(Integernum:list){// 内部使用迭代器O(n)// ...}3. 遍历时删除迭代器 vs for 循环ListStringlistnewArrayList();list.add(A);list.add(B);list.add(C);// ❌ 错误ConcurrentModificationExceptionfor(Strings:list){if(s.equals(B)){list.remove(s);// 修改了 modCount迭代器检测到抛出异常}}// ✅ 正确使用迭代器的 remove()IteratorStringitlist.iterator();while(it.hasNext()){if(it.next().equals(B)){it.remove();// 安全删除}}// ✅ 正确Java 8removeIflist.removeIf(s-s.equals(B));六、生产场景选型决策树需要 List 存储数据 │ ├─ 是否需要频繁随机访问get/set │ └─ 是 → 无脑选 ArrayList │ ├─ 是否需要频繁在头部插入/删除 │ ├─ 是 → 考虑 ArrayDeque更快更省内存或 LinkedList │ └─ 否 → 继续往下看 │ ├─ 是否需要在中间位置频繁插入/删除 │ ├─ 是且已经持有迭代器/节点引用 → LinkedList 或 LinkedHashMap │ └─ 否或需遍历找位置→ ArrayList遍历找位置已经是 O(n)数组移动也是 O(n)ArrayList 还省内存 │ ├─ 数据量极小 100 个元素 │ └─ 是 → 两者差别可忽略随便选 │ └─ 默认推荐90% 的场景→ ArrayList具体场景举例场景推荐理由查询接口返回列表只读ArrayList随机访问快内存小数据库批量查询结果ArrayList按索引遍历快消息队列FIFOArrayDeque比LinkedList快不需要随机访问只需头尾操作栈LIFOArrayDeque比LinkedList更快更省内存LRU 缓存需频繁头删/尾插LinkedList或LinkedHashMap需要快速头/尾操作并发读多写少CopyOnWriteArrayList读无锁写复制七、思考题检验是否真的懂了// 问题 1下面两段代码哪个性能更好为什么// 代码 A使用 ArrayListListIntegerlistAnewArrayList();for(inti0;i100000;i){listA.add(0,i);// 每次都插在头部}// 代码 B使用 LinkedListListIntegerlistBnewLinkedList();for(inti0;i100000;i){listB.add(0,i);// 每次都插在头部}// 问题 2下面代码的问题是什么生产环境真实事故ListIntegerlistnewLinkedList();for(inti0;i100000;i){list.add(i);}// 使用普通 for 循环遍历for(inti0;ilist.size();i){intvaluelist.get(i);// 处理 value}// 问题 3ArrayList 的默认初始容量是 10。如果已知要存储 100 万个元素// 直接 new ArrayList() 和 new ArrayList(1000000) 有什么区别答案选中下方空白区域查看代码 BLinkedList性能远好于 A。头部插入add(0, i)ArrayList每次都需要将整个数组元素后移O(n)总复杂度 O(n²)LinkedList只需修改指针O(1)总复杂度 O(n)。时间复杂度 O(n²)list.get(i)在LinkedList中是从头开始遍历总耗时 100000 * 平均遍历长度约 50000≈ 50 亿次操作。如果是生产环境接口会直接超时。new ArrayList()默认容量 10在插入 100 万元素时会触发约 17 次扩容10 → 15 → 22 → 33 → …每次扩容都涉及Arrays.copyOf()复制整个数组总复制量约为200 万次元素移动。new ArrayList(1000000)直接预分配足够容量0 次扩容性能提升巨大。总结终极速查表知识点一句话记忆ArrayList底层动态数组随机访问 O(1)内存连续LinkedList底层双向链表头部/尾部操作 O(1)内存碎片化扩容ArrayList1.5 倍扩容复制数组开销大节点内存LinkedList每个节点多 2 个指针内存占用是ArrayList的 3-6 倍遍历陷阱不要在LinkedList中用get(index)遍历复杂度 O(n²)默认选择90% 场景用ArrayList唯一优势场景频繁头插/头删或通过迭代器在中间插入/删除 互动话题你有没有在线上环境因为LinkedList的get(index)导致接口超时的“血泪史”或者把ArrayList用在头插场景导致性能问题的经历欢迎评论区分享如果觉得有收获别忘了点赞、收藏、转发让更多 Javaer 彻底搞懂这两个 List 的区别我们下篇见发布日期2026-08-26