目录
1. Java 中的 ArrayList 和 LinkedList 简介
1. Java 中的 ArrayList 和 LinkedList 简介
ArrayList
- 数据结构：基于动态数组实现。
- 特点：
- 元素按索引存储，随机访问效率高（时间复杂度 O(1)O(1)O(1)）。
- 动态扩容机制，扩容时会重新分配更大的数组，并将旧数组中的元素复制过去。
- 插入或删除时，若非在末尾操作，需要移动大量元素（时间复杂度最差为 O(n)O(n)O(n)）。
- 适用场景：频繁读取或操作末尾元素的场景。
LinkedList
- 数据结构：基于双向链表实现。
- 特点：
- 每个节点存储数据及前后节点的引用。
- 插入或删除元素时，只需调整引用，效率较高（时间复杂度 O(1)O(1)O(1) 对于给定节点位置）。
- 访问元素时需要从头/尾节点开始遍历（时间复杂度 O(n)O(n)O(n)）。
- 适用场景：频繁插入或删除中间元素的场景。
2. 相同数量级下的内存开销对比
ArrayList 的内存开销
- 存储元素的连续内存块 + 数组的额外空间（动态扩容时）。
- 每个元素仅占用对象引用的大小（通常是 4 字节或 8 字节，具体取决于 JVM 配置）。
- 动态数组可能浪费一定空间（未使用的容量）。
LinkedList 的内存开销
- 每个节点需要存储数据及两个引用（前驱节点和后继节点）。
- 除了数据本身，还需要额外的内存开销来存储这些引用。
- 内存占用大幅高于 ArrayList。
在相同数量级下，LinkedList 的内存开销明显高于 ArrayList，尤其在存储大量元素时。
3. 它们的速度对比
| 操作 | ArrayList | LinkedList |
|---|---|---|
| 随机访问 | O(1)O(1)O(1)：直接通过索引访问。 | O(n)O(n)O(n)：需要逐个遍历节点。 |
| 插入（中间位置） | O(n)O(n)O(n)：需要移动元素。 | O(1)O(1)O(1)：只需调整引用（需定位节点）。 |
| 插入（末尾） | O(1)O(1)O(1)：动态扩容后开销较高。 | O(1)O(1)O(1)：无需额外操作。 |
| 删除（中间位置） | O(n)O(n)O(n)：需要移动元素。 | O(1)O(1)O(1)：只需调整引用（需定位节点）。 |
| 删除（末尾） | O(1)O(1)O(1)：直接移除尾部元素。 | O(1)O(1)O(1)：直接移除尾节点。 |
总结
内存开销：
- LinkedList 更高，因为每个节点需要额外的引用存储。
- ArrayList 更节省内存。
性能：
- ArrayList 适合频繁随机访问、追加元素。
- LinkedList 更适合频繁的中间插入和删除操作。
综合考虑内存和速度，多数场景下更推荐使用 ArrayList，除非有明确的需求（如频繁中间插入/删除）。