List 实现对比

问题

ArrayList 和 LinkedList 有什么区别？ArrayList 的扩容机制是怎样的？CopyOnWriteArrayList 是什么？

答案

ArrayList

基于动态数组实现，支持随机访问（实现了 RandomAccess 标记接口）：

ArrayList 核心结构（简化）

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

    transient Object[] elementData; // 存储元素的数组
    private int size;               // 实际元素数量

    // 默认初始容量
    private static final int DEFAULT_CAPACITY = 10;
}

扩容机制

ArrayList 扩容流程

// 添加元素时检查容量
public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

// 扩容：每次扩 1.5 倍
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 新容量 = 旧容量 + 旧容量/2（即 1.5 倍）
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity < minCapacity)
        newCapacity = minCapacity;
    // 通过 Arrays.copyOf 复制到新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

预分配容量避免多次扩容

如果知道大致元素数量，使用带初始容量的构造器可以避免多次扩容拷贝：

// 已知约 10000 个元素
List<String> list = new ArrayList<>(10000);

LinkedList

基于双向链表实现，同时实现了 List 和 Deque 接口：

LinkedList 核心结构（简化）

public class LinkedList<E> extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, Serializable {

    transient int size = 0;
    transient Node<E> first; // 头节点
    transient Node<E> last;  // 尾节点

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
    }
}

ArrayList vs LinkedList

维度	ArrayList	LinkedList
底层结构	动态数组	双向链表
随机访问 get(i)	$O(1)$	$O(n)$
头部插入/删除	$O(n)$（需要移动元素）	$O(1)$
尾部插入	均摊 $O(1)$	$O(1)$
中间插入/删除	$O(n)$	$O(n)$（查找 $O(n)$ + 插入 $O(1)$）
内存占用	紧凑（仅数组 + 少量空位）	大（每个节点多两个指针）
CPU 缓存	友好（连续内存）	不友好（内存不连续）
实现接口	RandomAccess	Deque

实际开发建议

几乎所有场景都应该使用 ArrayList。LinkedList 虽然在头部插入理论上是 $O(1)$，但由于 CPU 缓存不友好和额外的内存开销，实际性能往往不如 ArrayList。LinkedList 唯一的优势场景是作为 Deque（双端队列）使用，但这种情况下 ArrayDeque 性能更好。

CopyOnWriteArrayList

线程安全的 List，适用于读多写少的场景：

CopyOnWriteArrayList 原理（简化）

public class CopyOnWriteArrayList<E> implements List<E> {
    private transient volatile Object[] array;
    final transient Object lock = new Object();

    // 读操作：无锁，直接读取当前数组
    public E get(int index) {
        return (E) array[index]; // 无同步开销
    }

    // 写操作：加锁，复制整个数组，修改后替换
    public boolean add(E e) {
        synchronized (lock) {
            Object[] es = array;
            int len = es.length;
            // 复制出新数组
            es = Arrays.copyOf(es, len + 1);
            es[len] = e;
            // 替换引用（volatile 保证可见性）
            array = es;
            return true;
        }
    }
}

优点	缺点
读操作无锁，性能极高	写操作需要复制整个数组，开销大
迭代器不会抛 ConcurrentModificationException	数据可能不是最新的（弱一致性）
适合读多写少场景	不适合大数据量或频繁写入

---

常见面试问题

Q1: ArrayList 的 elementData 为什么用 transient 修饰？

答案：

因为 elementData 数组通常有未使用的空位（预留容量），序列化整个数组会浪费空间。ArrayList 自定义了 writeObject 方法，只序列化实际存在的 size 个元素：

private void writeObject(ObjectOutputStream s) throws IOException {
    s.defaultWriteObject();
    s.writeInt(size);
    for (int i = 0; i < size; i++) {
        s.writeObject(elementData[i]); // 只写有效元素
    }
}

Q2: ArrayList 是线程安全的吗？怎么保证线程安全？

答案：

不安全。保证线程安全的方式：

1. Collections.synchronizedList()：包装为同步 List（所有方法加 synchronized）
2. CopyOnWriteArrayList：适合读多写少
3. Vector：所有方法 synchronized，已过时不推荐

Q3: ArrayList 和 Vector 的区别？

答案：

维度	ArrayList	Vector
线程安全	不安全	安全（synchronized）
扩容	1.5 倍	2 倍
性能	更快	较慢（同步开销）
推荐	推荐使用	已过时

Q4: 如何在遍历时删除 ArrayList 中的元素？

答案：

List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c", "d"));

// ❌ 增强 for 循环中删除 → ConcurrentModificationException
for (String s : list) {
    if ("b".equals(s)) list.remove(s);
}

// ✅ 方式一：Iterator.remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if ("b".equals(it.next())) {
        it.remove();
    }
}

// ✅ 方式二：removeIf（JDK 8+，推荐）
list.removeIf("b"::equals);

// ✅ 方式三：倒序遍历删除
for (int i = list.size() - 1; i >= 0; i--) {
    if ("b".equals(list.get(i))) list.remove(i);
}

Q5: Arrays.asList() 和 List.of() 的区别？

答案：

维度	Arrays.asList()	List.of()（JDK 9+）
可修改元素	可以 set()	不可修改
增删元素	不支持 add/remove	不支持
null 元素	允许	不允许
底层数组	与原数组共享	独立副本

Q6: subList() 需要注意什么？

答案：

subList() 返回的是原 List 的视图，不是独立副本：

• 修改子列表会影响原列表
• 修改原列表结构（增删）后操作子列表会抛 ConcurrentModificationException
• 要独立副本：new ArrayList<>(list.subList(0, 5))

相关链接

• Oracle - ArrayList (Java SE 17)
• Oracle - LinkedList (Java SE 17)
• Oracle - List Interface
• Baeldung - ArrayList vs LinkedList
• Baeldung - CopyOnWriteArrayList