【Java基础】- 集合 - ArrayList与LinkedList

ArrayList一、底层核心结构底层数据结构动态数组 transient Object[] elementData默认容量DEFAULT_CAPACITY 10最大容量Integer.MAX_VALUE - 8关键变量elementData存储元素的数组缓冲区size实际元素个数不是数组长度modCount结构修改次数用于迭代器fail-fast二、添加元素 扩容机制1. add (E e) 流程检查是否需要扩容ensureCapacityInternal数组末尾赋值 elementData[size] e2. 扩容规则核心新容量 旧容量 旧容量 1 → 1.5 倍扩容底层调用 Arrays.copyOf(elementData, newCapacity) 复制数组若指定了初始容量按指定大小初始化超过 MAX_ARRAY_SIZE 时直接用 Integer.MAX_VALUE3. 扩容流程添加元素 → 容量不足 → 1.5倍扩容 → 复制数组 → 插入元素三、查询、删除原理1. 查询 get (int index)直接下标访问elementData[index]时间复杂度 O(1)随机访问极快2. 删除 remove (int index)检查下标合法性计算需要移动的元素个数调用 System.arraycopy 整体前移覆盖效率低 O(n)size–置空末尾引用帮助 GC四、操作特点操作类型效率原因说明随机查询getO(1) 极快底层为数组连续内存可通过索引直接定位元素无需遍历尾部插入O(1) 快直接在数组末尾赋值不移动其他元素不扩容时效率极高尾部删除O(1) 快只需 size-- 并置空末尾元素无需移动其他元素中间/头部插入O(n) 慢插入位置后的所有元素需整体向后移动涉及数组拷贝中间/头部删除O(n) 慢删除位置后的所有元素需整体向前移动涉及数组拷贝扩容操作O(n) 慢创建新数组复制原数组全部元素开销较大五、fail-fast 机制每次 add/remove 都会让 modCount迭代器遍历会比对 modCount不一致 → 立即抛出 ConcurrentModificationException安全删除方式iterator.remove()list.removeIf(…)六、线程不安全问题没有任何锁多线程并发 add 可能出现数据覆盖、丢失数组下标越界高并发解决方案Collections.synchronizedListCopyOnWriteArrayList推荐七、优缺点优点随机访问极快数组特性内存紧凑无额外指针开销尾插效率高实现简单、通用缺点中间插入 / 删除效率低扩容有复制开销线程不安全八、总结ArrayList 底层是动态数组懒加载初始容量 101.5 倍扩容查询 O (1) 极快中间增删 O (n) 慢尾部增删接近O1非线程安全并发场景需用同步包装或 CopyOnWriteArrayList迭代器 fail-fast大数据量建议指定初始容量LinkedList一、底层核心结构底层数据结构双向链表JDK1.6 及以前双向循环链表JDK1.7标准双向链表非循环核心节点类 Node内部静态类三个关键属性Node first 头节点Node last 尾节点int size 元素个数modCount 结构修改次数fail-fast二、LinkedList 特点有序、可重复、允许 null无容量限制不需要扩容不支持随机访问查询慢头尾增删极快线程不安全实现了 List Deque可当 List / 栈 / 队列 / 双端队列 使用三、查询原理检查下标是否越界判断 index 在前半段还是后半段小于 size/2 → 从头遍历大于 size/2 → 从尾遍历逐个节点移动直到找到目标时间复杂度O (n)即使二分遍历最坏仍要走一半依然很慢四、增删原理增删快是指只改变节点引用不移动其他元素头部插入 / 删除直接修改 first 节点的 prev 和 next时间复杂度O(1)尾部插入 / 删除直接修改 last 节点时间复杂度O(1)中间插入 / 删除先找到目标位置O (n)再修改前后节点指针O (1)综合O(n)但指针修改开销极小五、LinkedList 效率总结操作效率说明随机访问 get(int index)O(n)必须从头/尾遍历查找头部增删O(1)直接改指针无需遍历尾部增删O(1)直接改指针无需遍历中间增删O(n)查找位置O(n)修改指针O(1)扩容无需扩容链表天然动态扩展六、优缺点维度优点缺点增删效率头尾增删效率极高为 O(1)中间增删需要先遍历查找效率一般查询效率无明显优势不支持随机访问查询需遍历时间复杂度 O(n)内存占用按需分配节点无扩容浪费每个节点需保存 prev/next 指针内存开销更大扩容机制天然支持动态扩展无需扩容无扩容问题但节点分散CPU 缓存命中率低功能特性实现 Deque 接口可做栈、队列、双端队列功能多但日常场景下性能不如 ArrayList七、总结LinkedList 是双向链表无扩容、头尾增删 O (1)查询 O (n) 慢内存开销更大、缓存不友好适合队列 / 栈不适合频繁随机访问ArrayDequeArrayDeque高性能双端队列的终极指南ArrayDequeArray Double Ended Queue是 Java 集合框架中基于循环数组实现的高性能双端队列。它兼具栈和队列的功能比LinkedList更快、比Stack更安全是算法题和电商系统中栈/队列场景的首选实现。一、核心特性与优势定义Java 6 引入位于java.util包中。继承关系public class ArrayDequeE extends AbstractCollectionE implements DequeE, Cloneable, Serializable核心优势比 LinkedList 更快基于数组CPU 缓存命中率高。比 Stack 更安全Stack是过时的遗留类ArrayDeque是现代替代品。内存紧凑比LinkedList节省约 50% 内存无节点指针开销。关键特性无容量限制自动扩容类似 ArrayList最小容量为 8。非线程安全追求极致性能多线程需外部同步。拒绝 null 元素避免歧义poll()返回 null 表示空。支持栈和队列操作一套 API 满足多种需求。二、底层实现原理循环数组设计核心思想将数组首尾相连形成闭环任何一点都可能被看作起点或终点。关键指针head指向队列头部第一个有效元素。tail指向队列尾部下一个可插入位置。容量约束数组长度始终为2 的幂次方便于位运算优化。高效扩容机制扩容时机当head tail时表示数组已满。扩容策略容量翻倍newCapacity n 1。扩容过程计算head到数组末端的元素数量r n - p。复制head到末端的元素到新数组头部。复制剩余元素到新数组后续位置。位运算优化关键技巧使用(head - 1) (elements.length - 1)代替取余操作。原理因数组长度为 2 的幂elements.length - 1的二进制位全为 1与操作相当于取余。优势处理负数情况更高效避免了传统取余的性能开销。三、ArrayDeque vs LinkedList特性ArrayDequeLinkedList底层结构动态数组循环数组实现双向链表内存占用连续内存节省空间每个节点需额外存储指针内存占用更大随机访问O(1)直接按索引访问O(n)必须遍历链表头尾插入/删除O(1)但可能触发扩容O(1)不需扩容中间插入/删除O(n)需移动元素O(1)只需改指针但需先遍历找到位置缓存命中高数组连续存储CPU 缓存友好低链表节点分散可能导致 cache miss扩容问题容量不够时自动扩容 2 倍不需要扩容线程安全非线程安全非线程安全性能对比数据2023 年测试操作ArrayDequeLinkedList优势幅度头部插入O(1)O(1)快 40%尾部插入O(1)O(1)快 35%随机访问O(n)O(n)快 10 倍内存占用更少更多节省 50%四、典型应用场景算法题与数据结构DFS/BFS 的标配作为队列实现广度优先搜索。滑动窗口Sliding Window高效地在两端添加/删除元素。撤销操作作为历史记录栈使用。单调栈问题比Stack类更高效。电商系统实战应用订单处理队列单线程环境下处理订单的高效队列。购物车操作当需要频繁在头部/尾部操作时比LinkedList更优。商品推荐队列维护用户实时推荐商品的滑动窗口。用户行为记录高效记录用户浏览、点击等行为序列。五、使用指南与最佳实践常用 API作为栈使用LIFODequeIntegerstacknewArrayDeque();stack.push(1);// 入栈inttopstack.pop();// 出栈作为队列使用FIFODequeIntegerqueuenewArrayDeque();queue.offer(1);// 入队intheadqueue.poll();// 出队注意事项避免使用addFirst/addLast失败会抛IllegalStateException应优先用offerFirst/offerLast失败返回false。多线程环境不能直接使用需用ConcurrentLinkedDeque或显式锁。null 元素插入null会直接抛NullPointerException。初始化容量明确知道元素规模时指定初始容量如new ArrayDeque(1024)避免多次扩容。性能优化技巧// 预分配容量避免 4-5 次扩容DequeIntegerdequenewArrayDeque(1024);// 优先使用 offer/poll 而非 add/remove避免异常开销if(deque.offerLast(1)){// 处理成功}else{// 处理失败扩容失败等情况}// 清空队列时使用 clear() 而非循环 removedeque.clear();六、总结与建议ArrayDeque 是 Java 集合框架中算法优化的典范通过循环数组的精妙设计和位运算优化实现了极致的性能表现。除非需要LinkedList的特定功能如中间插入删除否则应优先选择ArrayDeque。用作栈时ArrayDeque比Stack更快且更现代。用作队列时ArrayDeque比LinkedList性能更好。最佳实践在电商系统和算法题中90% 的栈/队列场景应优先使用ArrayDeque。三者对比数据结构核心特性电商业务应用场景ArrayList1. 基于动态数组内存连续2. 随机访问快O(1)3. 插入/删除慢O(n)需移动元素4. 适合读多写少场景1. 商品列表展示快速查询和展示商品信息2. 用户收藏夹需要频繁读取收藏商品3. 订单历史查询用户查看历史订单记录LinkedList1. 基于双向链表内存不连续2. 插入/删除快O(1)只需修改指针3. 随机访问慢O(n)需遍历4. 适合写多读少场景1. 订单处理流程频繁插入新订单和删除已完成订单2. 购物车操作频繁增删商品3. 消息队列处理订单状态变更通知ArrayQueue1. 基于循环数组实现 FIFO 队列2. 入队/出队快O(1)3. 不支持随机访问4. 适合任务排队场景1. 秒杀/抢购队列排队处理用户请求保证先到先得2. 支付回调处理按顺序处理支付结果3. 物流状态更新按顺序处理物流信息应用场景【电商】商品目录与展示数据应用场景推荐数据结构核心原因性能对比商品列表展示ArrayList高频随机访问需求需快速定位特定位置商品随机访问ArrayList 2ms vs LinkedList 650ms促销活动商品列表ArrayList需要快速排序、筛选和分页展示遍历性能ArrayList 15ms vs LinkedList 18ms推荐商品列表ArrayList以读取为主需快速定位和个性化展示缓存友好性ArrayList连续内存布局提升CPU缓存命中率商品详情页关联商品ArrayList内存敏感场景访问频繁修改较少内存占用ArrayList比LinkedList少30%-35%【电商】购物车与收藏应用场景推荐数据结构核心原因性能对比购物车操作LinkedList频繁在任意位置插入/删除商品无需随机访问中间插入ArrayList 420ms vs LinkedList 8ms用户收藏夹LinkedList用户频繁添加/删除收藏位置变化大删除操作ArrayList O(n) vs LinkedList O(1)用户浏览历史LinkedList持续在末尾添加记录偶尔中间删除尾部插入ArrayList 3ms vs LinkedList 5ms选择原则查询操作占比30% → 优先选择ArrayList适用于商品目录、缓存数据、用户信息查询等中间插入/删除占比50% → 优先选择LinkedList适用于购物车、订单队列、用户行为记录等仅头部/尾部操作 → 考虑ArrayDeque比LinkedList更优适用于订单处理队列、消息队列等