JAVA小知识20：万字详解List与ArrayList

一、集合简介

1.1、什么是集合？

可同时存储多个元素的数据结构就是集合。

1.2、为什么要有集合？

我们可以使用数组同时存储多个元素，但是数组有个弊端。数组创建之后长度就会固定，如需扩容则需要手动扩容，我们需要一个长度可变的新的容器（自动扩容）。

1.3、集合与数组的区别

数组可以存储基本数据类型，也可以存储引用数据类型。但是集合是不能直接存储基本数据类型的，需要把它转化为对应的包装类。

1.4、集合都有什么？

Java 集合框架可以分为两条大的支线：Collection接口与Map接口

• Collection接口：
  • List接口：有序集合，允许重复元素。
    • ArrayList：基于动态数组实现，支持快速随机访问。
    • LinkedList：基于双向链表实现，适合频繁插入和删除操作。
• Set接口：无序集合，不允许重复元素。
  • HashSet：基于哈希表实现，元素无序。
  • LinkedHashSet：继承自HashSet，维护插入顺序。
  • TreeSet：基于红黑树实现，元素有序。
• Queue接口：用于处理先进先出(FIFO)的队列。
  • PriorityQueue：基于堆实现的优先级队列，元素按自然顺序或指定的Comparator排序。
• Deque接口：双端队列，支持在两端插入和删除元素。
  • ArrayDeque：基于数组实现的双端队列。
  • LinkedList：也实现了Deque接口。
• Map接口：
  • HashMap：基于哈希表实现，键值对无序。
  • LinkedHashMap：继承自HashMap，维护插入顺序。
  • TreeMap：基于红黑树实现，键值对有序。

我们引用一张图片就能很好地来解释上面的文字：

今天我们要研究的目标是List这条分支，也是我们开发中最常用的一种集合。

二、List

2.1、List简介

List接口是Java集合框架中的一部分，提供了一组有序的、可重复的元素集合。List接口继承自Collection接口，并在其基础上添加了允许精确控制元素插入位置的操作。

java.util.Collection 接口是 Java 集合框架的根接口之一，它定义了一组通用的方法，用于操作集合中的元素。Collection 接口是 Java 集合框架中所有集合类的共同父接口。

2.2、主要特点

• 有序性：List接口保证元素的插入顺序，即元素的迭代顺序与插入顺序一致。
• 可重复性：List接口允许存储重复的元素。
• 索引访问：List接口提供了基于索引的位置访问元素的能力，类似于数组。

2.3、主要实现类

List接口有几个常用的实现类，每个类有其特定的特点和使用场景：

• ArrayList：
  • 基于动态数组实现，支持快速随机访问。
  • 适合频繁读取元素的场景。
  • 插入和删除操作相对较慢，尤其是在列表中间插入或删除时。
• LinkedList：
  • 基于双向链表实现，适合频繁插入和删除操作。
  • 读取速度较慢，因为需要从头遍历到指定位置。
  • 也实现了Deque接口，可以用作双端队列。

2.4、实现类对比

• ArrayList：适用于随机访问频繁的场景，因为基于数组的实现提供了快速的索引访问。
• LinkedList：适用于插入和删除操作频繁的场景，因为基于链表的实现提供了更高效的插入和删除操作。

2.5、为什么要用实现类？

在 Java 中，List 是一个接口（java.util.List），而不是一个具体的类。接口本身不能直接实例化为对象，因为它只是一组方法的声明，没有实际的方法实现。所以我们要想实现List，就要做一个向上造型，其中 ArrayList 是 List 接口的子类。将 ArrayList 类的对象赋值给 List 接口的引用，这是一种向上造型操作。这允许各位程序员使用 List 接口的方法来操作 ArrayList 对象，因为 ArrayList 实现了 List 接口，所以它是 List 接口的一个实例。

三、ArrayList

ArrayList 在数组的基础上实现了自动扩容，并且提供了比数组更丰富的预定义方法（各种增删改查），非常方便我们在开发中的使用。

3.1、创建ArrayList

先来看看List的源码：

我们可以看到List确确实实是继承了Collection，并且他也是一个接口，而且他还有个泛型（关于泛型的知识在java小知识19里面可以看看）。下面我们来看构造方法：

那我们如何初始化一个ArrayList集合呢？下面有两种方法，我们常用的为方法一。我们可以看到泛型（泛型只能是引用数据类型）里面规定了这个集合只能存储Integer包装类的数据。

3.2、ArrayList的成员方法

讲完了如何创建一个ArrayList我们来讲讲如何使用ArrayList

3.3、ArrayList的特性

