Java面试必问：ArrayList 和 LinkedList 区别：从底层到实战，彻底搞懂

ArrayList 和 LinkedList 区别从底层到实战彻底搞懂面试官“ArrayList 和 LinkedList 有什么区别”你“ArrayList 底层是动态数组查询快、增删慢LinkedList 底层是双向链表增删快、查询慢。”面试官“那如果我在链表中间插入元素真的是 O(1) 吗”你“……”很多人的回答止步于表面但面试官追问的往往是细节。本文从源码到内存、从理论到陷阱彻底讲透这两个集合的区别。一、一句话对比背诵版维度ArrayListLinkedList底层结构动态数组Object[]双向链表Node 节点查询效率O(1)随机访问快O(n)需遍历增删效率尾部 O(1)中间 O(n)头尾 O(1)中间 O(n)内存占用连续内存有闲置空间分散内存每个节点额外存储前后指针使用场景读多写少写多读少尤其是头尾操作二、底层结构详解1. ArrayList动态数组// JDK 8 源码简化publicclassArrayListE{transientObject[]elementData;// 存储元素的数组privateintsize;// 实际元素个数}初始容量为 10懒加载add 时才创建扩容newCapacity oldCapacity (oldCapacity 1)→ 1.5 倍扩容元素在内存中连续存放通过下标访问极快。2. LinkedList双向链表// JDK 8 源码简化publicclassLinkedListE{transientNodeEfirst;// 头节点transientNodeElast;// 尾节点privatestaticclassNodeE{Eitem;NodeEnext;NodeEprev;}}每个节点独立存在通过 prev/next 指针连接。没有扩容概念随增随加。三、增删效率的真实面目很多人背“LinkedList 增删快 O(1)”这是不严谨的。1. 头尾操作确实是 O(1)linkedList.addFirst(e);// 直接修改 first 指针linkedList.addLast(e);// 直接修改 last 指针linkedList.removeFirst();linkedList.removeLast();2. 中间插入O(n) 定位 O(1) 改指针// 在 index 处插入元素linkedList.add(index,element);源码中会先通过node(index)遍历到该位置NodeEnode(intindex){if(index(size1)){NodeExfirst;for(inti0;iindex;i)xx.next;returnx;}else{NodeExlast;for(intisize-1;iindex;i--)xx.prev;returnx;}}遍历耗时 O(n)真正改指针只是 O(1)。所以中间增删总复杂度也是 O(n)和 ArrayList 的 O(n) 没有量级差别只是常数不同ArrayList 需要复制元素LinkedList 只需改指针。结论只有头尾增删LinkedList 才有真正的 O(1) 优势。四、查询效率ArrayList 完胜arrayList.get(10000);// 直接返回 elementData[10000] → O(1)linkedList.get(10000);// 从 first 或 last 遍历 10000 步 → O(n)所以随机读取场景ArrayList 碾压 LinkedList。五、内存占用对比ArrayList数组本身是连续内存但可能预留了闲置空间例如 size10capacity15。每个元素只是一个引用4 或 8 字节无额外指针。LinkedList每个节点前驱指针 后继指针 元素引用 ≈ 24 字节额外开销64位 JVM 默认压缩指针下。节点在内存中分散CPU 缓存不友好遍历时 cache miss 率高。结论LinkedList 内存占用明显高于 ArrayList。六、使用场景与误区正确场景场景推荐频繁随机访问读多写少ArrayList频繁头尾增删如队列、栈LinkedList或 ArrayDeque 更优频繁中间增删两者都是 O(n)但 LinkedList 常数更小可酌情使用常见误区“LinkedList 增删总是比 ArrayList 快”→ 错。中间增删都需要先定位ArrayList 在尾部增删甚至更快。“LinkedList 实现了 Queue所以做队列最好”→ 不完全是。ArrayDeque在大多数场景下比 LinkedList 更快、更省内存。“ArrayList 扩容很慢所以能用 LinkedList 就用”→ 过度担忧。扩容均摊后仍是 O(1)且现代 JVM 内存分配很快。七、实战建议1. 写代码时如何选择// 已知元素数量或者以随机访问为主ListIntegerlistnewArrayList();// 需要频繁在头尾操作且元素数量很大QueueIntegerqueuenewLinkedList();// 或者 ArrayDeque// 不确定先用 ArrayList遇到性能瓶颈再分析2. 性能测试小例子// 头部插入 10 万次longstartSystem.currentTimeMillis();ListIntegerlistnewArrayList();for(inti0;i100000;i){list.add(0,i);// 每次移动全部元素}System.out.println(ArrayList head insert: (System.currentTimeMillis()-start)ms);// LinkedList 头部插入listnewLinkedList();startSystem.currentTimeMillis();for(inti0;i100000;i){list.add(0,i);// 只改指针}System.out.println(LinkedList head insert: (System.currentTimeMillis()-start)ms);结果典型值ArrayList~2000msLinkedList~5ms八、总结一张表特性ArrayListLinkedList底层数组双向链表随机访问 get/setO(1)O(n)尾部增删O(1) 均摊O(1)头部增删O(n)O(1)中间增删O(n) 移动O(n) 改指针内存连续性连续分散额外内存少量预留空间较大节点指针迭代性能好局部性差指针跳跃终极建议默认用ArrayList。只有确定需要大量头尾操作且不需要随机访问时再考虑LinkedList或更优的ArrayDeque。永远不要为了“听说增删快”而在中间插入场景盲目使用 LinkedList。希望这篇文章能帮你彻底掌握 ArrayList 与 LinkedList 的区别面试时从容应对追问。