Java LinkedList与ArrayList的区别与使用场景

ArrayList随机访问快因底层是数组，通过下标直接定位，O(1)；LinkedList是双向链表，需遍历节点，O(n)。首尾操作LinkedList更优，但ArrayDeque通常更佳。

ArrayList 的随机访问为什么快，而 LinkedList 不行

因为 ArrayList 底层是数组，通过下标计算内存偏移量就能直接定位元素，时间复杂度是 O(1)；LinkedList 是双向链表，每次 get(i) 都得从头或尾开始逐个跳节点，最坏要遍历一半，时间复杂度是 O(n)。

实操建议：

• 频繁调用 get(i)、set(i, e) 时，无条件选 ArrayList
• LinkedList 的 get(i) 在 i 接近 size/2 时性能断崖式下降，压测中容易被忽略
• 别被“链表查得慢”这种笼统说法误导——它只在随机访问时慢，首尾操作反而更快

LinkedList 的 add() 和 remove() 在首尾为什么比 ArrayList 快

ArrayList 在首部插入（add(0, e)）或删除（remove(0)）时，要整体移动后续所有元素；而 LinkedList 只需改几个指针，时间复杂度是 O(1)。

实操建议：

• 用作栈（push/pop）、队列（offer/poll）时，LinkedList 更合适——它实现了 Deque 接口，首尾操作都高效
• ArrayList 的 add(e)（尾插）也是 O(1) 均摊，但 add(0, e) 是 O(n)，别混为一谈
• 注意：JDK 21+ 中 ArrayDeque 在大多数首尾场景下比 LinkedList 更快且更省内存，优先考虑它

内存占用差异直接影响 GC 压力

ArrayList 每个元素只存数据本身（比如一个 Integer 引用），而 LinkedList 每个元素额外包着两个指针（prev、next）和一个 Node 对象头，单个元素内存开销大约是 ArrayList 的 3 倍以上。

实操建议：

• 存上万条简单数据（如 String ID 列表）时，LinkedList 容易触发频繁 Young GC
• Android 开发中尤其敏感——LinkedList 的对象碎片化会加剧内存抖动
• 如果只是需要“能快速删中间”，别硬上 LinkedList；先试试 ArrayList + removeIf() 或用 Iterator.remove()

迭代器行为差异导致 ConcurrentModificationException 风险不同

两者都使用 fail-fast 迭代器，但触发时机有微妙差别：ArrayList 的 modCount 在结构变更（增删）时更新；LinkedList 的 modCount 同样如此，但它支持通过 listIterator() 双向遍历，且 add() / previous() 等操作也可能改变结构。

实操建议：

• 遍历时修改集合，一律用 Iterator.remove()，别用 list.remove(obj)
• LinkedList 的 ListIterator 支持 add() 插入到迭代位置前，这在 ArrayList 迭代器里不支持——这是少数必须用 LinkedList 的明确场景
• 多线程环境别直接用二者，该上 CopyOnWriteArrayList 或 ConcurrentLinkedQueue

// 错误：遍历时直接 remove()
for (String s : list) {
    if (s.startsWith("tmp")) {
        list.remove(s); // 抛 ConcurrentModificationException
    }
}

// 正确：用迭代器 remove()
for (Iterator it = list.iterator(); it.hasNext(); ) {
    String s = it.next();
    if (s.startsWith("tmp")) {
        it.remove(); // 安全
    }
}