ArrayList 和 LinkedList 有什么区别？

结论速查

维度	ArrayList	LinkedList
底层结构	动态数组	双向链表
随机访问	O(1)	O(n)
头部插入	O(n)	O(1)
尾部插入	均摊 O(1)	O(1)
内存	连续，紧凑	每个节点额外存 prev/next
缓存友好	是	否

一、ArrayList

底层是 transient Object[] elementData：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

• 尾部追加快。
• 中间插入/删除要移动元素，O(n)。
• 扩容：默认 10，扩容为 1.5 倍。

二、LinkedList

底层是双向链表：

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

• 已知位置的插入删除 O(1)。
• 但 get(i) 要从头遍历，O(n)。
• 实现了 Deque，可以当队列/栈用。

三、怎么选

• 读多写少、随机访问多：ArrayList。
• 频繁头尾操作：LinkedList（或 ArrayDeque）。
• 中间插入多：实际很少用 LinkedList，因为查找位置本身就 O(n)。

常见误区

"LinkedList 插入快"是错觉。如果不知道节点位置，list.add(index, e) 要先遍历到 index，O(n)。真正快的是已经拿到节点引用的插入。

JDK 11+

LinkedList 在 JDK 21 中仍然存在，但实际项目 95% 用 ArrayList。