Java 集合Collection—List

ArrayList

ArrayList 就是 Java 集合框架里最常用的 动态数组，查询快、增删慢（中间位置）、自动扩容、非线程安全

创建（3 种）

// 1. 空构造（初始容量 10）
List<String> list = new ArrayList<>();

// 2. 指定容量（避免多次扩容）
List<String> list = new ArrayList<>(100);

// 3. 通过已有集合快速构造
List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));

基本 CRUD

list.add("A");                // 尾插
list.add(0, "头");            // 按下标插入
list.get(0);                  // 查
list.set(1, "B");             // 改
list.remove("A");             // 按对象删，返回 boolean
list.remove(0);               // 按下标删，返回被删元素
list.size();                  // 元素个数
list.isEmpty();               // 是否空
list.clear();                 // 清空

遍历（4 样）

// 1. for-each（最简洁）
for (String s : list) System.out.println(s);

// 2. 下标遍历（需要索引时）
for (int i = 0; i < list.size(); i++) System.out.println(list.get(i));

// 3. 迭代器（遍历中删除安全）
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("A")) it.remove();
}

// 4. Lambda（Java 8+）
list.forEach(System.out::println);

常见批量/工具操作

// 排序
list.sort(String::compareTo);          // Java 8+
Collections.sort(list);                // 旧写法

// 洗牌
Collections.shuffle(list);

// 反转
Collections.reverse(list);

// 转数组
String[] arr = list.toArray(new String[0]);

// 去重（借助 Set）
List<String> noDup = new ArrayList<>(new LinkedHashSet<>(list));

容量与性能提示

• 默认初始容量 10，扩容 ×1.5（old + (old >> 1)），频繁扩容影响性能。
  可预估大小时直接 new ArrayList<>(size)。

• 中间插入/删除 = 数组拷贝，复杂度 O(n)；只追加或随机读用 ArrayList 最划算。

• 线程安全替代

List<String> syncList = Collections.synchronizedList(new ArrayList<>());
// 或者直接用 CopyOnWriteArrayList（读多写少场景）

一行代码记忆

new ArrayList<>(容量)  // 创
add/get/set/remove     // 增查改删
forEach + iterator       // 遍历安全
sort/shuffle/reverse     // 工具

ArrayList扩容

ArrayList 扩容 = 旧容量 1.5 倍，若仍不够则直接按需分配，最后 Arrays.copyOf 一次性拷贝

// 位于 java.util.ArrayList 中
private void grow(int minCapacity) {   // minCapacity = 当前所需最小容量
    int oldCapacity = elementData.length;          // 旧容量
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 关键1：新容量 = 旧容量 + 旧容量/2  → 1.5 倍
    if (newCapacity - minCapacity < 0)               // 关键2：如果 1.5 倍还不够，就直接用所需容量
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)            // 超过 JVM 允许最大数组长度时做极限处理
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity); // 真正申请新数组并拷贝
}

使用时机

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 每次 add 先保证容量够用
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 空构造第一次 add
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); // 默认初始容量 10
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)  // 容量不足才触发 grow
        grow(minCapacity);
}

ArrayList源码

ArrayList 就是 “能自动长大的数组”——
底层用 连续 Object[] 存元素，用 size 字段记实际长度，扩容时 1.5 倍拷贝，所有操作围绕 “下标访问 + 数组拷贝” 设计；
查询 O(1)、中间增删 O(n)、内存紧凑、非线程安全。

下面按 字段 → 构造 → 扩容 → 增删查 → 迭代失败 五个核心展开

核心字段（JDK 17）

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    transient Object[] elementData; // 真正存元素的数组
    private int size;               // 当前元素个数，不是容量
    private static final int DEFAULT_CAPACITY = 10; // 默认容量
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
}

• elementData 长度 ≥ size，多余位置放 null

• size 为 0 时数组可能是 {} 或 new Object[10]（懒初始化）

构造策略：懒初始化 + 零拷贝空数组

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // {}
}
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0)
        this.elementData = new Object[initialCapacity];
    else if (initialCapacity == 0)
        this.elementData = EMPTY_ELEMENTDATA;   // 共享空常量
    else throw new IllegalArgumentException();
}

空构造第一次添加时才扩容到 10，避免 new ArrayList() 占 10 个引用。

