ArrayList与LinkedList

ArrayList 和 LinkedList 有什么区别？

1. 底层数据结构

ArrayList 基于 动态数组 实现，内存中是连续的存储空间。当数组容量不足时，会触发扩容（通常为原容量的1.5倍）。

LinkedList 基于 双向链表 实现，每个元素（节点）通过前后指针连接，内存中不要求连续存储。

2. 时间复杂度对比

操作	ArrayList	LinkedList
随机访问（get/set）	O(1)（通过索引直接访问）	O(n)（需遍历链表）
头部插入/删除	O(n)（需移动后续元素）	O(1)（修改指针）
尾部插入/删除	O(1)（均摊复杂度）	O(1)（直接操作尾节点）
中间插入/删除	O(n)（需移动元素）	O(n)（需遍历到位置）

多数情况下，ArrayList 更利于查找，LinkedList 更利于增删。

① 由于 ArrayList 是基于数组实现的，所以 get(int index) 可以直接通过数组下标获取，时间复杂度是 O(1)；LinkedList 是基于链表实现的，get(int index) 需要遍历链表，时间复杂度是 O(n)。

② ArrayList 如果增删的是数组的尾部，时间复杂度是 O(1)；如果 add 的时候涉及到扩容，时间复杂度会上升到 O(n)。

但如果插入的是中间的位置，就需要把插入位置后的元素向前或者向后移动，甚至还有可能触发扩容，效率就会低很多，变成 O(n)。

③ LinkedList 因为是链表结构，插入和删除只需要改变前置节点、后置节点和插入节点的引用，因此不需要移动元素。

如果是在链表的头部插入或者删除，时间复杂度是 O(1)；如果是在链表的中间插入或者删除，时间复杂度是 O(n)，因为需要遍历链表找到插入位置；如果是在链表的尾部插入或者删除，时间复杂度是 O(1)。

ArrayList 和 LinkedList 内存占用有何不同？

ArrayList 是基于数组的，是一块连续的内存空间，所以它的内存占用是比较紧凑的；但如果涉及到扩容，就会重新分配内存，空间是原来的 1.5 倍。

LinkedList 是基于链表的，每个节点都有一个指向下一个节点和上一个节点的引用，每个节点需要额外存储前后指针（每个元素多占用约12字节内存），内存开销更大。

ArrayList 和 LinkedList 的使用场景有什么不同？

• ArrayList 适用于：

随机访问频繁：需要频繁通过索引访问元素的场景。 读取操作远多于写入操作：如存储不经常改变的列表。 末尾添加元素：需要频繁在列表末尾添加元素的场景。

• LinkedList 适用于：

频繁插入和删除：在列表中间频繁插入和删除元素的场景。 不需要快速随机访问：顺序访问多于随机访问的场景。 队列和栈：由于其双向链表的特性，LinkedList 可以实现队列（FIFO）和栈（LIFO）。

ArrayList 的扩容机制了解吗？

① 当调用 add() 方法添加元素时，如果当前元素数量（size）等于数组长度（elementData.length），则会触发扩容。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 检查是否需要扩容
    elementData[size++] = e;
    return true;
}

② 扩容流程

步骤 1：计算最小所需容量

如果数组为空（初始容量为0），则最小容量取 默认容量（10） 和 所需容量（size+1） 的较大值。

否则直接取 size + 1。

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

步骤 2：决定是否扩容

如果 minCapacity 超过当前数组长度，则调用 grow() 方法扩容。

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

步骤 3：执行扩容（核心）

新容量 = 旧容量 + 旧容量 >> 1（即 1.5 倍，位运算比乘法高效）。

如果扩容后仍不足，则直接使用 minCapacity。

如果新容量超过 Integer.MAX_VALUE - 8，则调整为 Integer.MAX_VALUE（避免内存溢出）。

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍扩容
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity; // 特殊情况下直接使用minCapacity
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity); // 处理超大容量
    elementData = Arrays.copyOf(elementData, newCapacity); // 复制旧数据到新数组
}

③ 关键细节

默认初始容量：无参构造时，初始容量为 0（JDK 8+），首次添加元素时扩容到 10；指定容量构造时直接初始化对应大小。

扩容代价：每次扩容需将旧数组元素复制到新数组（Arrays.copyOf），时间复杂度为 O(n)。频繁扩容会影响性能，建议预估容量并初始化。

缩容机制：ArrayList 不会自动缩容，但可通过 trimToSize() 手动将数组调整为当前元素数量的大小。

④ 性能优化建议

预分配容量：若已知数据量较大，初始化时直接指定容量，避免多次扩容。

List<Integer> list = new ArrayList<>(1000); // 直接初始化为1000容量

避免无效扩容： 批量添加元素时，使用 addAll() 而非循环 add()，减少扩容次数。

了解 Java 快速失败（Fail-Fast）机制吗

快速失败（Fail-Fast）是 Java 集合框架中的一种错误检测机制，主要用于在多线程环境下快速发现并发修改问题。

在用迭代器遍历集合对象时，如果线程 A 遍历过程中，线程 B 对集合对象的内容进行了修改，就会抛出 Concurrent Modification Exception。

迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用 hashNext()/next()遍历下一个元素之前，都会检测 modCount 变量是否为 expectedmodCount 值，是的话就返回遍历；否则抛出异常，终止遍历。

异常的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果集合发生变化时修改 modCount 值刚好又设置为了 expectedmodCount 值，则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的 bug。

java.util 包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改），比如 ArrayList 类。

实现原理

1. modCount 机制