1. 动态数组： ArrayList是基于动态数组实现的，它允许存储和操作一个可变数量的元素。数组的容量会自动增长或减少，以适应元素的添加和删除操作，因此无需手动管理数组的大小。
2. 有序性： ArrayList 是有序集合，它以元素插入的顺序来维护元素的顺序。这意味着可以按照添加元素的顺序来访问和遍历元素。
3. 允许重复元素： ArrayList 允许存储重复的元素，即同一个元素可以在列表中出现多次。
4. 随机访问： 由于 ArrayList 基于数组实现，因此它支持随机访问。可以通过索引来直接访问列表中的元素。
5. 线程不安全： ArrayList 不是线程安全的，这意味着在多线程环境下，如果多个线程同时访问和修改同一个 ArrayList 实例，可能会导致数据不一致或异常。如果需要在多线程环境中使用，可以考虑使用 Collections.synchronizedList() 方法来获得一个线程安全的 ArrayList。
6. 性能： 由于 ArrayList 支持随机访问，因此对于需要频繁访问元素的场景非常高效。然而，在需要频繁插入或删除元素的情况下，性能可能较差，因为这涉及到数组元素的移动。
7. 动态扩容： 当 ArrayList 内部数组的容量不足以容纳新元素时，它会自动扩展数组的大小，通常是当前容量的一半。这可以避免频繁的数组重新分配操作，提高了性能。

四、ArrayList成员方法详解

4.1、add()：将元素插入到指定位置的 ArrayList 中。

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add(1, "Banana"); // 在索引1处插入
System.out.println(list); // 输出: [Apple, Banana]

4.2、addAll()：添加集合中的所有元素到 ArrayList 中。

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
List<String> moreFruits = Arrays.asList("Banana", "Orange");
list.addAll(moreFruits);
System.out.println(list); // 输出: [Apple, Banana, Orange]

4.3、clear()：删除 ArrayList 中的所有元素。

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.clear();
System.out.println(list); // 输出: []

4.4、clone()：复制一份 ArrayList。

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
ArrayList<String> clonedList = (ArrayList<String>) list.clone();
System.out.println(clonedList); // 输出: [Apple]

4.5、contains()：判断元素是否在 ArrayList 中。

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
boolean hasApple = list.contains("Apple");
System.out.println(hasApple); // 输出: true

4.6、get()：通过索引值获取 ArrayList 中的元素。

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
String fruit = list.get(0);
System.out.println(fruit); // 输出: Apple

4.7、indexOf()：返回 ArrayList 中元素的索引值。

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
int index = list.indexOf("Banana");
System.out.println(index); // 输出: 1

4.3、removeAll()：删除存在于指定集合中的 ArrayList 里的所有元素。

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.add("Orange");
List<String> toRemove = Arrays.asList("Banana", "Orange");
list.removeAll(toRemove);
System.out.println(list); // 输出: [Apple]

4.3、remove()：删除 ArrayList 里的单个元素。

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.remove("Apple");
System.out.println(list); // 输出: []

4.3、size()：返回 ArrayList 里元素数量。

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
int size = list.size();
System.out.println(size); // 输出: 1

4.3、isEmpty()：判断 ArrayList 是否为空。

ArrayList<String> list = new ArrayList<>();
boolean empty = list.isEmpty();
System.out.println(empty); // 输出: true

4.3、subList()：截取部分 ArrayList 的元素。

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.add("Orange");
List<String> subList = list.subList(1, 3);
System.out.println(subList); // 输出: [Banana, Orange]

4.3、set()：替换 ArrayList 中指定索引的元素。

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.set(0, "Banana");
System.out.println(list); // 输出: [Banana]

4.3、sort()：对 ArrayList 元素进行排序。

ArrayList<String> list = new ArrayList<>();
list.add("Banana");
list.add("Apple");
list.sort(String::compareTo);
System.out.println(list); // 输出: [Apple, Banana]

4.3、toArray()：将 ArrayList 转换为数组。

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
Object[] array = list.toArray();
System.out.println(Arrays.toString(array)); // 输出: [Apple]

4.3、toString()：将 ArrayList 转换为字符串。

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
String str = list.toString();
System.out.println(str); // 输出: [Apple]

4.3、ensureCapacity()：设置指定容量大小的 ArrayList。

ArrayList<String> list = new ArrayList<>();
list.ensureCapacity(100);
list.add("Apple");
System.out.println(list); // 输出: [Apple]

4.3、lastIndexOf()：返回指定元素在 ArrayList 中最后一次出现的位置。

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.add("Apple");
int lastIndex = list.lastIndexOf("Apple");
System.out.println(lastIndex); // 输出: 2

4.3、retainAll()：保留 ArrayList 中在指定集合中也存在的那些元素。

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
List<String> toRetain = Arrays.asList("Apple");
list.retainAll(toRetain);
System.out.println(list); // 输出: [Apple]

4.3、containsAll()：查看 ArrayList 是否包含指定集合中的所有元素。

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
List<String> toCheck = Arrays.asList("Apple", "Banana");
boolean containsAll = list.containsAll(toCheck);
System.out.println(containsAll); // 输出: true

4.3、trimToSize()：将 ArrayList 中的容量调整为数组中的元素个数。

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.trimToSize();
System.out.println(list); // 输出: [Apple]

4.3、removeRange()：删除 ArrayList 中指定索引之间存在的元素。

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.add("Orange");
list.subList(1, 2).clear(); // 删除索引1到2之间的元素
System.out.println(list); // 输出: [Apple, Orange]

