Java常用集合类库与LinkedList、ArrayList

ArrayList基于动态数组，支持O(1)随机访问但中间增删为O(n)；LinkedList是双向链表，首尾增删O(1)但按索引查找O(n)，且内存开销大、缓存不友好，非必要不推荐使用。

ArrayList 和 LinkedList 的底层实现差异直接决定性能表现

ArrayList 是基于动态数组实现的，支持 O(1) 随机访问，但插入/删除中间元素需移动后续元素，平均时间复杂度为 O(n)；LinkedList 是双向链表，头尾增删是 O(1)，但按索引查找必须遍历，get(i) 是 O(n)。

实际选型不能只看“增删快还是查得快”，要结合具体操作模式：

• 频繁 get(i) 或遍历 for-each → 优先 ArrayList
• 大量在列表首/尾调用 addFirst()、removeLast()（且没用到 ArrayList 的随机访问）→ LinkedList 可能更合适
• 用 list.add(index, element) 在中间位置插入？两者都慢，但 ArrayList 还要数组扩容

  

  +拷贝，LinkedList 虽免拷贝，但先遍历找节点开销也不小

LinkedList 不是 Stack 或 Queue 的最佳替代品

虽然 LinkedList 实现了 Deque 接口，能当栈或队列用，但它不是最优选择：

• 作为栈：用 ArrayDeque 更高效 —— 底层循环数组，无节点对象开销，缓存友好
• 作为队列：ArrayDeque 同样优于 LinkedList，尤其在中等规模数据下吞吐更高
• Stack 类已被官方标记为 legacy，不推荐使用；Deque 接口方法如 push()、pop()、offerFirst() 等才是标准做法

简单验证：

Deque stack = new ArrayDeque<>(); // ✅ 推荐
Deque badStack = new LinkedList<>(); // ⚠️ 语义可行，但非最优

ArrayList 的扩容机制和初始容量设置很关键

默认构造函数创建的 ArrayList 初始容量为 0，第一次 add 时才分配 10 个元素空间；后续扩容策略是 oldCapacity + (oldCapacity >> 1)（即 1.5 倍），涉及数组拷贝，有 GC 和 CPU 开销。

如果已知大致元素数量，务必显式指定初始容量：

• 写死容量：如 new ArrayList(1024)
• 从已有集合构造：用 new ArrayList(otherCollection)，它会按 otherCollection.size() 预分配
• 避免反复扩容：比如循环中不断 add() 且总量可预估，不设初容量可能触发多次 resize

LinkedList 的内存开销比 ArrayList 高得多

每个 LinkedList 元素都要额外封装成一个 Node 对象，含前后引用（两个指针）和数据字段；而 ArrayList 是紧凑的 Object[] 数组。在 10 万个 String 元素场景下，LinkedList 内存占用通常是 ArrayList 的 2–3 倍以上。

这意味着：

• GC 压力更大：更多短生命周期对象（Node）被创建和回收
• CPU 缓存不友好：节点在堆中分散分布，遍历时 cache miss 高
• 除非你真正在意头尾 O(1) 操作，且数据量不大，否则别为了“听起来更灵活”选 LinkedList

真正需要链式结构的场景，往往该考虑 ConcurrentLinkedQueue 或自定义节点逻辑，而不是拿 LinkedList 当通用列表用。