扩容逻辑：1.5 倍拷贝

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = ArraysSupport.newLength(oldCapacity,
            minCapacity - oldCapacity, /* minimum growth */
            oldCapacity >> 1           /* preferred growth：0.5 倍 */);
    return elementData = Arrays.copyOf(elementData, newCapacity);
}

• 新容量 = old + old/2（1.5 倍）

• Arrays.copyOf 一次性 连续内存拷贝，触发 CPU 缓存友好的批量复制

• 扩容后 旧数组立刻被 GC（无引用）

增删查设计——围绕“下标+拷贝”

随机访问（最快路径）

E elementData(int index) {
    return (E) elementData[index]; // O(1)
}

尾部添加（最快插入）

public boolean add(E e) {
    modCount++;
    add(e, elementData, size); // 直接放 elementData[size] 然后 size++
    return true;
}

中间插入/删除（代价操作）

public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s = size;
    if (s == elementData.length) elementData = grow();
    // 核心：System.arraycopy 把 [index..end] 整体后移 1 位
    System.arraycopy(elementData, index, elementData, index + 1, s - index);
    elementData[index] = element;
    size = s + 1;
}

• 插入：后移 → 赋值

• 删除：前移 → 末尾置 null（帮助 GC）

Fail-Fast 迭代器

private class Itr implements Iterator<E> {
    int expectedModCount = modCount; // 创建时记录
    ...
    final void checkForEachComModification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

• 任何 结构修改（add/remove/trimToSize）都会 modCount++

• 迭代器发现 expectedModCount ≠ modCount 立即抛异常，防止脏读

contains

顺序遍历数组 并调用 equals，直到找到匹配项

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    if (o == null) {                       // 支持 null 元素
        for (int i = 0; i < size; i++)
            if (elementData[i] == null) return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i])) return i; // 逐个 equals
    }
    return -1;                             // 未找到
}

内存与性能速览

“用连续数组换随机访问速度，用 size 字段解耦逻辑长度与物理长度，用 1.5 倍拷贝平衡扩容次数与内存浪费，用 modCount 保迭代一致性；中间增删靠 System.arraycopy 批量搬移，CPU 缓存友好，代价是 O(n)。”

LinkedList

LinkedList 是 双向链表 实现的 List 和 Deque，插入/删除头尾快、随机访问慢，非线程安全。

创建

LinkedList<String> list = new LinkedList<>();           // 空链表
LinkedList<Integer> list2 = new LinkedList<>(Arrays.asList(1,2,3)); // 带初值

List 接口常用（随机访问性能差）

list.add("A");              // 尾插
list.add(1, "B");           // 按下标插入（需遍历到节点，O(n)）
list.get(2);                // 按索引查（O(n)）
list.set(0, "AA");          // 改（O(n)）
list.remove("A");           // 按对象删
list.remove(0);             // 按下标删
list.size();                // 元素个数
list.clear();               // 清空

Deque 接口常用（头/尾操作 O(1)）

// 头
list.addFirst("head");      // 头部插入
String h = list.removeFirst(); // 头部删除并返回
String peek = list.peekFirst(); // 偷看头

// 尾
list.addLast("tail");       // 尾插（等价 add）
String t = list.removeLast();
String peekTail = list.peekLast();

// 队列模式
list.offer("task");         // 尾插
String task = list.poll();  // 头删，空返回 null
String element = list.element(); // 头查，空抛异常

遍历（4 样）

// 1. for-each（最常用）
for(String s : list) System.out.println(s);

// 2. 下标（慢，O(n^2) 总耗时）
for (int i = 0; i < list.size(); i++) ...

// 3. 迭代器（遍历时删安全）
Iterator<String> it = list.iterator();
while(it.hasNext()) if (it.next().equals("A")) it.remove();

// 4. Lambda
list.forEach(System.out::println);

栈/队列 一行用法

// 当栈用
list.push("A");      // 压栈
String top = list.pop(); // 出栈

// 当队列用
list.offer("job");
String job = list.poll();

性能 & 使用提示

• 随机访问 get(index) 需遍历，复杂度 O(n)；大量按位置读写请用 ArrayList。

• 头/尾增删 O(1)，适合 队列、栈 场景。

• 需要线程安全时

Deque<String> syncDeque = Collections.synchronizedDeque(new LinkedList<>());
// 或 ConcurrentLinkedQueue / LinkedBlockingDeque

口诀背下来

LinkedList = 双向链
push/pop 当栈用
addFirst/removeFirst 当队列
随机 get 慢成狗

