Java 集合-List

本文将介绍 Java 集合中的 List。

一、什么是 List？

List，列表，用于储存一组可重复的、有序的对象。

二、常用方法

1. Collection 方法

2. 特有方法

方法 说明
add(index, obj) 将元素插入到 index 处
addAll(index, collection) 将集合中所有元素插入到 index 处
get(index) 返回 index 处的元素
indexOf(obj) 返回元素在集合中第一次出现的位置
lastIndexOf(obj) 返回元素在集合中最后一次出现的位置
remove(index) 删除并返回 index 处的元素
set(index, obj) 将 index 处的元素替换为指定元素
subList(fromIndex, toIndex) 返回从 fromIndex 到 toIndex 的所有元素组成的子集
replaceAll(UnaryOperator operator) 根据 operator 指定的计算规则重新设置集合中所有的元素
sort(Comparator comparator) 根据 comparator 对集合中元素进行排序

3. 迭代器特有方法

方法 说明
hasPrevious() 是否有上一个元素
previous() 返回上一个元素
add(obj) 插入元素

三、fail-fast 迭代

在使用迭代器迭代的过程中，如果对集合进行了修改，将导致迭代结果不正确。

例如在迭代过程中删除集合元素：

1
2
3
4
Iterator iterator = arrayList.iterator();
while (iterator.hasNext()) {
	arrayList.remove(0);
}

针对这一问题，AbstractList 提供了可选的 fail-fast 迭代方案，具体如下：

  • 在对象中维护一个成员属性 modCount
  • 假如对 List 进行修改，应该递增 modCount 值
  • 迭代器将会在迭代过程中检测 modCount 值，并在其异常改变后抛出错误

网上的一部分说法存在误区，fail-fast 迭代的目的不是解决多线程访问问题，而是为了解决单一线程在迭代过程中修改的问题。

在 JDK5、JDK6 中，modCount 有 volatile 修饰，但自 JDK7 以来，modCount 已不再添加 volatile 修饰符。因此，fail-fast 迭代不是为了解决多线程访问问题，并且也没有能力解决它。

四、ArrayList

1. 特点

  • 底层通过数组实现

  • 与普通数组相比，没有容量限制

    当容量不足时，会自动扩大数组大小

  • 与普通数组相比，只能存储对象

2. initialCapacity

initialCapacity 表示初始容量。

可以通过构造函数指定，如果没有指定，则初始容量默认为 10。

一般情况下无需关心此参数，随着元素的添加，ArrayList 会自动扩容。

3. 自动扩容

每次添加元素前，检查容量是否充足，在容量不足时扩容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class ArrayList<E> {
    
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!  [此注释说明ensureCapacityInternal方法会递增modCount，因此无需在add方法中额外再递增modCount]
        elementData[size++] = e;
        return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
        // 记录被修改次数
        modCount++;
        
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    /**
     * 计算容量
     * <p>当内置数组未初始化时，使其容量至少为10
     */
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    
    /**
     * 数组扩容
     */
    private void grow(int minCapacity) {
        // 将原容量扩大1.5倍作为新容量
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);  // 等效于扩大1.5倍，位运算速度更快
        // 检查新容量是否足够，如果不够，直接取最小所需容量作为新容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 将新容量限制在Integer.MAX_VALUE之下
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 创建新数组并将内容拷贝至其中
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

4. 手动扩容

ArrayList 提供了 ensureCapacity 方法，可以用它来手动扩容。

如果可以预知 list 的元素增加情况，应该手动将容量扩到合适大小，以避免元素添加过程中由 ArrayList 自行多次扩容而导致的性能损耗。

5. 手动缩容

可以通过 trimToSize 调整容量为当前元素个数，以减少空间占用。

6. fail-fast 迭代

ArrayList 支持 fail-fast 迭代机制。

五、LinkedList

1. 特点

  • 底层通过链表实现
  • 同时实现了 List、Deque 接口，因此既可以作为列表，又可以作为队列

参考