ArrayList和LinkedList的区别是什么？

ArrayList和LinkedList是Java集合框架中两种常用的列表实现，它们的核心区别主要体现在底层数据结构、操作效率及适用场景上。以下是详细对比：

1. 底层数据结构

• ArrayList：基于动态数组实现。数组在内存中是连续存储的，支持快速随机访问。
• LinkedList：基于双向链表实现。每个元素（节点）通过前后指针连接，内存分布不连续。

2. 访问元素的效率

• ArrayList：
  • 支持随机访问（通过索引直接定位），时间复杂度为 O(1)。
  • 例如：list.get(100) 可以直接通过数组下标访问。
• LinkedList：
  • 需要从头或尾遍历链表找到目标位置，时间复杂度为 O(n)。
  • 若频繁访问中间元素，性能显著低于ArrayList。

3. 插入与删除操作的效率

• ArrayList：
  • 尾部插入：平均时间复杂度 O(1)（扩容时需复制数组，均摊后仍为O(1)）。
  • 中间/头部插入：需要移动后续元素，时间复杂度 O(n)。
• LinkedList：
  • 任意位置插入：找到位置后仅需修改指针，插入本身为 O(1)，但查找位置仍需 O(n)。
  • 头尾插入：通过头尾指针直接操作，时间复杂度 O(1)（如addFirst()、addLast()）。

4. 内存占用

• ArrayList：
  • 仅需存储元素和数组容量，内存连续，空间利用率高。但可能存在预留空间（扩容机制）。
• LinkedList：
  • 每个节点需额外存储前后指针（各占4-8字节），内存开销更大。节点分散存储，可能增加内存碎片。

5. 扩容机制

• ArrayList：
  • 初始容量默认10，扩容时新容量为原1.5倍（int newCapacity = oldCapacity + (oldCapacity >> 1)），需复制整个数组。
• LinkedList：
  • 无扩容概念，每次插入仅创建新节点，无需连续内存分配。

6. 应用场景

• 推荐使用ArrayList：
  • 频繁随机访问（如按索引读取）。
  • 数据量相对稳定，尾部插入/删除为主。
  • 适合CPU缓存友好的场景（连续内存）。
• 推荐使用LinkedList：
  • 频繁在头部或中间插入/删除（如实现队列、栈或需要大量结构调整的场景）。
  • 无需预先分配内存，适合动态增长且内存碎片不敏感的场景。

总结对比表

代码示例对比

▼
java
复制代码
// ArrayList尾部插入高效
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1); // O(1)

// LinkedList头部插入高效
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.addFirst(1); // O(1)

最终建议

• 选择依据：根据具体操作类型（读多还是写多）和数据规模权衡。
• 注意：LinkedList在大多数情况下性能优势有限，需结合实际场景测试验证。