LinkedList源码

LinkedList 就是 “双向链表” ——
用 Node<E> 把元素串成两条链（前向 + 后向），头尾插入/删除 O(1)，随机访问 O(n)，内存 非连续、迭代安全，支持 队列、栈、双端队列 全套 API。

下面按 节点结构 → 头尾指针 → 增删查 → 队列/栈适配 → 内存与 fail-fast 6 个维度拆解

节点结构：一条记录存 3 个引用

private static class Node<E> {
    E item;        // 数据
    Node<E> next;  // 后驱
    Node<E> prev;  // 前驱
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

每个元素额外 2 个指针 ≈ 24 byte（64 位压缩指针）开销。

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

空列表时 first = last = null；单节点时两者指向同一个 Node。

头尾增删：O(1) 只改邻居指针

头插 addFirst(E e)

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f); // prev = null
    first = newNode;
    if (f == null)                   // 原列表空
        last = newNode;
    else
        f.prev = newNode;            // 原头的前驱指向新头
    size++;
    modCount++;
}

尾插 addLast(E e)（JDK 里叫 linkLast）同理，只改 last 和原尾节点的 next。

中间插入 add(int index, E e)
→ 先 折半遍历找到节点（见第 4 点），再 unlinkBefore 改 4 个指针：

Node<E> succ = node(index);        // 目标位置原节点
Node<E> newNode = new Node<>(succ.prev, e, succ);
succ.prev.next = newNode;
succ.prev = newNode;

只改邻居引用，无需像 ArrayList 那样整体搬移数组。

随机访问：折半遍历 → O(n)

Node<E> node(int index) {
    // 下标 < size/2 从头扫；否则从尾扫
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++) x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--) x = x.prev;
        return x;
    }
}

最坏仍需 n/2 次指针跳转，缓存不友好，这也是 LinkedList 被随机访问嫌弃的根本原因。

队列/栈/双端队列：一套链表，三套接口

// 当 FIFO 队列
Queue<String> q = new LinkedList<>();
q.offer("A");      // 尾插
q.poll();          // 头删

// 当 LIFO 栈
Deque<String> s = new LinkedList<>();
s.push("A");       // 头插
s.pop();           // 头删

// 当双端队列
Deque<String> dq = new LinkedList<>();
dq.addFirst("head");
dq.addLast("tail");

底层都是 linkFirst / linkLast / unlinkFirst / unlinkLast 4 个私有方法，O(1) 完成。

Fail-Fast & 内存

• 同 ArrayList，modCount 计数结构修改；迭代器发现不一致立即抛 ConcurrentModificationException。

• 节点 分散在堆中，不连续，CPU 缓存行利用率低；但 插入/删除不移动数据，适合 头/尾频繁变动 场景。

设计思想一句话

“用 Node 前后指针把元素串成双向链，头尾 direct 指针保证 O(1) 增删，折半遍历应付随机 index；一套链表同时实现 List+Queue+Deque，迭代安全，内存分散换增删速度。”

List如何线程安全

CopyOnWriteArrayList —— 读多写少无敌手

• 原理：写时复制整个数组；读操作无锁。

• 适用：遍历远多于修改，且数据量不大（复制成本可接受）。

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

缺点：写频繁或数组巨大时 GC 压力大。

Collections.synchronizedList(new ArrayList<>()) —— 通用兜底

• 原理：对每个方法加 synchronized (mutex)，读写都串行。

• 适用：写操作不少、数据量中等、需要随机访问。

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

注意：

• 迭代必须手动加锁，否则抛 ConcurrentModificationException

synchronized (list) {
    for (String s : list) { ... }
}

Vector —— 历史遗产，别再用

与 synchronizedList 类似，但所有方法直接加 synchronized，性能差、扩展性差；官方已不推荐使用。

手动外部锁 —— 特殊需求

自己控制锁粒度，例如读写锁 ReentrantReadWriteLock：

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

// 读
rwl.readLock().lock();
try { ... } finally { rwl.readLock().unlock(); }

// 写
rwl.writeLock().lock();
try { list.add("x"); } finally { rwl.writeLock().unlock(); }

复杂度最高，只有需要 细粒度控制 或 批量读写 时才考虑。

选型口诀
“读远多于写” → CopyOnWriteArrayList
“读写差不多” → Collections.synchronizedList
“不要碰 Vector” → 历史遗迹
“极致性能” → 手动读写锁

