文章目录Java集合框架ArrayList vs LinkedList 核心区别与扩容机制一、在Java集合框架中的定位二、底层数据结构对比三、核心操作性能对比3.1 时间复杂度全景3.2 实际性能差异超越时间复杂度四、ArrayList扩容机制详解JDK8-JDK214.1 核心概念4.2 初始化策略4.3 JDK8扩容核心源码4.4 JDK17扩容优化4.5 扩容过程详解4.6 扩容性能影响与优化五、LinkedList无扩容机制六、内存占用对比七、线程安全性八、迭代器特性与fail-fast机制8.1 迭代器类型8.2 fail-fast机制九、适用场景对比9.1 优先使用ArrayList的场景9.2 优先使用LinkedList的场景9.3 重要误区澄清十、常见面试考点ArrayList vs LinkedList 面试标准答案可直接背诵 经典代码分析题一、面试标准答案按提问频率排序1. 核心定位与底层数据结构必问第一题2. 核心操作时间复杂度对比必问第二题3. ArrayList 扩容机制高频重点100% 会考4. 内存占用与 CPU 缓存差异5. 线程安全性与迭代器特性6. 适用场景与常见误区面试压轴题二、经典代码分析题含解析题目1ArrayList 扩容次数计算题目2ConcurrentModificationException 产生原因题目3LinkedList 随机访问性能陷阱Java集合框架ArrayList vs LinkedList 核心区别与扩容机制一、在Java集合框架中的定位ArrayListjava.util.ArrayList继承自AbstractList实现了List、RandomAccess、Cloneable、Serializable接口是基于动态数组的List实现LinkedListjava.util.LinkedList继承自AbstractSequentialList实现了List、Deque、Cloneable、Serializable接口是基于双向链表的List实现同时具备队列/双端队列的特性二、底层数据结构对比特性ArrayListLinkedList核心结构动态Object数组连续内存块双向链表离散节点核心成员变量transient Object[] elementData存储元素int size实际元素个数transient NodeE first头节点transient NodeE last尾节点int size实际元素个数节点结构无单独节点直接存储元素引用private static class NodeE { E item; NodeE next; NodeE prev; }内存连续性物理内存连续逻辑连续物理内存离散随机访问支持实现RandomAccess接口支持O(1)随机访问不支持必须遍历链表三、核心操作性能对比3.1 时间复杂度全景操作ArrayList均摊LinkedList最坏/最优关键说明get(int index)O(1)O(n)ArrayList直接通过索引计算内存地址LinkedList需从近的一端遍历add(E e)尾部O(1)均摊O(1)ArrayList扩容时为O(n)但1.5倍扩容因子使摊还代价极低add(int index, E e)O(n)O(n)ArrayList需移动index后所有元素LinkedList需O(n)定位O(1)修改指针addFirst(E e)头部O(n)O(1)ArrayList需移动全部元素LinkedList仅修改头节点指针remove(int index)O(n)O(n)同插入逻辑removeFirst()O(n)O(1)同头部插入set(int index, E e)O(1)O(n)ArrayList直接替换指定位置元素contains(Object o)O(n)O(n)均需遍历查找iterator().next()O(1)O(1)迭代器均维护当前位置指针3.2 实际性能差异超越时间复杂度CPU缓存友好性ArrayList元素连续存储CPU缓存行通常64字节可预加载多个元素缓存命中率极高LinkedList节点分散每次节点跳转都可能触发缓存未命中L3缓存缺失率高出3-5倍内存分配开销LinkedList每次插入都需创建新的Node对象涉及对象头、指针等额外开销ArrayList仅在扩容时分配大数组内存分配次数少扩容开销ArrayList扩容时需复制整个数组大数组扩容可能引发GC停顿LinkedList无扩容概念节点按需创建四、ArrayList扩容机制详解JDK8-JDK214.1 核心概念容量(Capacity)底层数组elementData的长度大小(Size)实际存储的元素个数扩容触发条件当size 1 elementData.length时触发扩容4.2 初始化策略构造方法初始容量首次扩容行为new ArrayList()0空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA第一次添加元素时扩容至默认容量10new ArrayList(int initialCapacity)指定的initialCapacity当元素个数超过指定容量时按1.5倍扩容new ArrayList(Collection? extends E c)集合c的大小当元素个数超过该大小时按1.5倍扩容4.3 JDK8扩容核心源码privatevoidgrow(intminCapacity){// 旧容量intoldCapacityelementData.length;// 新容量 旧容量 旧容量/2右移一位等价于除以2intnewCapacityoldCapacity(oldCapacity1);// 如果新容量仍小于最小需要容量则使用最小需要容量if(newCapacity-minCapacity0)newCapacityminCapacity;// 如果新容量超过最大数组大小则使用hugeCapacity计算if(newCapacity-MAX_ARRAY_SIZE0)newCapacityhugeCapacity(minCapacity);// 复制数组到新容量elementDataArrays.copyOf(elementData,newCapacity);}privatestaticinthugeCapacity(intminCapacity){if(minCapacity0)// 溢出thrownewOutOfMemoryError();return(minCapacityMAX_ARRAY_SIZE)?Integer.MAX_VALUE:MAX_ARRAY_SIZE;}privatestaticfinalintMAX_ARRAY_SIZEInteger.MAX_VALUE-8;4.4 JDK17扩容优化JDK17及后续LTS版本未改变核心1.5倍扩容公式但进行了重要优化引入ArraysSupport.computeGrow()统一处理数组长度计算增强整数溢出防护优化hugeCapacity()逻辑更早抛出OutOfMemoryError而非静默截断底层数组拷贝逻辑优化减少CPU占用对空数组的处理更加精细避免不必要的内存分配4.5 扩容过程详解容量计算优先按1.5倍扩容若仍不满足需求则使用最小需要容量边界检查检查是否超过最大数组大小防止内存溢出数组分配创建新的Object数组大小为计算出的新容量元素复制通过System.arraycopy()native方法将旧数组元素复制到新数组引用更新将elementData引用指向新数组计数器更新modCount用于fail-fast机制4.6 扩容性能影响与优化性能影响扩容本质是O(n)的数组复制操作大数组扩容会导致内存碎片与GC压力频繁分配/丢弃中等大小对象实时性抖动数百MB数组复制可能引发数十毫秒STW缓存局部性破坏新老数组物理地址不连续降低CPU缓存命中率优化实践预估容量创建ArrayList时根据业务峰值设置合理的初始容量批量添加优先使用addAll()方法减少扩容次数手动扩容添加大量元素前调用ensureCapacity(int minCapacity)方法五、LinkedList无扩容机制LinkedList基于双向链表实现不存在扩容概念元素存储在独立的Node节点中节点按需动态创建和销毁每次添加元素只需创建一个新的Node对象并修改前后节点的指针理论上没有容量限制受限于JVM内存内存开销固定每个节点额外占用2个引用prev和next的空间六、内存占用对比集合内存占用特点示例存储1000个Object引用ArrayList连续内存可能浪费尾部空间数组长度15001.5倍扩容后总占用1500 * 4字节引用 6KBLinkedList离散内存每个节点有额外开销节点数1000每个节点对象头(16字节) 3个引用(12字节) 28字节总占用1000 * 28字节 28KB结论在相同元素个数下LinkedList的内存占用通常是ArrayList的4-5倍七、线程安全性ArrayList和LinkedList都是非线程安全的多线程环境下同时进行结构性修改添加、删除元素会导致ConcurrentModificationException并发修改异常数据丢失、数组越界等不可预期的错误线程安全替代方案Collections.synchronizedList(new ArrayList())CopyOnWriteArrayList读多写少场景ConcurrentLinkedDeque并发队列场景八、迭代器特性与fail-fast机制8.1 迭代器类型ArrayList返回Itr迭代器支持快速随机访问LinkedList返回ListItr迭代器只能顺序访问8.2 fail-fast机制两个集合都实现了fail-fast快速失败机制迭代器创建时会记录modCount结构性修改计数器迭代过程中如果modCount发生变化其他线程修改了集合会立即抛出ConcurrentModificationException注意fail-fast是一种尽力而为的机制不能保证一定能检测到所有并发修改九、适用场景对比9.1 优先使用ArrayList的场景频繁随机访问get/set操作多尾部添加/删除操作多对内存占用敏感需要遍历整个集合ArrayList遍历性能远优于LinkedList大多数业务场景90%以上的List使用场景9.2 优先使用LinkedList的场景频繁在头部/尾部进行插入/删除操作如实现栈、队列不需要随机访问元素元素个数不确定且变化频繁9.3 重要误区澄清❌ 误区LinkedList在中间插入/删除比ArrayList快✅ 真相两者中间插入/删除的时间复杂度都是O(n)且由于ArrayList的CPU缓存优势实际性能往往比LinkedList更好❌ 误区LinkedList是队列的最佳实现✅ 真相在并发场景下ArrayDeque作为队列的性能通常优于LinkedList十、常见面试考点ArrayList的默认初始容量是多少扩容倍数是多少ArrayList和LinkedList的底层数据结构分别是什么为什么ArrayList实现了RandomAccess接口而LinkedList没有ArrayList的扩容过程是怎样的ArrayList和LinkedList在什么场景下性能差异最大两个集合都是线程安全的吗如何实现线程安全的Listfail-fast机制的原理是什么为什么说大多数场景下应该优先使用ArrayList而不是LinkedListArrayList vs LinkedList 面试标准答案可直接背诵 经典代码分析题一、面试标准答案按提问频率排序1. 核心定位与底层数据结构必问第一题背诵版ArrayList 继承自 AbstractList实现了 List、RandomAccess 接口底层是动态 Object 数组物理内存连续支持 O(1) 随机访问。LinkedList 继承自 AbstractSequentialList实现了 List、Deque 接口底层是双向链表物理内存离散不支持随机访问同时具备双端队列的特性。2. 核心操作时间复杂度对比必问第二题背诵版操作ArrayListLinkedList关键结论随机访问 get/setO(1)O(n)ArrayList 直接通过索引计算地址LinkedList 需从两端遍历尾部添加 add(E)O(1)均摊O(1)ArrayList 仅扩容时为 O(n)摊还代价极低头部添加/删除O(n)O(1)ArrayList 需移动全部元素LinkedList 仅修改指针中间添加/删除O(n)O(n)两者时间复杂度相同实际 ArrayList 更快迭代器遍历O(1) 每个元素O(1) 每个元素迭代器均维护当前指针性能接近3. ArrayList 扩容机制高频重点100% 会考背诵版分5步初始化策略无参构造初始容量为 0空数组第一次添加元素时扩容至默认容量 10JDK8 优化JDK7 默认初始容量 10有参构造初始容量为指定值集合构造初始容量为传入集合的大小扩容触发条件当size 1 elementData.length数组已满无法容纳新元素时触发扩容。扩容公式新容量 旧容量 旧容量 1即 1.5 倍扩容右移一位等价于除以 2效率更高。边界处理若 1.5 倍容量仍小于所需最小容量则直接使用最小容量若超过最大数组大小Integer.MAX_VALUE - 8则使用 Integer.MAX_VALUE扩容过程通过System.arraycopy()native 方法将旧数组元素复制到新数组更新 elementData 引用。加分项JDK17 优化了整数溢出防护和数组拷贝逻辑未改变核心 1.5 倍扩容公式。4. 内存占用与 CPU 缓存差异背诵版ArrayList连续内存仅浪费尾部未使用的数组空间内存效率高。存储 1000 个引用约占用 6KB。LinkedList每个元素需额外存储 prev 和 next 两个指针以及对象头开销内存占用是 ArrayList 的 4-5 倍。存储 1000 个元素约占用 28KB。CPU 缓存ArrayList 元素连续CPU 缓存行可预加载多个元素缓存命中率极高LinkedList 节点分散每次跳转都可能触发缓存未命中实际性能差距远大于时间复杂度体现的差异。5. 线程安全性与迭代器特性背诵版两者都是非线程安全的多线程结构性修改会导致 ConcurrentModificationException 或数据丢失。线程安全替代方案通用场景Collections.synchronizedList(new ArrayList())读多写少CopyOnWriteArrayList并发队列ConcurrentLinkedDeque都实现了 fail-fast 机制迭代器创建时记录 modCount迭代过程中若 modCount 变化则立即抛出异常这是一种尽力而为的保护机制。6. 适用场景与常见误区面试压轴题背诵版优先使用 ArrayList90% 以上业务场景频繁随机访问get/set 多尾部添加/删除操作多对内存占用敏感需要遍历整个集合仅在以下场景使用 LinkedList频繁在头部/尾部进行插入/删除如实现栈、队列不需要随机访问元素必澄清的两个误区❌ 误区LinkedList 中间插入/删除比 ArrayList 快✅ 真相两者时间复杂度都是 O(n)ArrayList 的数组复制是 native 方法且 CPU 缓存友好实际性能通常比 LinkedList 更好❌ 误区LinkedList 是队列的最佳实现✅ 真相ArrayDeque作为双端队列的性能全面优于 LinkedList是 Java 官方推荐的队列实现二、经典代码分析题含解析题目1ArrayList 扩容次数计算importjava.util.ArrayList;publicclassArrayListGrowTest{publicstaticvoidmain(String[]args){ArrayListIntegerlistnewArrayList();for(inti0;i11;i){list.add(i);}System.out.println(元素个数list.size());// 问此时 list 的底层数组容量是多少共触发了几次扩容}}答案数组容量为 15共触发了 2 次扩容。详细解析无参构造创建 ArrayList初始容量为 0空数组添加第 1 个元素时触发第一次扩容容量变为默认值 10添加第 11 个元素时size 1 11 10触发第二次扩容新容量 10 10 1 15因此最终容量为 15扩容次数为 2 次延伸考点若初始容量为 10添加 11 个元素扩容次数为 1 次优化建议提前预估容量使用new ArrayList(11)可避免所有扩容题目2ConcurrentModificationException 产生原因importjava.util.ArrayList;importjava.util.Iterator;importjava.util.List;publicclassFailFastTest{publicstaticvoidmain(String[]args){ListStringlistnewArrayList();list.add(A);list.add(B);list.add(C);// 方式1for-each 循环删除会抛异常for(Strings:list){if(B.equals(s)){list.remove(s);}}// 方式2迭代器删除不会抛异常// IteratorString it list.iterator();// while (it.hasNext()) {// String s it.next();// if (B.equals(s)) {// it.remove();// }// }System.out.println(list);}}答案方式1 会抛出ConcurrentModificationException方式2 正常执行输出[A, C]。详细解析for-each 循环本质是迭代器遍历迭代器创建时会记录expectedModCount modCount调用list.remove()方法会修改modCount但不会更新迭代器的expectedModCount下一次调用it.next()时会检查modCount expectedModCount不相等则抛出异常调用it.remove()方法会同时更新modCount和expectedModCount因此不会抛异常延伸考点为什么删除倒数第二个元素不会抛异常因为删除后 size 减 1it.hasNext()返回 false不会执行下一次next()检查多线程环境下即使使用迭代器删除也可能抛异常因为其他线程可能修改了 modCount题目3LinkedList 随机访问性能陷阱importjava.util.ArrayList;importjava.util.LinkedList;importjava.util.List;publicclassLinkedListPerformanceTest{publicstaticvoidmain(String[]args){ListIntegerarrayListnewArrayList();ListIntegerlinkedListnewLinkedList();// 初始化 10万个元素for(inti0;i100000;i){arrayList.add(i);linkedList.add(i);}// 测试随机访问性能longstartSystem.currentTimeMillis();for(inti0;i100000;i){arrayList.get(i);}System.out.println(ArrayList 随机访问耗时(System.currentTimeMillis()-start)ms);startSystem.currentTimeMillis();for(inti0;i100000;i){linkedList.get(i);}System.out.println(LinkedList 随机访问耗时(System.currentTimeMillis()-start)ms);}}答案ArrayList 耗时约 1-5msLinkedList 耗时约 5000-10000ms差距上千倍。详细解析ArrayList 的get(i)是 O(1) 操作直接通过索引计算内存地址LinkedList 的get(i)是 O(n) 操作每次都需要从头部或尾部遍历到指定位置上述代码中LinkedList 总共进行了约 50 亿次节点跳转而 ArrayList 仅进行了 10 万次内存访问再加上 CPU 缓存的差异实际性能差距会进一步扩大延伸考点遍历 LinkedList 必须使用迭代器或 for-each 循环时间复杂度为 O(n)若需要频繁随机访问绝对不能使用 LinkedList
【Java基础】集合框架： ArrayList vs LinkedList 核心区别、扩容机制（附《思维导图》+《面试高频考点清单》）
发布时间：2026/5/20 20:07:59
文章目录Java集合框架ArrayList vs LinkedList 核心区别与扩容机制一、在Java集合框架中的定位二、底层数据结构对比三、核心操作性能对比3.1 时间复杂度全景3.2 实际性能差异超越时间复杂度四、ArrayList扩容机制详解JDK8-JDK214.1 核心概念4.2 初始化策略4.3 JDK8扩容核心源码4.4 JDK17扩容优化4.5 扩容过程详解4.6 扩容性能影响与优化五、LinkedList无扩容机制六、内存占用对比七、线程安全性八、迭代器特性与fail-fast机制8.1 迭代器类型8.2 fail-fast机制九、适用场景对比9.1 优先使用ArrayList的场景9.2 优先使用LinkedList的场景9.3 重要误区澄清十、常见面试考点ArrayList vs LinkedList 面试标准答案可直接背诵 经典代码分析题一、面试标准答案按提问频率排序1. 核心定位与底层数据结构必问第一题2. 核心操作时间复杂度对比必问第二题3. ArrayList 扩容机制高频重点100% 会考4. 内存占用与 CPU 缓存差异5. 线程安全性与迭代器特性6. 适用场景与常见误区面试压轴题二、经典代码分析题含解析题目1ArrayList 扩容次数计算题目2ConcurrentModificationException 产生原因题目3LinkedList 随机访问性能陷阱Java集合框架ArrayList vs LinkedList 核心区别与扩容机制一、在Java集合框架中的定位ArrayListjava.util.ArrayList继承自AbstractList实现了List、RandomAccess、Cloneable、Serializable接口是基于动态数组的List实现LinkedListjava.util.LinkedList继承自AbstractSequentialList实现了List、Deque、Cloneable、Serializable接口是基于双向链表的List实现同时具备队列/双端队列的特性二、底层数据结构对比特性ArrayListLinkedList核心结构动态Object数组连续内存块双向链表离散节点核心成员变量transient Object[] elementData存储元素int size实际元素个数transient NodeE first头节点transient NodeE last尾节点int size实际元素个数节点结构无单独节点直接存储元素引用private static class NodeE { E item; NodeE next; NodeE prev; }内存连续性物理内存连续逻辑连续物理内存离散随机访问支持实现RandomAccess接口支持O(1)随机访问不支持必须遍历链表三、核心操作性能对比3.1 时间复杂度全景操作ArrayList均摊LinkedList最坏/最优关键说明get(int index)O(1)O(n)ArrayList直接通过索引计算内存地址LinkedList需从近的一端遍历add(E e)尾部O(1)均摊O(1)ArrayList扩容时为O(n)但1.5倍扩容因子使摊还代价极低add(int index, E e)O(n)O(n)ArrayList需移动index后所有元素LinkedList需O(n)定位O(1)修改指针addFirst(E e)头部O(n)O(1)ArrayList需移动全部元素LinkedList仅修改头节点指针remove(int index)O(n)O(n)同插入逻辑removeFirst()O(n)O(1)同头部插入set(int index, E e)O(1)O(n)ArrayList直接替换指定位置元素contains(Object o)O(n)O(n)均需遍历查找iterator().next()O(1)O(1)迭代器均维护当前位置指针3.2 实际性能差异超越时间复杂度CPU缓存友好性ArrayList元素连续存储CPU缓存行通常64字节可预加载多个元素缓存命中率极高LinkedList节点分散每次节点跳转都可能触发缓存未命中L3缓存缺失率高出3-5倍内存分配开销LinkedList每次插入都需创建新的Node对象涉及对象头、指针等额外开销ArrayList仅在扩容时分配大数组内存分配次数少扩容开销ArrayList扩容时需复制整个数组大数组扩容可能引发GC停顿LinkedList无扩容概念节点按需创建四、ArrayList扩容机制详解JDK8-JDK214.1 核心概念容量(Capacity)底层数组elementData的长度大小(Size)实际存储的元素个数扩容触发条件当size 1 elementData.length时触发扩容4.2 初始化策略构造方法初始容量首次扩容行为new ArrayList()0空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA第一次添加元素时扩容至默认容量10new ArrayList(int initialCapacity)指定的initialCapacity当元素个数超过指定容量时按1.5倍扩容new ArrayList(Collection? extends E c)集合c的大小当元素个数超过该大小时按1.5倍扩容4.3 JDK8扩容核心源码privatevoidgrow(intminCapacity){// 旧容量intoldCapacityelementData.length;// 新容量 旧容量 旧容量/2右移一位等价于除以2intnewCapacityoldCapacity(oldCapacity1);// 如果新容量仍小于最小需要容量则使用最小需要容量if(newCapacity-minCapacity0)newCapacityminCapacity;// 如果新容量超过最大数组大小则使用hugeCapacity计算if(newCapacity-MAX_ARRAY_SIZE0)newCapacityhugeCapacity(minCapacity);// 复制数组到新容量elementDataArrays.copyOf(elementData,newCapacity);}privatestaticinthugeCapacity(intminCapacity){if(minCapacity0)// 溢出thrownewOutOfMemoryError();return(minCapacityMAX_ARRAY_SIZE)?Integer.MAX_VALUE:MAX_ARRAY_SIZE;}privatestaticfinalintMAX_ARRAY_SIZEInteger.MAX_VALUE-8;4.4 JDK17扩容优化JDK17及后续LTS版本未改变核心1.5倍扩容公式但进行了重要优化引入ArraysSupport.computeGrow()统一处理数组长度计算增强整数溢出防护优化hugeCapacity()逻辑更早抛出OutOfMemoryError而非静默截断底层数组拷贝逻辑优化减少CPU占用对空数组的处理更加精细避免不必要的内存分配4.5 扩容过程详解容量计算优先按1.5倍扩容若仍不满足需求则使用最小需要容量边界检查检查是否超过最大数组大小防止内存溢出数组分配创建新的Object数组大小为计算出的新容量元素复制通过System.arraycopy()native方法将旧数组元素复制到新数组引用更新将elementData引用指向新数组计数器更新modCount用于fail-fast机制4.6 扩容性能影响与优化性能影响扩容本质是O(n)的数组复制操作大数组扩容会导致内存碎片与GC压力频繁分配/丢弃中等大小对象实时性抖动数百MB数组复制可能引发数十毫秒STW缓存局部性破坏新老数组物理地址不连续降低CPU缓存命中率优化实践预估容量创建ArrayList时根据业务峰值设置合理的初始容量批量添加优先使用addAll()方法减少扩容次数手动扩容添加大量元素前调用ensureCapacity(int minCapacity)方法五、LinkedList无扩容机制LinkedList基于双向链表实现不存在扩容概念元素存储在独立的Node节点中节点按需动态创建和销毁每次添加元素只需创建一个新的Node对象并修改前后节点的指针理论上没有容量限制受限于JVM内存内存开销固定每个节点额外占用2个引用prev和next的空间六、内存占用对比集合内存占用特点示例存储1000个Object引用ArrayList连续内存可能浪费尾部空间数组长度15001.5倍扩容后总占用1500 * 4字节引用 6KBLinkedList离散内存每个节点有额外开销节点数1000每个节点对象头(16字节) 3个引用(12字节) 28字节总占用1000 * 28字节 28KB结论在相同元素个数下LinkedList的内存占用通常是ArrayList的4-5倍七、线程安全性ArrayList和LinkedList都是非线程安全的多线程环境下同时进行结构性修改添加、删除元素会导致ConcurrentModificationException并发修改异常数据丢失、数组越界等不可预期的错误线程安全替代方案Collections.synchronizedList(new ArrayList())CopyOnWriteArrayList读多写少场景ConcurrentLinkedDeque并发队列场景八、迭代器特性与fail-fast机制8.1 迭代器类型ArrayList返回Itr迭代器支持快速随机访问LinkedList返回ListItr迭代器只能顺序访问8.2 fail-fast机制两个集合都实现了fail-fast快速失败机制迭代器创建时会记录modCount结构性修改计数器迭代过程中如果modCount发生变化其他线程修改了集合会立即抛出ConcurrentModificationException注意fail-fast是一种尽力而为的机制不能保证一定能检测到所有并发修改九、适用场景对比9.1 优先使用ArrayList的场景频繁随机访问get/set操作多尾部添加/删除操作多对内存占用敏感需要遍历整个集合ArrayList遍历性能远优于LinkedList大多数业务场景90%以上的List使用场景9.2 优先使用LinkedList的场景频繁在头部/尾部进行插入/删除操作如实现栈、队列不需要随机访问元素元素个数不确定且变化频繁9.3 重要误区澄清❌ 误区LinkedList在中间插入/删除比ArrayList快✅ 真相两者中间插入/删除的时间复杂度都是O(n)且由于ArrayList的CPU缓存优势实际性能往往比LinkedList更好❌ 误区LinkedList是队列的最佳实现✅ 真相在并发场景下ArrayDeque作为队列的性能通常优于LinkedList十、常见面试考点ArrayList的默认初始容量是多少扩容倍数是多少ArrayList和LinkedList的底层数据结构分别是什么为什么ArrayList实现了RandomAccess接口而LinkedList没有ArrayList的扩容过程是怎样的ArrayList和LinkedList在什么场景下性能差异最大两个集合都是线程安全的吗如何实现线程安全的Listfail-fast机制的原理是什么为什么说大多数场景下应该优先使用ArrayList而不是LinkedListArrayList vs LinkedList 面试标准答案可直接背诵 经典代码分析题一、面试标准答案按提问频率排序1. 核心定位与底层数据结构必问第一题背诵版ArrayList 继承自 AbstractList实现了 List、RandomAccess 接口底层是动态 Object 数组物理内存连续支持 O(1) 随机访问。LinkedList 继承自 AbstractSequentialList实现了 List、Deque 接口底层是双向链表物理内存离散不支持随机访问同时具备双端队列的特性。2. 核心操作时间复杂度对比必问第二题背诵版操作ArrayListLinkedList关键结论随机访问 get/setO(1)O(n)ArrayList 直接通过索引计算地址LinkedList 需从两端遍历尾部添加 add(E)O(1)均摊O(1)ArrayList 仅扩容时为 O(n)摊还代价极低头部添加/删除O(n)O(1)ArrayList 需移动全部元素LinkedList 仅修改指针中间添加/删除O(n)O(n)两者时间复杂度相同实际 ArrayList 更快迭代器遍历O(1) 每个元素O(1) 每个元素迭代器均维护当前指针性能接近3. ArrayList 扩容机制高频重点100% 会考背诵版分5步初始化策略无参构造初始容量为 0空数组第一次添加元素时扩容至默认容量 10JDK8 优化JDK7 默认初始容量 10有参构造初始容量为指定值集合构造初始容量为传入集合的大小扩容触发条件当size 1 elementData.length数组已满无法容纳新元素时触发扩容。扩容公式新容量 旧容量 旧容量 1即 1.5 倍扩容右移一位等价于除以 2效率更高。边界处理若 1.5 倍容量仍小于所需最小容量则直接使用最小容量若超过最大数组大小Integer.MAX_VALUE - 8则使用 Integer.MAX_VALUE扩容过程通过System.arraycopy()native 方法将旧数组元素复制到新数组更新 elementData 引用。加分项JDK17 优化了整数溢出防护和数组拷贝逻辑未改变核心 1.5 倍扩容公式。4. 内存占用与 CPU 缓存差异背诵版ArrayList连续内存仅浪费尾部未使用的数组空间内存效率高。存储 1000 个引用约占用 6KB。LinkedList每个元素需额外存储 prev 和 next 两个指针以及对象头开销内存占用是 ArrayList 的 4-5 倍。存储 1000 个元素约占用 28KB。CPU 缓存ArrayList 元素连续CPU 缓存行可预加载多个元素缓存命中率极高LinkedList 节点分散每次跳转都可能触发缓存未命中实际性能差距远大于时间复杂度体现的差异。5. 线程安全性与迭代器特性背诵版两者都是非线程安全的多线程结构性修改会导致 ConcurrentModificationException 或数据丢失。线程安全替代方案通用场景Collections.synchronizedList(new ArrayList())读多写少CopyOnWriteArrayList并发队列ConcurrentLinkedDeque都实现了 fail-fast 机制迭代器创建时记录 modCount迭代过程中若 modCount 变化则立即抛出异常这是一种尽力而为的保护机制。6. 适用场景与常见误区面试压轴题背诵版优先使用 ArrayList90% 以上业务场景频繁随机访问get/set 多尾部添加/删除操作多对内存占用敏感需要遍历整个集合仅在以下场景使用 LinkedList频繁在头部/尾部进行插入/删除如实现栈、队列不需要随机访问元素必澄清的两个误区❌ 误区LinkedList 中间插入/删除比 ArrayList 快✅ 真相两者时间复杂度都是 O(n)ArrayList 的数组复制是 native 方法且 CPU 缓存友好实际性能通常比 LinkedList 更好❌ 误区LinkedList 是队列的最佳实现✅ 真相ArrayDeque作为双端队列的性能全面优于 LinkedList是 Java 官方推荐的队列实现二、经典代码分析题含解析题目1ArrayList 扩容次数计算importjava.util.ArrayList;publicclassArrayListGrowTest{publicstaticvoidmain(String[]args){ArrayListIntegerlistnewArrayList();for(inti0;i11;i){list.add(i);}System.out.println(元素个数list.size());// 问此时 list 的底层数组容量是多少共触发了几次扩容}}答案数组容量为 15共触发了 2 次扩容。详细解析无参构造创建 ArrayList初始容量为 0空数组添加第 1 个元素时触发第一次扩容容量变为默认值 10添加第 11 个元素时size 1 11 10触发第二次扩容新容量 10 10 1 15因此最终容量为 15扩容次数为 2 次延伸考点若初始容量为 10添加 11 个元素扩容次数为 1 次优化建议提前预估容量使用new ArrayList(11)可避免所有扩容题目2ConcurrentModificationException 产生原因importjava.util.ArrayList;importjava.util.Iterator;importjava.util.List;publicclassFailFastTest{publicstaticvoidmain(String[]args){ListStringlistnewArrayList();list.add(A);list.add(B);list.add(C);// 方式1for-each 循环删除会抛异常for(Strings:list){if(B.equals(s)){list.remove(s);}}// 方式2迭代器删除不会抛异常// IteratorString it list.iterator();// while (it.hasNext()) {// String s it.next();// if (B.equals(s)) {// it.remove();// }// }System.out.println(list);}}答案方式1 会抛出ConcurrentModificationException方式2 正常执行输出[A, C]。详细解析for-each 循环本质是迭代器遍历迭代器创建时会记录expectedModCount modCount调用list.remove()方法会修改modCount但不会更新迭代器的expectedModCount下一次调用it.next()时会检查modCount expectedModCount不相等则抛出异常调用it.remove()方法会同时更新modCount和expectedModCount因此不会抛异常延伸考点为什么删除倒数第二个元素不会抛异常因为删除后 size 减 1it.hasNext()返回 false不会执行下一次next()检查多线程环境下即使使用迭代器删除也可能抛异常因为其他线程可能修改了 modCount题目3LinkedList 随机访问性能陷阱importjava.util.ArrayList;importjava.util.LinkedList;importjava.util.List;publicclassLinkedListPerformanceTest{publicstaticvoidmain(String[]args){ListIntegerarrayListnewArrayList();ListIntegerlinkedListnewLinkedList();// 初始化 10万个元素for(inti0;i100000;i){arrayList.add(i);linkedList.add(i);}// 测试随机访问性能longstartSystem.currentTimeMillis();for(inti0;i100000;i){arrayList.get(i);}System.out.println(ArrayList 随机访问耗时(System.currentTimeMillis()-start)ms);startSystem.currentTimeMillis();for(inti0;i100000;i){linkedList.get(i);}System.out.println(LinkedList 随机访问耗时(System.currentTimeMillis()-start)ms);}}答案ArrayList 耗时约 1-5msLinkedList 耗时约 5000-10000ms差距上千倍。详细解析ArrayList 的get(i)是 O(1) 操作直接通过索引计算内存地址LinkedList 的get(i)是 O(n) 操作每次都需要从头部或尾部遍历到指定位置上述代码中LinkedList 总共进行了约 50 亿次节点跳转而 ArrayList 仅进行了 10 万次内存访问再加上 CPU 缓存的差异实际性能差距会进一步扩大延伸考点遍历 LinkedList 必须使用迭代器或 for-each 循环时间复杂度为 O(n)若需要频繁随机访问绝对不能使用 LinkedList
![BUUCTF [ZJCTF 2019]NiZhuanSiWei 通关详解：从PHP伪协议到反序列化的三层渗透](http://pic.xiahunao.cn/yaotu/BUUCTF [ZJCTF 2019]NiZhuanSiWei 通关详解：从PHP伪协议到反序列化的三层渗透)
