ArrayList 与 LinkedList 有何区别？ArrayList 如何扩容？

结论先行：ArrayList 底层是动态数组，按下标随机访问 O(1)、尾部增删快，扩容时要整体搬移；LinkedList 底层是双向链表，头尾增删 O(1)，但按下标访问需遍历到 O(n)。日常绝大多数场景应选 ArrayList——LinkedList 的“中间插入快”因要先遍历定位而大打折扣，属于伪优势。

对比表

维度	ArrayList	LinkedList
底层结构	Object[] 动态数组	双向链表（Node）
随机访问 get(i)	O(1)	O(n) 从头/尾遍历
头部增删	O(n) 整体搬移	O(1)
尾部增删	O(1) 摊还	O(1)
中间插入	O(n) 搬移	O(n) 定位 + O(1) 链接
内存占用	连续紧凑	每节点额外存前后指针

ArrayList 扩容规则

1. 默认初始容量 10，且是懒分配：首次 add 时才真正创建数组。
2. 容量不足时新容量 = 旧容量 + (旧容量 >> 1)，即按 1.5 倍增长。
3. 扩容动作 = 新建数组 + System.arraycopy 整体拷贝，代价 O(n)，因此能预估大小时应指定初始容量。

import java.util.ArrayList;
import java.util.List;

public class ListDemo {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(1000); // 预分配，减少扩容拷贝
        for (int i = 0; i < 1000; i++) {
            list.add(i);
        }
        // 遍历删除应使用迭代器或 removeIf，否则抛 ConcurrentModificationException
        list.removeIf(v -> v % 2 == 0);
        System.out.println(list.size());
    }
}

常见追问 / 记忆点

• 记忆点：数组 1.5 倍扩容 + 拷贝；链表“增删快”要扣掉定位成本，是伪优势。
• 追问：subList 返回的是视图而非副本，对子列表做结构性修改会影响原列表甚至抛异常。
• 追问：Arrays.asList 得到的列表定长，调用 add/remove 会抛 UnsupportedOperationException。