Java 中 List 的几种实现
List 是有序、可重复的集合接口
常见实现:ArrayList、LinkedList、Vector、Stack、CopyOnWriteArrayList
ArrayList
底层结构
新容量 = 旧容量 + 旧容量 / 2(1.5 倍)
时间复杂度
| 操作 | 复杂度 | 说明 |
|---|
| 随机访问 get(i) | O(1) | 数组下标 |
| 尾部 add | O(1) 均摊 | 扩容时 O(n) |
| 中间插入/删除 | O(n) | 元素整体移动 |
线程安全
解决方案:Collections.synchronizedList;CopyOnWriteArrayList
LinkedList
底层结构
- 双向链表
- 每个节点:prev | item | next
时间复杂度
| 操作 | 复杂度 | 说明 |
|---|
| get(i) | O(n) | 要遍历 |
| 头/尾插入删除 | O(1) | 指针操作 |
| 中间插入 | O(n) | 找位置 |
Vector
底层结构
关键区别
问题
Stack
继承关系
Stack extends Vector
特点
- 后进先出(LIFO)
- 线程安全(继承 Vector)
CopyOnWriteArrayList(并发重点)
底层思想
特点
| 方面 | 说明 |
|---|
| 线程安全 | ✅ |
| 读性能 | 非常高 |
| 写性能 | 较差(复制数组) |
| 迭代 | 不会抛 ConcurrentModificationException |
对比总结
| 实现 | 底层 | 线程安全 | 适合场景 |
|---|
| ArrayList | 动态数组 | ❌ | 查询多 |
| LinkedList | 双向链表 | ❌ | 头尾操作多 |
| Vector | 动态数组 | ✅ | 淘汰 |
| Stack | 栈 | ✅ | 淘汰 |
| CopyOnWriteArrayList | 数组复制 | ✅ | 并发读多 |
面试常见问题
Q1:ArrayList 和 LinkedList 区别?
ArrayList:数组,查询快,插入慢
LinkedList:链表,头尾操作快,随机访问慢
Q2:为什么 ArrayList 不是线程安全?
add / remove 过程中可能发生:
扩容
覆盖
数据丢失
Q3:CopyOnWriteArrayList 为什么读快?
读操作不加锁
始终读的是稳定数组快照
Q4:为什么不推荐 Vector / Stack?
synchronized 粒度太大
性能差
有更好的并发方案
总结
ArrayList 查得快,LinkedList 插得快(头尾),
并发读多用 CopyOnWrite,Vector Stack 已淘汰
List 与 Set 的区别
List vs Set
| 对比点 | List | Set |
|---|
| 是否有序 | ✅ 有序(按插入顺序) | ❌ 大多无序(LinkedHashSet 例外) |
| 是否允许重复 | ✅ 允许 | ❌ 不允许 |
| 是否有下标 | ✅ 有(get(i)) | ❌ 没有 |
| 常见实现 | ArrayList、LinkedList | HashSet、LinkedHashSet、TreeSet |
| 典型用途 | 保存'有顺序、可重复'的数据 | 保存'去重'的数据 |
一句话记忆:
List = 有顺序 + 可重复
Set = 去重
什么是 List?
- 像数组的升级版
- 能按顺序存
- 能存重复元素
- 能通过下标访问
List<Integer> list = new ArrayList<>();
list.add(10);
list.add(10);
list.add(20);
System.out.println(list);
System.out.println(list.get(1));
什么是 Set?
Set<Integer> set = new HashSet<>();
set.add(10);
set.add(10);
set.add(20);
System.out.println(set);
Set 是怎么判断'重复'的?
靠 hashCode() + equals()
- 先算 hashCode
- 再用 equals 比较
List vs Set 核心区别
List 和 Set 都是 Collection 的子接口,主要区别在于是否允许重复和是否有顺序。List 允许重复元素并且有下标,适合顺序存储;Set 不允许重复元素,主要用于去重。
一句话总结
List:顺序 + 重复 + 下标
Set:去重 + 无下标 + 基于 equals/hashCode