概述

List 是 Java 中的一种有序、可重复的集合接口类型。其常用的实现类有：

ArrayList：动态数组。
LinkedList：链表。

ArrayList 和 LinkedList 的区别

ArrayList 和 LinkedList 的区别主要体现在数据结构、用途、是否支持随机访问、内存占用等方面。

数据结构

ArrayList 基于数组实现。
LinkedList 基于（双向）链表实现。

适用性

查找访问：ArrayList 在使用下标进行查找时更有优势。

ArrayList 调用 get(int index) 方法时可以直接通过数组下标获取元素，查找的时间复杂度是 $O(1)$；
LinkedList 调用 get(int index) 方法时需要按顺序遍历链表，查找的时间复杂度是 $O(n), \space n = index$。

如果使用 List<E>#get(E element) 方法进行查找，这两种类型的集合都需要对集合中的元素进行遍历，并通过元素的 equals() 方法进行比较。所以使用 get(E element) 时间复杂度都是 $O(n)$。

增删操作：LinkedList 在增删时更有效率。

ArrayList：
- 在尾部进行增删：一般情况下，直接在数组尾部进行插入或删除，时间复杂度是 $O(1)$；当 add() 操作涉及到扩容时，时间复杂度会提升到 $O(n)$。
- 在中间或头部进行增删：在数组中间进行插入（或删除）时，需要对插入（或删除）元素位置后的其它所有元素向后（或向前）移动一个位置，并且在插入时还有可能触发扩容，时间复杂度为 $O(n)$。
- 使用 remove(Object o) 进行删除：需要进行遍历，找到对应元素，时间复杂度为 $O(n)$。
在扩容时，需要将元素从原数组复制到新数组上，这一步骤的时间复杂度为 $O(n)$。
LinkedList：链表结构的插入和删除操作只需要改变对应节点（例如前置、后置或插入节点）的引用，不需要移动元素。
- 在头部或尾部进行增删：时间复杂度是 $O(1)$。
- 在中间进行增删：需要遍历链表找到插入位置，时间复杂度是 $O(n)$。
- 使用 remove(Object o) 进行删除：需要进行遍历，找到对应元素，时间复杂度为 $O(n)$。

LinkedList 更利于增删不是体现在时间复杂度上，因为二者增删的时间复杂度都是 $O(n)$，都有可能需要遍历列表。LinkedList 在增删上的优势体现在操作效率上，因为 LinkedList 的增删只需要改变引用，而 ArrayList 的增删可能需要移动元素。

所以，ArrayList 适合于频繁的随机访问和较少的增删操作，而 LinkedList 适合于频繁的增删操作和较少的随机访问。

随机访问

ArrayList 是基于数组的，并实现了 RandomAccess 接口，支持随机访问，可通过下标直接获取元素。
LinkedList 是基于链表的，需要按顺序遍历访问，无法根据下标直接获取元素，不支持随机访问，并没有实现 RandomAccess 接口。

RandomAccess 接口是一个标记接口（Marker Interface）。这个接口并没有定义任何方法，它存在的主要目的是为了指示实现这个接口的列表（List）支持随机访问。

内存占用

ArrayList 是基于数组的，是一块连续的内存空间，在内存空间中的结构紧凑。但如果涉及到扩容，就会重新分配内存。默认情况下是将空间增加到原来的 1.5 倍，存在一定的空间浪费。
LinkedList 是基于双向链表的，每个节点都有一个指向下一个（后置）节点和上一个（前置）节点的引用，在内存空间中的结构是松散的。因为每个节点都需要额外记录前置和后置节点的引用，所以占用的内存空间比起同样大小的数组来说会稍微大一点。

ArrayList

扩容机制

ArrayList 的底层是基于动态数组实现。当往 ArrayList 中添加元素时，会先检查是否需要扩容，如果 $当前容量+1$ 超过数组长度，就会进行扩容。一般情况下，扩容后的新数组长度是原来的 1.5 倍，然后再把原数组的值拷贝到新数组中。

注意：ArrayList 的容量（$c$）和长度（$l$）是两个概念，容量并不一定等于其长度，它们的关系是 $l \le c$。

ArrayList#grow(int) 方法用于计算扩容后的容量大小。

private void grow(int minCapacity) {
  // overflow-conscious code
  int oldCapacity = elementData.length;
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  if (newCapacity - minCapacity < 0)
      newCapacity = minCapacity;
  if (newCapacity - MAX_ARRAY_SIZE > 0) // 超出索引的最大值
      newCapacity = hugeCapacity(minCapacity);
  // minCapacity is usually close to size, so this is a win:
  elementData = Arrays.copyOf(elementData, newCapacity);
}

