在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) 若已知位置小结
| 特性 | ArrayList | LinkedList |
|---|---|---|
| 随机访问 | $O(1)$ | $O(n)$ |
| 头部插入/删除 | $O(n)$ | $O(1)$ |
| 尾部插入/删除 | $O(1)$（均摊） | $O(1)$ |
| 中间插入/删除 | $O(n)$ | $O(n)$（定位）+ $O(1)$（操作） |
| 内存占用 | 更低 | 更高（指针开销） |
