ArrayList 和 LinkedList 的区别是什么？

在Java集合框架中，ArrayList和LinkedList都是List接口的实现类，但底层数据结构和操作效率存在显著差异：

1. 底层数据结构

• ArrayList
  基于动态数组实现。初始容量为10，当元素超出容量时，自动扩容至原容量的1.5倍（例如：newCapacity = oldCapacity + (oldCapacity >> 1)）。

• LinkedList
  基于双向链表实现。每个节点（Node）包含数据域和两个指针： $$ \text{Node} = { \text{prev}, \text{element}, \text{next} } $$

2. 操作效率对比

随机访问（Get/Set）

• ArrayList：$O(1)$
  通过索引直接定位数组位置，例如：array[index]。
• LinkedList：$O(n)$
  需遍历链表，最坏情况下需扫描半个链表（平均时间复杂度为 $n/2$）。

插入与删除（Add/Remove）

• ArrayList：
  • 尾部操作：$O(1)$（扩容时除外）
  • 中间操作：$O(n)$，需移动后续元素（例如：删除索引 $i$ 的元素需移动 $n-i-1$ 个元素）。
• LinkedList：
  • 任意位置操作：$O(1)$，仅需修改相邻节点的指针（但需 $O(n)$ 时间定位位置）。

3. 内存占用

• ArrayList
  仅需存储元素和数组容量，内存连续。
• LinkedList
  每个元素需额外存储两个指针（每个指针占4~8字节），内存非连续，空间开销更大。

4. 适用场景

• ArrayList：
  适合频繁随机访问（如按索引查询）、尾部插入/删除操作。
• LinkedList：
  适合频繁在任意位置插入/删除（如实现栈、队列或频繁修改的列表）。

代码示例

// ArrayList 尾部插入高效 ArrayList<Integer> arrayList = new ArrayList<>(); arrayList.add(1); // O(1) // LinkedList 中间插入高效 LinkedList<Integer> linkedList = new LinkedList<>(); linkedList.add(0, 1); // O(1) 若已知位置

小结