序列化和反序列化机制

在 ArrayList 的定义中可以发现有如下内容：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

    /* ... */
    
    transient Object[] elementData;

    /**
     * 将 ArrayList 实例的状态保存到流中(序列化, Serialize).
     */
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // modCount 快照, 用于后续判断是否有并发处理
        int expectedModCount = modCount;
        // 序列化没有标记为 static、transient 的字段, 包括 size 等
        s.defaultWriteObject();

        s.writeInt(size);

        // 按顺序序列化元素的前 size 个元素
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }

        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

    /**
     * 从流重新构造 ArrayList 实例(反序列化, Deserialize).
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        // 反序列化没有标记为 static、transient 的字段, 包括 size 等
        s.defaultReadObject();

        // 读取最大容量
        s.readInt(); // ignored

        if (size > 0) {
            // 就像 clone() 方法一样, 基于大小而不是最大容量进行扩容
            int capacity = calculateCapacity(elementData, size);
            SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // 按顺序反序列化前 size 个元素, 并填充到数组中
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }
}

错误检测机制

快速失败（fail-fast）和安全失败（fail-safe）是 Java 集合框架中处理和迭代时使用的两种不同的错误检测机制，主要用于处理多线程环境下的并发访问问题。

快速失败（fail-fast）

快速失败是一种设计模式。Java 中的安全失败是指在用迭代器遍历一个集合对象时，如果当前线程在遍历过程中，其它线程对集合对象的内容进行了修改（增删改），则会抛出 ConcurrentModificationException，终止迭代操作。这种机制确保了对并发修改的快速响应，避免了潜在的不一致状态。

原理：通过成员变量 modCount 实现。modCount 在 AbstractList 中被定义：

protected transient int modCount = 0;

每当 ArrayList 的内容发生结构性变化时，如添加、删除元素或清空列表等操作，modCount 的值就会递增。

当创建一个迭代器时，迭代器会保留一个对 modCount 的快照（通常命名为 expectedModCount），用于在迭代过程中比较。每次迭代器访问元素前后，都会检查modCount是否仍然等于迭代器创建时的 expectedModCount。如果这两个值不相等，说明在迭代过程中集合已经被其他线程修改，这时迭代器会立即抛出 ConcurrentModificationException 异常，阻止进一步的迭代操作。

例如上方 ArrayList 序列化过程中对 modCount 进行检测：

// modCount 快照, 用于后续判断是否有并发处理
int expectedModCount = modCount;

/* 遍历... */

// 当遍历前后 modCount 的值被改变, 说明当前集合实例被修改了
// 于是抛出 ConcurrentModificationException
if (modCount != expectedModCount) {
    throw new ConcurrentModificationException();
}

当迭代器使用 next() 遍历下一个元素之前，会检测 modCount 变量是否为 expectedmodCount 值，是的话就返回遍历；否则抛出异常，终止遍历。

例如 ArrayList 的 Iterator 是使用内部私有类实现的：

private class Itr implements Iterator<E> {
    int cursor;       // 下一个元素的索引
    int lastRet = -1; // 最后一个元素的索引, 如果没用元素则返回 -1
    /**
     * 在创建 Iterator 时会保存一次快照, 当调用其它方法如 remove()、
     * ListIterator#add(E) 时会再次保存 modCount 的快照
     */
    int expectedModCount = modCount;

    @SuppressWarnings("unchecked")
    public E next() {
        // 在遍历前检查 modCount
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }

    /* ... */
}

注：

不能依赖于 ConcurrentModificationException 是否被抛出判断集合是否有并发操作。ConcurrentModificationException 仅是保证集合在遍历过程中结构没用被其它线程修改，只建议用于检测并发修改。

java.util 包下的集合类都是快速失败的，不能在多线程环境下发生并发修改（迭代过程中被修改），如 ArrayList、HashMap，以及它们的标准迭代器。

安全失败（fail-safe）

安全失败机制被设计用于在并发访问过程中，即使集合正在被迭代，其他线程对集合的修改也不会影响迭代过程，不会抛出异常。

采用安全失败机制的集合容器，在遍历时不是直接在原始集合内容上访问的，而是在遍历前先创建原始集合的副本或视图，在副本或视图的集合上进行遍历。在遍历过程中对原始集合所作的修改并不能被迭代器检测到，因此原集合的修改不会影响到迭代过程，不会触发 ConcurrentModificationException。

