第二大脑

主题

2026-08-24
691
2.6m

概念卡片：ArrayList 与 LinkedList ​

一句话机制 ​

ArrayList 底层是动态数组（Object[] elementData），随机访问快、增删慢，扩容 1.5 倍；LinkedList 底层是双向链表（first/last 指针），增删快、随机访问慢。 二者取舍的核心是「数组连续内存 vs 链表指针跳转」的代价差。

底层结构对比 ​

维度ArrayListLinkedList
底层transient Object[] elementData双向链表（Node first/last）
随机访问O(1)（下标直接寻址）O(n)（从头/尾遍历）
增删（中间）O(n)（搬移元素）O(1)（改指针）
内存连续，可能预留空间分散，每个节点额外存前驱/后继指针
实现接口List + RandomAccessList + Deque（可当队列/栈用）

不变量：ArrayList 实现了 RandomAccess 标记接口，遍历用普通 for 更快；LinkedList 没实现，遍历用迭代器（foreach）更快。

ArrayList 扩容机制（源码级） ​

java
// 核心：1.5 倍扩容
int newCapacity = oldCapacity + (oldCapacity >> 1);  // 右移 1 位 = 除以 2
构造方式初始容量扩容规则
无参 new ArrayList()0（DEFAULTCAPACITY_EMPTY_ELEMENTDATA）第一次 add 扩到 10，之后 1.5 倍
有参 new ArrayList(n)n满了直接 1.5 倍

关键坑：无参构造不是一开始就 10，而是懒初始化——第一次 add 才分配 10 容量，避免空 list 浪费内存。

fail-fast（快速失败）机制 ​

ArrayList 的 modCount 记录结构修改次数，迭代时若发现 modCount 被改（如遍历中 add/remove），抛出 ConcurrentModificationException。这是「快速失败」：宁可立即抛异常，也不让迭代器在结构已变的数据上继续错乱地跑。

规避：遍历中删除用迭代器自己的 remove()（会同步 modCount），或用 CopyOnWriteArrayList（写时复制，但内存开销大）。

如何选型 ​

场景选谁
频繁随机访问 / 尾部追加ArrayList
频繁头尾插入删除 / 当队列栈用LinkedList
已知大小、追求性能new ArrayList(n) 指定容量，避免反复扩容

实际开发中 ArrayList 用得远比 LinkedList 多：现代 JVM 的内存局部性让数组访问极快，LinkedList 的「增删快」只在头尾成立（中间增删也要先遍历定位），优势被高估。

常见误解（避坑） ​

  1. ❌ "ArrayList 一创建就有 10 容量"。→ 无参构造初始是空数组，第一次 add 才扩到 10。
  2. ❌ "ArrayList 满了扩容 2 倍"。→ 是 1.5 倍（oldCapacity + oldCapacity >> 1）。
  3. ❌ "LinkedList 增删一定比 ArrayList 快"。→ 只在头尾增删快；中间增删要先 O(n) 遍历定位，未必快。
  4. ❌ "遍历 ArrayList 用迭代器最快"。→ ArrayList 实现了 RandomAccess，普通 for（下标）比迭代器快；LinkedList 才适合迭代器。

关联 ​

最近更新