ArrayList、LinkedList 与 CopyOnWriteArrayList 面试八问

ArrayList 内部：
elementData -> [A][B][C][ ][ ][ ]   size=3, capacity=6

继续 add 到第 7 个，容量不够：
oldCapacity = 6
newCapacity = 6 + (6 >> 1) = 6 + 3 = 9

扩容复制：
旧: [A][B][C][D][E][F]
新: [A][B][C][D][E][F][ ][ ][ ]

// 简化版
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)
        newCapacity = minCapacity; // 1.5 倍还不够，就按需要来
    elementData = Arrays.copyOf(elementData, newCapacity);
}

查：
下标:   0   1   2   3   4
数组: [A] [B] [C] [D] [E]
get(3) -> 直接定位到 D，O(1)

中间插入：
add(1, X)
[A] [X] [B] [C] [D] [E]
         B C D E 全部后移

public E get(int index) {
    return elementData(index); // 直接数组下标，O(1)
}

public void add(int index, E element) {
    ensureCapacityInternal(size + 1);
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     size - index); // 后移
    elementData[index] = element;
    size++;
}

null <- [prev|A|next] <-> [prev|B|next] <-> [prev|C|next] -> null
        first                                      last

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

transient Node<E> first;
transient Node<E> last;

// 尾插 O(1)
void linkLast(E e) {
    Node<E> l = last;
    Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null) first = newNode;
    else l.next = newNode;
    size++;
    modCount++;
}

// 按下标查找 O(n)
Node<E> node(int index) {
    if (index < (size >> 1)) {
        // 从头找
    } else {
        // 从尾找
    }
}

迭代器创建：
expectedModCount = modCount

集合结构修改：
list.add() / list.remove() / clear() -> modCount++

迭代器 next()：
if (modCount != expectedModCount)
    throw new ConcurrentModificationException

// 错误：增强 for 中直接 remove
for (String s : list) {
    if ("a".equals(s)) {
        list.remove(s); // 下一次 next() 抛 CME
    }
}

// 正确：用 Iterator.remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String s = it.next();
    if ("a".equals(s)) {
        it.remove(); // 内部会同步 expectedModCount
    }
}

// 也可以
list.removeIf(s -> "a".equals(s));

// 读多、随机访问多
List<User> list = new ArrayList<>();

// 频繁头尾操作，可作队列
Deque<User> deque = new ArrayDeque<>(); // 通常优于 LinkedList

读线程：直接读 array，不加锁

写线程：
lock
  old array: [A][B][C]
  复制 -> [A][B][C][ ]
  写入 -> [A][B][C][D]
  array = 新数组
unlock

volatile array 保证新数组引用对读线程可见

private transient volatile Object[] array;

final Object[] getArray() {
    return array;
}

final void setArray(Object[] a) {
    array = a;
}

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

COW 迭代器创建：
snapshot = 当前 array

其他线程 add：
复制新数组 -> 替换 array

迭代器仍然遍历 snapshot：
看不到新元素，也不会 ConcurrentModificationException

static final class COWIterator<E> implements ListIterator<E> {
    private final Object[] snapshot;
    private int cursor;

    COWIterator(Object[] elements, int initialCursor) {
        cursor = initialCursor;
        snapshot = elements;
    }

    public boolean hasNext() {
        return cursor < snapshot.length;
    }

    public E next() {
        return (E) snapshot[cursor++];
    }

    public void remove() {
        throw new UnsupportedOperationException();
    }
}

ArrayList 扩容：容量不足 -> 1.5 倍 -> Arrays.copyOf
COW 写操作：每次 add/remove -> 复制新数组 -> 替换引用

// 读多写极少，线程安全
List<String> listeners = new CopyOnWriteArrayList<>();

// 单线程或外部同步，随机访问多
List<String> list = new ArrayList<>();

// 头尾频繁操作，队列/栈
Deque<String> deque = new ArrayDeque<>();