目录
1. List接口简介
在Java集合框架中,List接口是最常用的接口之一。List表示一个有序的集合,允许重复元素,并提供了基于索引的操作。
主要的List方法包括:
add(E e): 添加元素到列表末尾add(int index, E element): 在指定位置插入元素get(int index): 获取指定位置的元素remove(int index): 移除指定位置的元素set(int index, E element): 替换指定位置的元素size(): 返回列表的大小
2. ArrayList
ArrayList是List接口最常用的实现之一,它的底层是基于动态数组实现。
2.1 基本特性
- 允许null元素
- 有序集合
- 非同步(线程不安全)
- 随机访问效率高
- 插入和删除操作可能较慢(特别是在列表中间)
2.2 内部实现
ArrayList内部使用一个对象数组来存储元素。当数组容量不足时,会进行扩容操作。
2.3 扩容机制
当ArrayList的大小超过其当前容量时,会触发扩容操作:
- 创建一个新的更大的数组(通常是原容量的1.5倍)
- 将原数组中的元素复制到新数组
- 将新数组赋值给elementData字段
/**
* 增加数组的容量，以确保它可以容纳至少minCapacity个元素
* 此方法在内部用于管理动态数组的大小，当数组的当前容量不足以容纳新元素时调用
*
* @param minCapacity 数组需要能够容纳的最小容量
* @return 扩容后的数组对象
*/
private Object[] grow(int minCapacity) {
// 获取当前数组的容量
int oldCapacity = elementData.length;
// 检查当前数组是否已经初始化或者不是默认的空数组
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 计算并获取新的数组容量，确保它既可以满足最小容量要求，又符合首选的扩容策略
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, //最小增长量
oldCapacity >> 1 /* 优先增长量*/);
// 使用新的容量复制当前数组，并返回扩容后的数组
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
// 如果当前数组未初始化或等于默认的空数组，使用默认容量或minCapacity中较大的一个来初始化数组
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
/**
* 计算基于旧长度和增长需求的新数组长度。
* 本方法旨在确定一个满足最小增长要求的新长度，同时考虑一个优先增长量。
* 在特殊情况下（例如，当首选长度超过最大数组长度限制时），将使用不同的计算策略。
*
* @param oldLength 原始数组长度，必须是非负数。
* @param minGrowth 最小增长量，也就是我现在至少还要增加的容量，必须是正数，表示所需增长的最小长度。
* @param prefGrowth 优先增长量，表示期望的增长量，为原容量的一半。
* @return 根据参数计算的新数组长度。
*/
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
// 前提条件检查因内联而省略
// 应断言 oldLength 非负
// 应断言 minGrowth 为正数
// 计算首选长度，可能溢出
int prefLength = oldLength + Math.max(minGrowth, prefGrowth);
// 如果首选长度在合理范围内，直接返回 SOFT_MAX_ARRAY_LENGTH是数组最大长度的限制
if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
return prefLength;
} else {
// 将冷代码放在单独的方法中处理
return hugeLength(oldLength, minGrowth);
}
}
2.4 性能考虑
- 随机访问: O(1)
- 插入/删除(末尾): 平均O(1)
- 插入/删除(中间): O(n)
- 查找: O(n)
2.5 代码示例
import java.util.ArrayList;
import java.util.List;
public class ArrayListExample {
public static void main(String[] args) {
List<String> fruits = new ArrayList<>();
// 添加元素
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Orange");
// 在指定位置插入元素
fruits.add(1, "Mango");
System.out.println("Fruits 列表: " + fruits);//Fruits 列表: [Apple, Mango, Banana, Orange]
// 获取元素
String secondFruit = fruits.get(1);
System.out.println("第二个: " + secondFruit);//第二个: Mango
// 修改元素
fruits.set(2, "Grape");
// 删除元素
fruits.remove("Apple");
System.out.println("更新后的列表: " + fruits);//更新后的列表: [Mango, Grape, Orange]
// 遍历列表
for (String fruit : fruits) {
System.out.println(fruit);//Mango Grape Orange
}
// 检查是否包含某元素
boolean containsBanana = fruits.contains("Banana");
System.out.println("有没有Banana? " + containsBanana);//有没有Banana? false
// 获取列表大小
int size = fruits.size();
System.out.println("列表大小: " + size);//列表大小: 3
}
}
3. LinkedList
LinkedList是基于双向链表实现的List,同时也实现了Deque接口。
### 3.1 特性
- 允许null元素
- 有序集合
- 非同步(线程不安全)
- 插入和删除操作效率高(特别是在列表两端)
- 随机访问效率较低
3.2 内部实现
LinkedList使用双向链表存储元素,每个节点包含前驱节点、后继节点和元素值。
3.3 性能考虑
- 随机访问: O(n)
- 插入/删除(两端): O(1)
- 插入/删除(中间): O(n)
- 查找: O(n)
3.4 代码示例
import java.util.LinkedList;
import java.util.List;
public class LinkedListExample {
public static void main(String[] args) {
LinkedList<String> animals = new LinkedList<>();
// 添加元素
animals.add("Lion");
animals.add("Tiger");
animals.add("Bear");
// 在列表开头添加元素
animals.addFirst("Elephant");
// 在列表末尾添加元素
animals.addLast("Giraffe");
System.out.println("链表: " + animals);//链表: [Elephant, Lion, Tiger, Bear, Giraffe]
// 获取第一个和最后一个元素
String firstAnimal = animals.getFirst();
String lastAnimal = animals.getLast();
System.out.println("第一个: " + firstAnimal);//第一个: Elephant
System.out.println("最后一个: " + lastAnimal);//最后一个: Giraffe
// 删除第一个和最后一个元素
animals.removeFirst();
animals.removeLast();
System.out.println("更新后的链表: " + animals);//更新后的链表: [Lion, Tiger, Bear]
// 使用索引访问元素
String secondAnimal = animals.get(1);
System.out.println("第二个: " + secondAnimal);//第二个: Tiger
// 修改元素
animals.set(1, "Leopard");
// 遍历列表
for (String animal : animals) {
System.out.println(animal);//Lion Leopard Bear
}
// 检查是否包含某元素
boolean containsTiger = animals.contains("Tiger");
System.out.println("链表是否存在Tiger? " + containsTiger);//链表是否存在Tiger? false
// 获取列表大小
int size = animals.size();
System.out.println("链表大小: " + size);//链表大小: 3
}
}
4. Vector
Vector是一个古老的同步List实现,现在已经不推荐使用。
4.1 特性
- 同步(线程安全)
- 允许null元素
- 有序集合
- 基于动态数组实现
4.2 与ArrayList的比较
- 同步性: Vector是同步的,ArrayList不是。
- 性能: 在单线程环境下,ArrayList通常优于Vector。
- 扩容: Vector默认扩容为原来的2倍,ArrayList是1.5倍。
4.3 代码示例
import java.util.Vector;
public class VectorExample {
public static void main(String[] args) {
Vector<String> vector = new Vector<>();
// 添加元素
vector.add("One");
vector.add("Two");
vector.add("Three");
System.out.println("Vector: " + vector);//Vector: [One, Two, Three]
// 在指定位置插入元素
vector.add(1, "Four");
System.out.println("Vector: " + vector);//Vector: [One, Four, Two, Three]
// 获取元素
String element = vector.get(2);
System.out.println("第三个元素: " + element);//第三个元素: Two
// 修改元素
vector.set(0, "Zero");
// 删除元素
vector.remove("Three");
System.out.println("更新后Vector: " + vector);//更新后Vector: [Zero, Four, Two]
// 获取向量大小
int size = vector.size();
System.out.println("Vector 大小: " + size);//
// 检查是否包含某元素
boolean containsTwo = vector.contains("Two");//Vector 大小: 3
System.out.println("是否包含 'Two'? " + containsTwo);//是否包含 'Two'? true
}
}
5. Collections.synchronizedList
Collections.synchronizedList是一个同步List包装器,可以将任何List转换为线程安全的List。
根据list是否实现RandomAccess接口，决定使用哪种线程安全的实现,总之返回一个线程安全的List
5.1 特性
- 同步(线程安全)
- 包装了一个普通的List实现
- 所有操作都是同步的
5.2 实现原理
synchronizedList通过在每个方法上添加同步块来实现线程安全。
5.3 使用场景
当需要在多线程环境中使用ArrayList或LinkedList时,可以使用synchronizedList。
5.4 代码示例
import java.util.Collections;
import java.util.List;
import java.util.ArrayList;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
public class SynchronizedListExample {
public static void main(String[] args) {
// 创建一个非线程安全的ArrayList
List<String> unsafeList = new ArrayList<>();
//
// // 使用Collections.synchronizedList将其转换为线程安全的List
// List<String> safeList = Collections.synchronizedList(unsafeList);
// 创建一个线程池，模拟多线程环境
ExecutorService executorService = Executors.newFixedThreadPool(10);
// 提交多个任务，每个任务向safeList中添加元素
for (int i = 0; i < 100; i++) {
final int index = i;
executorService.submit(() -> {
String item = "Item " + index;
unsafeList.add(item);
// System.out.println(Thread.currentThread().getName() + " added: " + item);
});
}
// 关闭线程池，等待所有任务完成
executorService.shutdown();
try {
//等待所有任务完成，超时则关闭线程池
if (!executorService.awaitTermination(60, TimeUnit.SECONDS)) {
executorService.shutdownNow();
}
} catch (InterruptedException e) {
executorService.shutdownNow();
}
// 输出最终的列表内容，验证线程安全性
System.out.println("Final unsafeList size: " + unsafeList.size());
// for (String item : unsafeList) {
// System.out.println(item);
// }
}
}
首先来看不安全List的结果：多次测试也会发现，最后的集合数量是存在问题的，方便显示我只输出了集合最后数量
接下来使用安全的List进行测试（注意把循环体、输出的list修改为safeList），无论执行多少次，最后的结果都是100
6. CopyOnWriteArrayList
CopyOnWriteArrayList是一个线程安全的List实现,专门设计用于处理读多写少的并发场景。
CopyOnWrite一般就是写时复制：当要对某个对象进行修改时，先对该对象进行复制一份，在副本上进行修改，修改完毕后再将原来的对象指向副本完成更新，因此要注意当对象较大时会耗费较大的空间
6.1 特性
- 线程安全
- 适用于读多写少的场景
- 写操作开销大(复制整个数组)
- 读操作不需要加锁,性能高
6.2 实现原理
- 读操作不加锁,直接返回数组元素（如果有在修改，那就先读取原来的数组）。
- 写操作会创建一个新的数组副本,在副本上进行修改,然后用新数组替换旧数组。
这里看看add方法来源码
6.3 使用场景
- 读操作远多于写操作的并发场景
- 监听器列表
- 需要频繁遍历的线程安全列表
6.4 代码示例
import java.util.concurrent.CopyOnWriteArrayList;
public class CopyOnWriteArrayListExample {
public static void main(String[] args) {
CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
// 添加元素
list.add("Red");
list.add("Green");
list.add("Blue");
System.out.println("初始 list: " + list);
// 创建一个读线程
Runnable reader = () -> {
for (String color : list) {
System.out.println(Thread.currentThread().getName() + " 正在读: " + color);
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
};
// 创建一个写线程
Runnable writer = () -> {
list.add("Yellow");
System.out.println(Thread.currentThread().getName() + " 写入 Yellow");
list.remove("Green");
System.out.println(Thread.currentThread().getName() + " 删除 Green");
};
// 启动多个读线程和一个写线程
new Thread(reader, "Reader1").start();
new Thread(reader, "Reader2").start();
new Thread(writer, "Writer").start();
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("最后的 list: " + list);
}
}
输出结果：
这里能够看到：writer线程写入yellow并且删除green后，两个reader线程都仍然读取到了green并且都没有读取到插入的yellow，正是因为两个读线程读取的快照是原数组，而修改的对象是原对象的副本，再看最后的list发现，green被删除了也插入了yellow，正是修改完成后重新指向了新数组的结果。
7. 性能比较
下面是各种List实现在不同操作上的性能比较:
| 操作 | ArrayList | LinkedList | Vector | CopyOnWriteArrayList |
|---|---|---|---|---|
| 随机访问 | O(1) | O(n) | O(1) | O(1) |
| 插入/删除(开头) | O(n) | O(1) | O(n) | O(n) |
| 插入/删除(结尾) | O(1)* | O(1) | O(1)* | O(n) |
| 插入/删除(中间) | O(n) | O(n) | O(n) | O(n) |
| 搜索 | O(n) | O(n) | O(n) | O(n) |
*注: 当需要扩容时为O(n)
8. 选择合适的List实现
- ArrayList: 适用于随机访问频繁、插入删除操作较少的场景。
- LinkedList: 适用于频繁在两端插入删除,但很少随机访问的场景。
- Vector: 不推荐使用,已被ArrayList和Collections.synchronizedList取代。
- Collections.synchronizedList: 需要线程安全且读写操作都比较频繁的场景。
- CopyOnWriteArrayList: 读多写少的并发场景,如监听器列表。
9. 总结
Java提供了多种List实现,每种实现都有其特定的用途和性能特征。在选择使用哪种List实现时,需要考虑以下因素:
- 是否需要线程安全
- 读写操作的频率
- 随机访问的需求
- 插入和删除操作的位置和频率
- 内存使用和性能要求
如果想以此对比Map家族可参考：
链接: Java中的Map集合
希望本文章能对各位有所帮助！
标签：Java,ArrayList,List,System,线程,数组,println,out From： https://blog.csdn.net/2303_76892351/article/details/143993731