集合类内部维护一个 modCount（modification count）字段：

protected transient int modCount = 0;

每次对集合进行结构性修改（add/remove等）时，modCount 递增

创建迭代器时，记录当前的 modCount 为 expectedModCount

2. 检查机制 迭代过程中，每次操作前检查：

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

典型场景

1. 单线程环境

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");

Iterator<String> it = list.iterator();
while(it.hasNext()) {
    String s = it.next();
    list.remove(s); // 抛出ConcurrentModificationException
}

2. 多线程环境

List<String> list = new ArrayList<>();

// 线程1
new Thread(() -> {
    Iterator<String> it = list.iterator();
    while(it.hasNext()) {
        System.out.println(it.next());
        try { Thread.sleep(100); } catch (Exception e) {}
    }
}).start();

// 线程2
new Thread(() -> {
    list.add("new element"); // 可能导致线程1抛出异常
}).start();

注意事项

非同步修改检测：即使单线程中通过非迭代器方法修改集合也会触发

不保证实时性：不能保证100%检测到并发修改

非原子性检查：检查与操作之间仍可能有并发修改

解决方案

使用并发集合：

CopyOnWriteArrayList

ConcurrentHashMap

加锁同步：

synchronized(list) {
    Iterator it = list.iterator();
    while(it.hasNext()) {
        // 操作
    }
}

使用迭代器的修改方法：

Iterator<String> it = list.iterator();
while(it.hasNext()) {
    String s = it.next();
    it.remove(); // 安全删除
}

什么是安全失败（Fail-Safe）机制

采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。

原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发 Concurrent Modification Exception。

缺点：基于拷贝内容的优点是避免了 Concurrent Modification Exception，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。

场景：java.util.concurrent 包下的容器都是安全失败，可以在多线程下并发使用，并发修改，比如 CopyOnWriteArrayList 类。

安全失败（Fail-Safe）是 Java 集合框架中的一种并发修改处理机制，与快速失败（Fail-Fast）相对应。它的核心特点是：在迭代过程中，即使集合被修改，也不会抛出 ConcurrentModificationException，而是基于数据副本来进行操作，从而保证线程安全。

1. Fail-Safe 的核心特点 不抛出异常：即使集合在迭代过程中被修改（增删元素），也不会报错。

基于数据副本：迭代器操作的是集合的快照（Snapshot），而不是原始数据。

适用于并发环境：适合多线程场景，不会因为并发修改而中断程序。

2. Fail-Safe 的实现方式

Fail-Safe 集合通常采用以下两种方式之一：

Copy-On-Write（写时复制）：

每次修改集合时，先复制一份新的数据，修改在新数据上进行。

迭代器始终访问原始数据的副本，不受后续修改影响。

典型实现：CopyOnWriteArrayList、CopyOnWriteArraySet。

弱一致性（Weakly Consistent）迭代器：

迭代器遍历时，可能看到部分修改，但不保证完全一致。

典型实现：ConcurrentHashMap 的迭代器。

3. Fail-Safe 集合示例

（1）CopyOnWriteArrayList（写时复制）

List<String> list = new CopyOnWriteArrayList<>();
list.add("A");
list.add("B");
list.add("C");

Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String s = it.next();
    System.out.println(s); // 输出 A, B, C
    list.add("D"); // 不会影响当前迭代
}
System.out.println(list); // [A, B, C, D, D, D]

特点：

迭代期间修改不影响当前遍历。

每次修改都会复制底层数组，适合读多写少的场景。

（2）ConcurrentHashMap（弱一致性迭代器）

Map<String, Integer> map = new ConcurrentHashMap<>();
map.put("A", 1);
map.put("B", 2);
map.put("C", 3);

Iterator<Map.Entry<String, Integer>> it = map.entrySet().iterator();
while (it.hasNext()) {
    Map.Entry<String, Integer> entry = it.next();
    System.out.println(entry.getKey() + "=" + entry.getValue()); // 可能看到部分修改
    map.put("D", 4); // 不会抛出异常
}

特点：

迭代时可能看到部分修改，但不保证完全一致性。

适用于高并发读写场景。

有哪几种实现 ArrayList 线程安全的方法？

常用的有两种。

可以使用 Collections.synchronizedList() 方法，它可以返回一个线程安全的 List。

SynchronizedList list = Collections.synchronizedList(new ArrayList());

内部是通过 synchronized 关键字加锁来实现的。

也可以直接使用 CopyOnWriteArrayList，它是线程安全的 ArrayList，遵循写时复制的原则，每当对列表进行修改时，都会创建一个新副本，这个新副本会替换旧的列表，而对旧列表的所有读取操作仍然在原有的列表上进行。

CopyOnWriteArrayList list = new CopyOnWriteArrayList();

通俗的讲，CopyOnWrite 就是当我们往一个容器添加元素的时候，不直接往容器中添加，而是先复制出一个新的容器，然后在新的容器里添加元素，添加完之后，再将原容器的引用指向新的容器。多个线程在读的时候，不需要加锁，因为当前容器不会添加任何元素。这样就实现了线程安全。

CopyOnWriteArrayList 了解多少？

CopyOnWriteArrayList 就是线程安全版本的 ArrayList。

CopyOnWrite——写时复制，已经明示了它的原理。

CopyOnWriteArrayList 采用了一种读写分离的并发策略。CopyOnWriteArrayList 容器允许并发读，读操作是无锁的。至于写操作，比如说向容器中添加一个元素，首先将当前容器复制一份，然后在新副本上执行写操作，结束之后再将原容器的引用指向新容器。