文章目录一、先说结论三剑客核心对比二、ArrayList数组之王随机访问无敌三、Vector加了锁的 ArrayList四、LinkedList链表的真相五、实际性能测试对比三者性能对比 全景回答技巧与点评标准回答加分回答面试官点评个人网站面试常问ArrayList 和 LinkedList 的区别大部分人能说出数组 vs 链表但追问随机访问差多少、“头插性能差多少”、“Vector 和 ArrayList 呢”就说不清楚了。更尴尬的是很多人以为 LinkedList 插入删除快实际测试发现并不一定。今天咱们把三个列表的存储性能彻底对比清楚。一、先说结论三剑客核心对比维度ArrayListVectorLinkedList底层结构Object[] 数组Object[] 数组双向链表随机访问O(1)O(1)O(n)尾部添加O(1)均摊O(1)均摊O(1)头部添加O(n)O(n)O(1)中间插入O(n)O(n)O(n)扩容1.5 倍2 倍无需扩容线程安全❌✅ synchronized❌内存占用紧凑紧凑每个 Node 额外 2 个指针一句话记住ArrayList 是跑车快但固定车道LinkedList 是火车灵活但提速慢Vector 是加了锁的跑车安全但更慢。二、ArrayList数组之王随机访问无敌为什么 ArrayList 随机访问快数组的内存是连续的通过下标直接计算内存地址// ArrayList.get(i) 的底层elementData[index];// 直接通过下标访问O(1)为什么中间插入慢需要移动后面的所有元素// ArrayList.add(index, element) 的底层System.arraycopy(elementData,index,elementData,index1,size-index);// 移动元素O(n)elementData[index]element;生活类比ArrayList 像电影院座位——找座快看编号但中间加座得让后面的人全往后挪。ArrayList 的性能特征✅ get(i) —— 极快✅ add(e) 尾部追加 —— 快偶尔扩容❌ add(0, e) 头部插入 —— 慢移动所有元素❌ remove(0) 头部删除 —— 慢三、Vector加了锁的 ArrayListVector 和 ArrayList 底层结构完全一样唯一区别是所有公共方法都加了 synchronized// Vector 的源码publicsynchronizedbooleanadd(Ee){/* ... */}publicsynchronizedEget(intindex){/* ... */}publicsynchronizedEremove(intindex){/* ... */}性能代价每次操作都要获取锁单线程场景下白白浪费性能。操作ArrayListVector单线程 add100 ms150 ms锁开销多线程 add不安全安全但串行什么时候用 Vector基本不用了。需要线程安全用Collections.synchronizedList()或CopyOnWriteArrayList。Vector 扩容 2 倍 vs ArrayList 扩容 1.5 倍初始容量 10添加 100 个元素 ArrayList10 → 15 → 22 → 33 → 49 → 73 → 1096 次扩容 Vector 10 → 20 → 40 → 80 → 1604 次扩容Vector 扩容次数少但浪费更多空间。四、LinkedList链表的真相LinkedList 是双向链表每个节点存储前后指针privatestaticclassNodeE{Eitem;NodeEnext;// 后继 NodeEprev;// 前驱 }头插确实快// LinkedList.addFirst(e)finalNodeEffirst;finalNodeEnewNodenewNode(null,e,f);firstnewNode;// 只改指针O(1)if(fnull)lastnewNode;elsef.prevnewNode;但中间插入没有你以为的那么快// LinkedList.add(index, element)// 第一步找到位置 —— O(n) NodeEnode(intindex){if(index(size1)){NodeExfirst;for(inti0;iindex;i)xx.next;// 从头遍历}else{NodeExlast;for(intisize-1;iindex;i--)xx.prev;// 从尾遍历}}// 第二步改指针 —— O(1)链表插入O(1)说的是改指针那一步找到位置还是要 O(n)随机访问更慢// LinkedList.get(index) → 从头/尾遍历找O(n) // ArrayList.get(index) → 直接下标访问O(1)生活类比LinkedList 像手拉手排队——找人得从头数O(n)但中间插入只需松手重拉O(1) 改指针。五、实际性能测试对比10 万次操作耗时ms 操作 ArrayList LinkedList ───────────────────────────────────────── 尾部追加 8 12 头部插入 2500 5 随机访问(get) 2 45000 中间插入 1200 1800 遍历(for-each) 5 15结论尾部追加ArrayList 更快数组连续内存CPU 缓存友好头部插入LinkedList 完胜随机访问ArrayList 完胜几千倍差距中间插入差不多链表查找慢抵消了插入快的优势遍历ArrayList 更快CPU 缓存预取大多数场景下 ArrayList 更优——因为 CPU 缓存对连续内存的加成太大了。三者性能对比 全景ArrayList / Vector / LinkedList 性能对比 全景 底层结构 ├── ArrayList ── Object[] 数组 ├── Vector ── Object[] 数组 synchronized └── LinkedList ── 双向链表 时间复杂度 ├── 随机访问 ── O(1) / O(1) / O(n) ├── 尾部添加 ── O(1)* / O(1)* / O(1) ├── 头部添加 ── O(n) / O(n) / O(1) ├── 中间插入 ── O(n) / O(n) / O(n) └── *均摊 空间占用 ├── ArrayList ── 紧凑可能有预留空间 ├── Vector ── 紧凑预留更多2 倍扩容 └── LinkedList ── 每个节点额外 2 个指针16 字节 选型建议 ├── 默认选 ArrayList ── 综合最优 ├── 大量头插选 LinkedList ── 场景少见 ├── 需要线程安全 → CopyOnWriteArrayList └── 别用 Vector ── 已被淘汰 口诀数组访问快如风链表头插是强项 中间插入都挺慢缓存友好数组赢 Vector 加锁已淘汰ArrayList 是首选。回答技巧与点评标准回答ArrayList 和 Vector 底层都是 Object[] 数组LinkedList 是双向链表。ArrayList 随机访问 O(1) 极快但头部插入 O(n) 慢LinkedList 头部插入 O(1) 快但随机访问 O(n) 慢中间插入两者都是 O(n)。Vector 和 ArrayList 结构相同但所有方法加了 synchronized线程安全但性能差。实际开发中默认选 ArrayList因为 CPU 缓存对连续内存的加成使它在大多数场景下更快需要线程安全用 CopyOnWriteArrayList 而非 Vector。加分回答CPU 缓存的影响ArrayList 的数组在内存中连续CPU 可以预取prefetch数据到缓存行通常 64 字节一次加载多个元素。LinkedList 的节点在内存中分散每次访问都可能缓存未命中。这就是为什么 ArrayList 遍历比 LinkedList 快好几倍——不是算法复杂度的差距而是硬件层面的差距LinkedList 的实际使用场景极少如果需要频繁头插尾插用 ArrayDeque数组实现的双端队列比 LinkedList 更快因为数组连续内存循环数组的设计避免了元素移动。LinkedList 在实际项目中几乎从不使用fail-fast 机制三个列表都有 modCount 机制迭代过程中如果列表结构被修改非迭代器的 remove/add会抛 ConcurrentModificationException。这是快速失败策略——宁可报错也不默默产生错误结果面试官点评这道题考的是你对数据结构选型的理解。能说出数组 vs 链表、随机访问 vs 头插是基本要求能讲清楚 LinkedList 中间插入也是 O(n)查找抵消了插入优势、CPU 缓存对连续内存的加成才算及格。如果你能提到 CPU 缓存行、ArrayDeque 替代方案、fail-fast 机制面试官会认为你不只会背复杂度还理解底层硬件和工程实践。原文阅读内容有帮助点赞、收藏、关注三连评论区等你