ArrayList 和 LinkedList（arraylist和linkedlist线程安全吗）
在 Java 中，ArrayList 和 LinkedList 是 List 接口的两个常用实现类，它们都用于存储和操作有序、可重复的元素集合。虽然功能相似，但在底层实现、性能特性和适用场景上有显著区别。
一、基本对比表
特性 | ArrayList | LinkedList |
底层结构 | 动态数组 | 双向链表 |
随机访问 | 快（O(1)） | 慢（O(n)） |
插入/删除（已知位置） | 慢（O(n)） | 快（O(1)） |
内存占用 | 较小 | 较大（每个节点多出前后指针） |
线程安全 | 不安全 | 不安全 |
是否支持高效头尾操作 | 支持（如作为队列使用） |
二、底层实现详解
1. ArrayList
- 基于 动态数组 实现。
- 初始容量为 10（JDK 8+），当数组满时会扩容（通常是当前容量的 1.5 倍）。
- 支持通过索引快速访问任意元素（因为数组是连续内存）。
- 在中间插入或删除元素时，需要移动大量元素，效率较低。
2. LinkedList
- 基于 双向链表 实现。
- 每个元素（节点）包含三个部分：前驱指针、数据、后继指针。
- 插入和删除只需修改相邻节点的指针，无需移动其他元素。
- 查找某个索引位置的元素时，必须从头或尾开始遍历，因此效率低。
三、常见操作性能对比（Big O 表示法）
操作 | ArrayList | LinkedList |
访问（get(index)） | O(1) | O(n) |
添加到末尾（add(e)） | O(1)* | O(1) |
插入到指定位置（add(index, e)） | O(n) | O(1)** |
删除指定位置（remove(index)） | O(n) | O(1)** |
删除指定元素（remove(Object)） | O(n) | O(n) |
*：如果需要扩容，则为 O(n)**：前提是已经定位到节点位置，否则查找仍为 O(n)
四、适用场景对比
场景 | 推荐实现 |
需要频繁随机访问元素 | ArrayList |
需要频繁在头部或尾部插入/删除 | LinkedList（适合做队列或双端队列） |
数据量较大且频繁增删 | LinkedList |
数据量较小，读多写少 | ArrayList |
使用 ListIterator 进行双向遍历 | LinkedList 更高效 |
五、源码级差异（简要）
ArrayList 示例：
transient Object[] elementData; // 存储元素的数组
int size; // 实际元素数量- 扩容机制：
int newCapacity = oldCapacity + (oldCapacity >> 1); // 原容量的 1.5 倍LinkedList 示例：
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
}- 每个节点保存前一个和后一个节点的引用。
六、如何选择？
如果你需要... | 选择 |
快速访问任意元素 | ArrayList |
高频插入/删除（特别是在头部） | LinkedList |
节省内存 | ArrayList |
用作栈、队列或双端队列 | LinkedList（也可使用 ArrayDeque） |
七、简单性能测试代码（伪代码）
// 测试插入到中间
List<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new LinkedList<>();
long start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
list.add(5000, i); // 插入到中间
}
System.out.println("耗时：" + (System.currentTimeMillis() - start) + " ms");- ArrayList 可能较慢（每次都要移动一半元素）
- LinkedList 相对快很多（找到位置后插入快）
八、小结
项目 | ArrayList | LinkedList |
查询 | 快 | 慢 |
插入/删除 | 慢 | 快 |
内存占用 | 少 | 多 |
默认推荐 | 一般情况 | 仅特定场景 |
