ArrayList vs LinkedList：从源码看使用场景

// ArrayList.java（JDK 8+）· 核心字段
transient Object[] elementData;    // 底层数组：连续内存（transient 见第 13 站）
private int size;                  // 当前元素个数（≠ 数组长度）

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 懒加载：首次 add 才建 10 容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // 数组长度上限

// 随机访问 —— O(1)
public E get(int index) {
    rangeCheck(index);            // 越界检查
    return elementData(index);   // 直接下标取值
}

private void rangeCheck(int index) {
    if (index >= size)          // 只查上界；负数会由数组访问抛 AIOOBE
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

// 下标访问的内部方法，无任何边界检查
E elementData(int index) {
    return (E) elementData[index];
}

public boolean add(E e) {
    ensureCapacityInternal(size + 1);   // 容量不足时触发扩容
    elementData[size++] = e;               // 追加到末尾
    return true;
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // ★ 1.5 倍：右移一位再相加
    if (newCapacity - minCapacity < 0)     // 一次 addAll 加太多时，直接扩到刚好够
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0) // 触及上限走 hugeCapacity
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity); // 新数组 + 整体拷贝
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0)                 // int 溢出为负数 → 真的装不下了
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

public void add(int index, E element) {
    rangeCheckForAdd(index);                      // 要求 0 ≤ index ≤ size
    ensureCapacityInternal(size + 1);         // 可能触发扩容
    System.arraycopy(elementData, index,
                     elementData, index + 1,  // 目标位置右移一位
                     size - index);               // 搬移后半段全部元素
    elementData[index] = element;
    size++;
}

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    elementData[--size] = null;   // ★ 尾部置 null：切断引用，帮助 GC
    return oldValue;
}

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;           // 前驱

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Node<E> node(int index) {
    // 优化：从距离更近的一端开始遍历
    if (index < (size >> 1)) {   // index 在前半段 → 从头走
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;             // 从头部跳到 index
        return x;
    } else {                        // index 在后半段 → 从尾走
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;             // 从尾部跳到 index
        return x;
    }
}

// 头尾操作：O(1)
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null) last = newNode;   // 原链表为空
    else f.prev = newNode;
    size++; modCount++;
}
// linkLast 对称，略

// 在 succ 节点之前插入：只改 4 个指针
void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null) first = newNode;   // succ 是头节点
    else pred.next = newNode;
    size++; modCount++;
}

// 摘除节点：同样只改相邻指针
E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) first = next;
    else { prev.next = next; x.prev = null; }

    if (next == null) last = prev;
    else { next.prev = prev; x.next = null; }

    x.item = null;          // 帮助 GC
    size--; modCount++;
    return element;
}

// 但按 API 删除：先 O(n) 找节点，再 O(1) 摘除
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));   // ★ node(index) 才是真正的成本
}

// ✗ 错误：for-each 中直接 remove，迭代器检测到 modCount 变化 → 抛 CME
for (String s : list) {
    if (s.startsWith("x")) list.remove(s);
}

// ✓ 正确 1：迭代器 remove（同步 modCount）
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().startsWith("x")) it.remove();
}

// ✓ 正确 2：removeIf（JDK 8+，ArrayList 底层用 BitSet 标记 + 一次批量搬移，性能最好）
list.removeIf(s -> s.startsWith("x"));

// ✗ 另一个坑：for-i 正序删除会跳过相邻元素（删除后下标错位）
for (int i = 0; i < list.size(); i++) {
    if (list.get(i).startsWith("x")) list.remove(i); // 相邻元素被跳过
}
// ✓ 倒序遍历即可

List<String> sub = list.subList(1, 3);   // 视图：共享底层数组，不是新列表
sub.set(0, "X");                          // 会影响原 list（视图的修改是"原地"的）
list.add("new");                          // ✗ 原 list 结构性修改后，再碰 sub → CME
// 需要独立副本时：new ArrayList<>(list.subList(1, 3))

String[] arr = (String[]) list.toArray();   // ✗ ClassCastException：擦除后运行时是 Object[]
String[] arr2 = list.toArray(new String[0]);  // ✓ JDK 11+ 对空数组有专门优化，推荐
String[] arr3 = list.toArray(new String[list.size()]); // ✓ 但会先分配再被覆盖