章
目
录
Java ArrayList（Java数组列表）表示一个可调整大小的对象数组，允许我们添加、删除、查找、排序和替换元素。ArrayList是集合框架的一部分，并在List接口中实现。
1.Java ArrayList简介
1.1. 什么是ArrayList？
ArrayList具有以下特点：
- 有序 – ArrayList中的元素保留它们的顺序，这默认为它们添加到列表中的顺序。
- 基于索引 – 可以使用索引位置随机访问元素。索引从’0’开始。
- 动态调整大小 – 当需要添加的元素多于当前大小时，ArrayList会动态增长。
- 非同步 – 默认情况下，ArrayList不是同步的。程序员需要适当地使用同步关键字或简单地使用Vector类。
- 允许重复项 – 我们可以在ArrayList中添加重复元素。在Set集合中是不可以重复的。
java.util.ArrayList类扩展了实现List接口的AbstractList。List接口以分层顺序扩展了Collection和Iterable接口。
1.2. 内部实现
在内部，ArrayList类使用数组（也称为支持数组）来实现。实际上，添加或删除ArrayList中的元素会修改支持数组中的元素。所有ArrayList方法都访问这个支持数组并在其中获取/设置元素。
public class ArrayList<E> ... {
transient Object[] elementData; //backing array
private int size; //array or list size
//...
}
当我们创建一个空的ArrayList时，该数组以默认容量10进行初始化。我们不断向ArrayList中添加项目，它们都存储在支持数组中。
当数组变满时，而我们要添加一个新项时，会进行重新调整大小的操作。在重新调整大小中，数组的大小增加，以确保它永远不会超出JVM的限制。项目从先前的数组复制到这个新数组中。然后，先前的支持数组会被释放以进行垃圾收集。
1.3. 何时使用ArrayList？
如前所述，ArrayList是可调整大小的数组实现。在处理数组时，一个主要关注点是始终检查有效的索引，否则程序会抛出IndexOutOfBoundsException异常。ArrayList永远不会抛出IndexOutOfBoundsException异常，我们可以自由地添加/删除元素，ArrayList在添加或删除元素时会自动处理重新调整大小。
ArrayList是Java集合框架的一部分，因此可以无缝地与其他集合类型和Stream API一起使用，提供了在处理数据时的很多灵活性。
当与泛型一起使用时，ArrayList在编译时提供类型安全性，并确保它只包含特定类型的项目，从而减少了在运行时发生ClassCastException的机会。
2.创建一个ArrayList
在不同的情境下，我们可以以不同的方式创建ArrayList。让我们来看看它们：
2.1. 使用构造函数
创建ArrayList最简单的方式是使用其构造函数。它的默认无参构造函数创建一个空的ArrayList，其默认初始容量为10。
ArrayList<String> arrayList = new ArrayList<>();
可选地，我们可以在构造函数中指定initialCapacity以避免频繁的调整大小操作，如果我们已经知道要存储多少项。
ArrayList<String> arrayList = new ArrayList<>(128);
还可以通过将集合传递给构造函数来使用另一个列表或集合中的项目来初始化ArrayList。
Set<String> set = ...;
//使用set集合中元素初始化List
ArrayList<String> arrayList = new ArrayList<>(set);
2.2. 使用工厂方法
自Java 9以来，我们可以使用工厂方法来初始化带有项目的ArrayList。例如，List.of() 是一个创建带有指定项目的不可变列表的方法。通常用于在一行中创建和初始化一个列表。我们可以将其与ArrayList构造函数一起使用，在一行中创建一个ArrayList并填充它的项目。
ArrayList<String> arrayList = new ArrayList<>(List.of("a", "b", "c"));
同样，我们也可以使用Arrays.asList() 工厂方法：
ArrayList<String> arrayList = new ArrayList<>(Arrays.asList("a", "b", "c"));
2.3. 创建自定义对象的ArrayList
尽管在ArrayList中存储自定义对象似乎很简单，但我们仍必须确保自定义对象正确实现了equals()方法并满足要求。
考虑以下具有两个字段id和name的Item类。它没有定义equals方法。
class Item {
long id;
String name;
public Item(long id, String name) {
this.id = id;
this.name = name;
}
}
当我们向列表中添加一些项，然后尝试检查一个项时，我们得不到预期的结果。未找到该项。
ArrayList<Item> listOfItems = new ArrayList<>(List.of(new Item(1, "Item1"), new Item(2, "Item2")));
System.out.println( listOfItems.contains(new Item(1, "Item1")) ); //prints 'false'
在我们的示例中，假设如果两个项具有相同的id，则它们必须相等。让我们编写一个自定义的equals()方法：
class Item {
//...
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
Item item = (Item) o;
return id == item.id;
}
}
现在当我们再次运行示例代码时，我们得到了正确的结果，该项在列表中找到了。
System.out.println( listOfItems.contains(new Item(1, "Item1")) ); //prints 'true'
3.常见操作
现在我们对ArrayList类有了基本了解，让我们看看其用于常见CRUD操作的方法：
3.1. 向ArrayList添加项
我们可以使用两种方法将项附加到现有的ArrayList中：
- add(e)：将指定的元素附加到列表的末尾，并返回true，否则返回false。
- addAll()：将指定集合中的所有元素按照它们由指定集合的迭代器返回的顺序附加到列表的末尾。要在指定位置添加元素，可以使用add(index, element)方法。
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("a"); // [a]
arrayList.addAll(List.of("b", "c", "d")); // [a, b, c, d]
要在指定位置添加元素，我们可以使用该add(index, element)方法。
- 它将指定元素插入列表中的指定位置。
- 它还将当前位于该位置的元素（如果有）和任何后续元素向右移动（将其索引加一）。
ArrayList<String> arrayList = new ArrayList<>(List.of("a", "b", "c", "d"));
arrayList.add(2, "temp"); //[a, b, temp, d, c]
3.2. 替换ArrayList中的元素
要用新元素替换现有元素，可以使用set(index, element)方法。
ArrayList<String> listWithItems = new ArrayList<>(List.of("a", "b", "c", "d"));
System.out.println(listWithItems); //[a, b, c, d]
listWithItems.set(2, "T");
System.out.println(listWithItems); //[a, b, T, d]
3.3. 从ArrayList中删除元素
ArrayList类提供了两种用于删除项的方法：
- remove(e)：从此列表中删除指定元素的第一个出现，如果存在则返回true。否则，返回false。
- removeAll(collection)：删除包含在指定集合中的所有元素。即使由于此操作而删除了单个元素，它也会返回true，否则如果列表未更改，则返回false。
ArrayList<String> list = new ArrayList<>(List.of("a", "b", "c", "d"));
list.remove("c"); // [a, b, d]
list.removeAll(List.of("b", "d")); // [a]
我们可以使用clear()方法一次性删除列表中的所有元素。它会使列表为空，其中不包含任何元素。
list.clear(); // []
3.4. 检查ArrayList大小
要获取数组列表的大小，或计算列表中的元素数，我们可以使用size()方法。
ArrayList<String> list = new ArrayList<>(List.of("a", "b", "c", "d"));
int size = list.size(); // 4
3.5. 检查ArrayList是否为空
isEmpty()方法在列表不包含元素时返回true，否则返回false。
ArrayList<String> list = new ArrayList<>();
boolean isEmpty = list.isEmpty(); // true
list.add("a");
isEmpty = list.isEmpty(); // false
4. 遍历ArrayList
作为 Collection 框架的一部分，我们可以使用多种方法来迭代 ArrayList 的元素。
4.1. 使用ListIterator
ArrayList的listIterator()方法返回ListIterator类型的迭代器。它允许以任一方向遍历列表，在迭代期间修改列表，并获取迭代器在列表中的当前位置。
ListIterator<String> listIterator = list.listIterator();
while (listIterator.hasNext()) {
System.out.println(listIterator.next());
}
值得一提的是，ListIterator中的remove()和set()方法不是根据光标位置定义的；它们是定义为在调用next()或previous()后操作最后返回的元素。
ArrayList<String> list = new ArrayList<>(List.of("a", "b", "c", "d"));
ListIterator<String> listIterator = list.listIterator();
while (listIterator.hasNext()) {
if(listIterator.next().equalsIgnoreCase("c")){
listIterator.remove();
}
}
System.out.println(list); // [a, b, d]
4.2. 使用增强的 for 循环（for-each）
我们还可以将for-each 循环与ArrayList一起使用。
ArrayList<String> list = new ArrayList<>(List.of("a", "b", "c", "d"));
list.forEach(e -> {
System.out.println(e);
});
5.ArrayList和Java Streams
5.1. 迭代元素
除了forEach()循环和ListIterator之外，我们还可以使用Stream API来迭代ArrayList中的元素。流允许我们在处理每个元素时对它们执行更多操作。
arraylist.stream().forEach(e -> {
System.out.println(e);
});
5.2. 过滤元素
流(Stream)过滤帮助我们找到与特定条件匹配的列表子集。例如，我们可以从数字列表中找到所有偶数如下所示：
ArrayList<Integer> numbersList = new ArrayList<>(List.of(1, 2, 3, 4, 5));
numbersList.stream()
.filter(n -> n % 2 == 0)
.forEach(System.out::println); // 2 4
5.3. 使用reduce()减少元素
归约操作对于使用流处理列表中的每个元素并将结果收集到另一个列表中非常有帮助。请注意，原始流可以来自任何数据结构/集合类型，toList()方法在处理流后始终返回结果列表。
ArrayList<Integer> numbersList = new ArrayList<>(List.of(1, 2, 3, 4, 5));
List<Integer> evenNumList = numbersList.stream()
.filter(n -> n % 2 == 0)
.toList();
在上面的示例中，EvenNumList是可变的并且类型为List。如果我们想专门收集ArrayList实例中的元素，我们可以使用Collectors.toCollection(ArrayList::new)创建一个新的ArrayList并将元素收集到其中。
ArrayList<Integer> numbersList = new ArrayList<>(List.of(1, 2, 3, 4, 5));
ArrayList<Integer> evenNumList = numbersList.stream()
.filter(n -> n % 2 == 0)
.collect(Collectors.toCollection(ArrayList::new));
5.4. 使用map()映射元素
Stream.map()操作可以帮助以简洁的方式对流的每个元素应用特定的逻辑。例如，在数字流中，我们可以将每个数字平方并收集到一个新列表中。
List<Integer> squareList = numbersList.stream()
.map(n -> n * n)
.toList();
System.out.println(squareList); // [1, 4, 9, 16, 25]
6. 对 ArrayList 进行排序
处理从其他来源接收的数据时，排序是一项重要任务。要对ArrayList进行排序，我们可以利用Collections.sort()进行自然排序，或者通过实现Comparable或Comparator接口来实现自定义排序顺序。
6.1. 使用Collections.sort()进行自然排序
Collections.sort ()根据其元素的自然顺序对指定列表进行升序排序。列表中的所有元素都必须实现Comparable接口。
ArrayList<Integer> arrayList = new ArrayList<>(List.of(2, 1, 4, 5, 3));
Collections.sort(arrayList);
System.out.println(arrayList); // [1, 2, 3, 4, 5]
对于自定义对象，我们可以通过实现Comparable接口来定义自定义对象中的自然顺序。
class Item implements Comparable <Item>{
long id;
String name;
//...
@Override
public int compareTo(Item item) {
if(item.getName() == null || this.getName() == null){
return -1;
}
return item.getName().compareTo(this.getName());
}
}
6.2. 自定义排序Comparator接口
我们可以使用Comparator实例应用自定义的排序顺序。我们可以使用内置的Comparators，如Comparator.reverseOrder()，或者我们可以创建自己的实现。
Collections.sort(arrayList, Comparator.reverseOrder());
System.out.println(arrayList); // [5, 4, 3, 2, 1]
要创建自定义Comparator，我们可以通过根据需求比较适当的字段来创建一个实例，并将比较器传递给 sort() 方法。以下示例按自然顺序比较项目的名称。
ArrayList<Integer> itemList = ...;
Comparator<Item> customOrder = Comparator.comparing(Item::getName);
Collections.sort(itemList, customOrder);
7. 在ArrayList中搜索元素
7.1. 使用 contains()、indexOf() 和 lastIndexOf() 进行线性搜索
ArrayList中与搜索相关的方法通过逐个迭代元素来执行线性搜索，直到找到所需元素或到达列表末尾。
一般来说，在ArrayList中查找元素有以下3种方法：
contains(e)：如果列表至少包含一个指定元素，则返回 true ，否则返回false。indexOf(e)：返回列表中指定元素第一次出现的索引，或者-1如果此列表不包含该元素。lastIndexOf(e)：返回列表中最后一次出现的指定元素的索引-1，或者如果此列表不包含该元素。
ArrayList<Integer> numList = new ArrayList<>(List.of(1, 2, 2, 3, 4, 4, 4, 5));
System.out.println( numList.contains(2) ); //true
System.out.println( numList.contains(8) ); //false
System.out.println( numList.indexOf(4) ); //4
System.out.println( numList.lastIndexOf(4) ); //6
7.2. 使用Collections.binarySearch()进行二分搜索
在大型数组列表中，我们可以利用Collections.binarySearch()方法利用二分搜索算法来提高性能。
请注意，必须对列表进行排序才能使二分搜索正常工作。
另外，如果列表包含多个等于指定对象的元素，则不能保证一定能找到一个。例如，在numList中，元素 4 出现了 3 次。此方法可以返回 3 个元素中任意一个的索引。
ArrayList<Integer> numList = new ArrayList<>(List.of(1, 2, 2, 3, 4, 4, 4, 5));
Collections.sort(numList);
int foundIndex = Collections.binarySearch(numList, 4); //5
8. 同步和线程安全
ArrayList类不是线程安全的。在并发环境中使用它可能会产生不一致的结果。我们可以使用以下技术来创建线程安全的数组列表。
8.1. 使用Collections.synchronizedList()使ArrayList线程安全
Collections.synchronizedList()方法返回由指定列表支持的同步（线程安全）列表。所有方法都将被同步，并可用于并发环境中的添加/删除操作。
ArrayList<String> arrayList = new ArrayList<>();
List<String> synchronizedList = Collections.synchronizedList(arrayList);
synchronizedList.add("a"); //thread-safe operation
请注意，尽管所有 add/remove/get/set 方法都是线程安全的，但迭代器仍然不是线程安全的，必须手动同步。
List<String> synchronizedList = Collections.synchronizedList(arrayList);
...
synchronized (synchronizedList) {
Iterator i = synchronizedList.iterator(); // Must be in synchronized block
while (i.hasNext()) {
foo(i.next());
}
}
8.2. 使用CopyOnWriteArrayList进行并发访问
CopyOnWriteArrayList是ArrayList的线程安全变体，其中所有可变操作（add、set等）都是通过创建底层数组的新副本来实现的。
当迭代次数远远超过可变操作时，CopyOnWriteArrayList是一个很好的替代方案。当您不能或不想同步遍历，但需要排除并发线程之间的干扰时，它非常有用。
ArrayList<String> arrayList = new ArrayList<>();
OnWriteArrayList<String> concurrentList = new CopyOnWriteArrayList<>(arrayList);
//all operations are thread-safe
concurrentList.add("a");
for (String token : concurrentList) {
System.out.print(token);
}
值得庆幸的是，因为CopyOnWriteArrayList在每次变异操作中都会创建一个新的数组副本，所以即使其他线程正在修改列表，我们也不会遇到ConcurrentModificationException异常。
9. ArrayList 的子列表
9.1. 使用subList()
subList (fromIndex, toIndex)fromIndex方法返回此列表中指定的、包含的和toIndex不包含的部分的视图。如果fromIndex和toIndex相等，则返回列表为空。
ArrayList<Integer> origList = new ArrayList<>(List.of(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
List<Integer> subList = origList.subList(2, 6); // [2, 3, 4, 5]
请注意，返回的列表由原始列表支持，因此子列表中的所有添加/删除更改都会反映在原始列表中，反之亦然。
subList.add(10);
System.out.println(origList); // [0, 1, 2, 3, 4, 5, 10, 6, 7, 8, 9]
9.2. 使用流
如果我们想要一个仅包含符合特定条件的元素的子列表，也可以使用list.stream ().filter(…).toList(…) 。它不需要传递 from 和 to 索引。
ArrayList<Integer> origList = new ArrayList<>(List.of(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
List<Integer> subListWithStream = origList.stream()
.filter(n -> n % 2 == 0)
.toList();
10. ArrayList操作的性能和时间复杂度
ArrayList操作的性能因方法而异。不需要移动其他元素或调整列表大小的方法在 O(1) 下执行效果最好，而其他方法在需要移动数组中的所有元素时在最坏情况下执行 O(n) 。
add(e)：需要 O(1) 的常量时间，因为它总是附加在列表的末尾。然而，在最坏的情况下，如果发生大小调整，时间复杂度为 O(n)，其中 n 是 ArrayList 的当前大小。add(index, e)和remove(e)：时间复杂度为 O(n)，因为它可能需要移动现有元素。get(i)和set(i, e)：由于对元素进行直接基于索引的访问，因此具有 O(1) 的恒定时间复杂度。contains()、indexOf()和lastIndexOf(): 的时间复杂度为 O(n)，因为它们内部使用线性搜索。
11. 常见问题解答
11.1. ArrayList和Array的区别
在 Java 中，数组和 arraylist 都用于将元素集合存储为有序集合，并提供对元素的基于索引的访问。正如所讨论的，仍然存在一些差异：
- 数组是固定大小的数据结构，一旦创建就无法更改。arraylist 充当可调整大小的数组，当我们从中添加/删除元素时，它会动态增长/收缩。
- ArrayList使用泛型提供类型安全。数组不安全地提供此类类型，并且可能在运行时导致ClassCastException。
- ArrayList是 Collections 框架的一部分，因此提供了内置的实用方法，可以透明地存储和检索其中的元素。使用数组时，我们需要手动迭代并跟踪数组索引和元素类型。
11.2. ArrayList和LinkedList的区别
虽然ArrayList和LinkedList，两者在功能上看起来相同，但它们在存储和处理元素的方式上有很大不同。
- ArrayList实现为动态数组，而LinkedList实现为双向链表，其中每个元素（节点）包含数据以及对列表中前一个和下一个元素的引用。
- 在添加操作期间，如果达到列表大小限制，则执行调整大小。在LinkedList中，不需要调整大小，因为新元素总是作为节点添加，并且仅调整下一个和上一个引用。
- ArrayList需要更少的内存，因为它将元素存储在数组中并使用数组索引来跟踪它们。LinkedList需要更多内存，因为它需要维护对上一个和下一个元素的引用。
- 当列表迭代数量超过突变数量时，ArrayList是合适的。当突变比迭代更多时，LinkedList 的性能会更好。
12. 结论
Java ArrayList 类是一个优秀的实用程序类，用于按插入顺序存储元素并对它们执行各种操作。作为集合框架的一部分，它变得更具吸引力，因为它与其他类、接口和流集成得很好。