4.3、replaceAll()：将给定的操作内容替换掉数组中每一个元素。

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.replaceAll(fruit -> fruit.toUpperCase());
System.out.println(list); // 输出: [APPLE, BANANA]

4.3、removeIf()：删除所有满足特定条件的 ArrayList 元素。

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.removeIf(fruit -> fruit.startsWith("A"));
System.out.println(list); // 输出: [Banana]

4.3、forEach()：遍历 ArrayList 中每一个元素并执行特定操作。

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.forEach(fruit -> System.out.println(fruit));

五、ArrayList的扩容机制

结合源码我们来讲一下ArrayList的扩容机制

第一步：创建ArrayList对象

首先我们来看一下创建一个ArrayList对象的时候都发生了什么

public static void main(String[] args) {
    List<String> list = new ArrayList<>();
}

ArrayList在底层有一个数组，他的名字叫做elementData，他还有一个成员变量size记录元素的个数。

如果利用空参的构造方法或者参数为0的情况下，在底层他会默认创建一个长度为0的数组


也就是说我们创建一个空参ArrayList对象时候，他的数组长度为0

第二步、添加元素

我们来看看当向ArrayList集合中添加第一个元素时候发生了什么。

当第一次添加元素时，ArrayList 会检查是否需要扩容。在 add 方法中，会调用ensureCapacityInternal 方法来确保容量足够：

然后我们来看那可能这个ensureCapacityInternal(size + 1); 方法是怎么来保证容量是足够的。

当我们刚刚创建这个ArrayList的时候，他的size值为0，而+1之后参数就为1。
此时，就变成了ensureCapacityInternal(1)
ensureCapacityInternal()方法会调用 ensureExplicitCapacity 来判断是否需要扩容：

此时又来了一个方法，我们先看看这个calculateCapacity(elementData, minCapacity)都干了什么？

两个参数，一个是底层数组，一个是刚刚传过来的size+1，底层数组在初始化的时候赋值的就是空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA，所以满足if条件
而这个DEFAULT_CAPACITY这个常量在源码中的默认值就是10。minCapacity的值为1。所以会返回10。

说完了calculateCapacity(elementData, minCapacity)我们接着来看最外层的ensureExplicitCapacity()都干了什么？

第三步、扩展数组

重点来了！！！可以看到初始数组长度为0，进入到了grow()函数，这个函数就是扩容函数，我们来详细的分析看看。

先上完整代码：

1、变量初始化

// overflow-conscious code
int oldCapacity = elementData.length;

elementData.length 表示当前 ArrayList 内部数组的长度，即当前容量。
oldCapacity 就是当前数组的长度，即当前 ArrayList的容量。
2、计算新容量

int newCapacity = oldCapacity + (oldCapacity >> 1);

oldCapacity >> 1 是对 oldCapacity 进行右移一位的操作，相当于 oldCapacity / 2。这一步是为了将当前容量增加 50%。
newCapacity 就是计算出来的新容量，通常是当前容量的1.5倍。
3、调整新容量

if (newCapacity - minCapacity < 0)
   newCapacity = minCapacity;

这里判断如果 newCapacity(计算后的新容量) 小于 minCapacity(参数)，则将newCapacity设置为 minCapacity。这是为了确保扩容后的容量至少能够满足 minCapacity，即确保能够容纳至少 minCapacity 个元素。
4、最大容量限制

if (newCapacity - MAX_ARRAY_SIZE > 0)
   newCapacity = hugeCapacity(minCapacity);

MAX_ARRAY_SIZE 是 ArrayList 内部定义的一个常量，表示数组的最大容量。如果 newCapacity 超过了 MAX_ARRAY_SIZE，则调用hugeCapacity方法进行处理，通常是返回一个较大的合理容量。
5、扩容操作

// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);

·Arrays.copyOf ·方法用于将 ·elementData· 数组扩展到 ·newCapacity ·的大小，并复制原数组的内容到新数组中。这一步实现了真正的扩容操作。

关于这个copyof可以看一下我的java小知识18有讲过，这里也直接贴出截图：

六、关于ArrayList的一些问答

6.1 ArrayList的扩容机制

上面五讲过了

6.2 ArrayList频繁扩容导致性能下降问题

问题：
假设现在需要添加10w条数据，可能时间上很快，不到1s就能添加完，但是这其中ArrayList就会扩容n次，并且重复拷贝n次，这样的操作非常的占用我们的内存开销。
答案：
可以使用有参构造来创建ArrayList，然后添加元素。看下列示例，同样添加10w条数据。

public static void main(String[] args) {
    long t1 = System.currentTimeMillis();
    List<String> list = new ArrayList<>();
    for(int i=0; i<100000; i++) {
        list.add(i+"a");
    }
    long t2 = System.currentTimeMillis();
    System.out.println("方法一运行："+(t2 - t1)+"毫秒");
    long t3 = System.currentTimeMillis();
    List<String> list2 = new ArrayList<>(100000);
    for(int i=0; i<100000; i++) {
        list2.add(i+"a");
    }
    long t4 = System.currentTimeMillis();
    System.out.println("方法二运行："+(t4 - t3)+"毫秒");
}