缺点：基于拷贝副本进行遍历的优点是避免了 ConcurrentModificationException 被触发，但同样地，迭代器在遍历过程中并不能访问到集合修改后的内容。即，遍历期间原始集合发生的修改迭代器检测不到，迭代器可能获取不到实时的集合状态。

注：java.util.concurrent 包下的容器都是安全失败的，可以在多线程下并发使用，并发修改，如 CopyOnWriteArrayList 和 ConcurrentHashMap.KeySetView 等并发集合类。

线程安全

线程安全是指在多线程环境下，集合能够正确地处理并发访问，确保数据的一致性和完整性。安全失败仅仅只是实现线程安全集合的一个方面，但仅凭安全失败这一点不足以断言一个集合就是线程安全的。集合是否线程安全还需看其是否在所有操作上都能正确地处理并发场景，包括添加、删除、查询等。

Collections.synchronizedList()

一种方式是使用 Collections.synchronizedList() 方法，它将返回一个线程安全的 List。

List<Object> synchronizedList = Collections.synchronizedList(new ArrayList<>());

在 Collections.synchronizedList() 方法中，使用了两个 Collections 的静态子类 SynchronizedRandomAccessList 和 SynchronizedList 来实现线程安全的 List：

public static <T> List<T> synchronizedList(List<T> list) {
    return (list instanceof RandomAccess ?
            new SynchronizedRandomAccessList<>(list) :
            new SynchronizedList<>(list));
}

/**
 * 支持随机访问的线程安全 List
 */
static class SynchronizedRandomAccessList<E>
    extends SynchronizedList<E>
    implements RandomAccess {/* ... */}

/**
 * 普通的线程安全 List
 */
static class SynchronizedList<E>
    extends SynchronizedCollection<E>
    implements List<E> {/* ... */}

在 SynchronizedList 和 SynchronizedRandomAccessList 内部，是通过 synchronized 关键字加锁来实现的。Java 中，synchronized 关键字是一种用于控制多线程并发访问共享资源的同步机制，它提供了一种锁的实现，保证了在任何时刻，只有一个线程可以执行特定的代码块或方法。synchronized 可以用于方法或代码块上，确保线程间的互斥访问，防止数据的不一致性问题。
同步方法：
public synchronized void synchronizedMethod() {
    /* ... */
}
同步代码块:
synchronized(对象引用) {
    /* 需要同步的代码块... */
}

Collections 类是 Java 标准库中的一个工具类，它提供了大量的静态方法，用于执行各种集合操作。在 Collections 提供了一系列实现 synchronized 集合的方法：

synchronizedCollection()

synchronizedSortedSet()

synchronizedNavigableSet()

synchronizedList()

synchronizedMap()

synchronizedSortedMap()

synchronizedNavigableMap()

synchronizedNavigableMap()

写时复制 CopyOnWriteArrayList

另一种方式是基于写时复制（Copy-On-Write, COW）原则实现线程安全的 List。写时复制是指每当对列表进行修改（添加、删除或更改元素）时，都会创建列表的一个新副本，这个新副本会替换旧的列表，而对旧列表的所有读取操作仍然可以继续。Java 中的 CopyOnWriteArrayList 就是基于写时复制来实现线程安全的。

CopyOnWriteArrayList<Object> list = new CopyOnWriteArrayList<>();

CopyOnWriteArrayList<Object> copyOnWriteArrayList = new CopyOnWriteArrayList<>(new ArrayList<>());

但对于写操作来说，

优点：

CopyOnWriteArrayList 采用了一种读写分离的并发策略。CopyOnWriteArrayList 容器允许并发读，读操作是无锁的，性能较高。

缺点：

写操作开销大：每次写操作都需要复制整个数据结构或数据页，开销较大，对于大数据集或频繁写入的情况，这可能成为性能瓶颈。
数据不一致：在写入操作完成并更新引用之前，其他线程看到的仍然是旧数据，可能导致短暂的数据不一致。

Java List

目录

概述

ArrayList 和 LinkedList 的区别

数据结构

适用性

随机访问

内存占用

ArrayList

扩容机制

序列化和反序列化机制

错误检测机制

快速失败（fail-fast）

安全失败（fail-safe）

线程安全

Collections.synchronizedList()

写时复制 CopyOnWriteArrayList

版权

评论

Java List

目录

概述

ArrayList 和 LinkedList 的区别

数据结构

适用性

随机访问

内存占用

ArrayList

扩容机制

序列化和反序列化机制

错误检测机制

快速失败（fail-fast）

安全失败（fail-safe）

线程安全

Collections.synchronizedList()

写时复制 CopyOnWriteArrayList

版权

相关文章

评论