CopyOnWriteArrayList写时加锁复制

同一时刻只能有一条线程写，读线程完全无锁；
写操作先 加锁 → 复制数组 → 修改副本 → 原子替换引用，最后释放锁。

set(int index, E element) —— 替换指定位置元素

public E set(int index, E element) {
    synchronized (lock) {              // ① 全局写锁，保证只有一条线程进入
        Object[] es = getArray();      // ② 拿到当前 volatile 数组快照（读无锁）
        E oldValue = elementAt(es, index); // ③ 取旧值

        if (oldValue != element) {     // ④ 值真正变化才复制
            es = es.clone();           // ⑤ 整表复制一份新数组
            es[index] = element;       // ⑥ 在新数组上修改
        }
        // ⑦ 即使旧值相同，也做一次 volatile 写，保证“写-写”顺序语义
        setArray(es);                  // ⑧ 原子替换数组引用，读线程立即可见
        return oldValue;               // ⑨ 返回旧值
    }                                    // ⑩ 解锁，写完成
}

add(E e) —— 尾部追加元素

public boolean add(E e) {
    synchronized (lock) {              // ① 写锁
        Object[] es = getArray();      // ② 当前数组
        int len = es.length;           // ③ 旧长度
        es = Arrays.copyOf(es, len + 1); // ④ 复制并扩容 1 位
        es[len] = e;                   // ⑤ 在新数组尾部放入新元素
        setArray(es);                  // ⑥ volatile 替换引用，读线程无感知切换
        return true;                   // ⑦ 成功
    }                                    // ⑧ 解锁
}

Arrays.copyOf

Collections.synchronizedList

Collections.synchronizedList的原理是在原有的List上套一层synchronized

Collections.synchronizedList 的实现原理就是 “装饰器模式 + 同步代码块”：
它并不改动原 List 的内部结构，而是把 所有访问方法 包上一层 synchronized (mutex)，让 同一时刻只有一个线程能读写。

下面给出源码级注释，一眼看懂。

工厂方法入口

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

→ 根据是否支持随机访问，选两个装饰子类，但核心逻辑一样。

装饰类结构（以 SynchronizedList 为例）

static class SynchronizedList<E> extends SynchronizedCollection<E> implements List<E> {
    private static final long serialVersionUID = -7754090372962977524L;
    final List<E> list;           // 被装饰的原始 List

    SynchronizedList(List<E> list) {
        super(list);              // 父类把 list 保存为 this.c
        this.list = list;
    }
    ...
}

方法级同步 —— 所有操作包 synchronized (mutex)

public E get(int index) {
    synchronized (mutex) {        // 同一时刻只有一个线程能读
        return list.get(index);
    }
}

public void add(int index, E element) {
    synchronized (mutex) {        // 写也串行
        list.add(index, element);
    }
}

public Iterator<E> iterator() {
    return list.iterator();       // ⚠️ 注意：迭代器本身 **不同步**！
}

• mutex 在父类 SynchronizedCollection 里就是 当前装饰器实例 (this)。

• 因此 读写互斥、写写互斥、读读也互斥 —— 完全串行。

迭代器 不同步 —— 必须手动加锁

List<Foo> syncList = Collections.synchronizedList(new ArrayList<>());
...
synchronized (syncList) {        // 整个遍历区间加锁
    for (Foo f : syncList) {
        // do something
    }
}

否则在多线程环境下会抛 ConcurrentModificationException。

与 Vector 对比

一句话总结
Collections.synchronizedList 就是 给原 List 套一层“方法级同步壳”，
所有读写操作串行化，迭代器必须额外手动加锁，简单但并发度低，适合 写少读少 或 快速兜底 场景。

LinkedList和ArrayList使用场景

查询多、尾部增删多 → ArrayList；插入删除多、当队列/栈用 → LinkedList
下面把场景、量化数据、代码示例一次给全，面试直接背。

一、底层决定性格

二、量化场景阈值（经验值）

1. 随机访问次数 > 1 000 / 每 1 次插入 → 用 ArrayList
   实测 10w 次 get(i)：ArrayList ≈ 1 ms，LinkedList ≈ 200 ms

2. 头/尾插入比例 > 30% 且几乎不查询 → LinkedList 开始反超
   10w 次头插：LinkedList ≈ 3 ms，ArrayList ≈ 200 ms（批量 add(0, e) 需整体拷贝）

三、典型业务场景对照