数组和链表有什么区别？各自适合什么场景？
简化版
数组是连续内存存储，靠下标随机访问，读快（O(1)）但增删中间元素要搬移（O(n)）；链表是离散节点+指针串联，增删只需改指针（O(1)），但访问第 k 个要从头遍历（O(n)）。读多写少用数组，频繁在两端/中间增删用链表。
详细版
| 维度 | 数组 | 链表 |
|---|---|---|
| 内存 | 一整块连续内存 | 节点分散，靠指针连接 |
| 随机访问第 k 个 | O(1)（起始地址 + k×元素大小） | O(n)（从头走 k 步） |
| 头部增删 | O(n)（后面元素整体搬移） | O(1)（改指针） |
| 中间增删 | O(n)（搬移） | 查 O(n) + 改指针 O(1) |
| 尾部增删 | 均摊 O(1)（动态数组，满了要扩容） | O(1)（若存了尾指针） |
| 额外空间 | 几乎无 | 每个节点多存 1~2 个指针 |
| 缓存友好度 | 高（连续，命中率高） | 低（跳来跳去） |
怎么选：要频繁按下标访问、读多写少 → 数组；要频繁在头部/中间插入删除、大小变化大 → 链表。实际开发里数组（ArrayList）用得远多于链表，因为 CPU 缓存对连续内存的偏好经常让数组「常数更小」。
完整版教学
一、本质差异：连续 vs 离散
数组在内存里是一整块连续空间，所以知道起始地址和下标就能直接算出任意元素的地址：addr = base + index × size，这就是随机访问 O(1) 的来源。代价是它「长度固定」——想在中间插入一个元素，后面所有元素都得往后挪一格。
链表把数据拆成一个个 节点（Node），每个节点除了存数据，还存指向下一个节点的指针。节点在内存里可以东一个西一个，靠指针串起来。好处是插入/删除只要把前后指针接一下，不用搬移数据；坏处是想找第 k 个元素，只能从头指针一个一个跳过去。
二、为什么「链表增删快」经常是个误区
面试常听到「链表增删快」，但要看清前提：「改指针」确实是 O(1)，但「找到要改的位置」通常是 O(n)。
- 如果你已经持有目标节点的引用（比如 LRU 里已经拿到了要移动的节点），那增删是真 O(1)。
- 如果只知道「删除第 5 个」或「按值删除」，得先遍历定位，整体还是 O(n)。
而数组虽然搬移是 O(n)，但搬的是连续内存，CPU 一次能预取一大片，实际很快。所以别一看到「增删」就无脑选链表。
三、缓存友好度：容易被忽略的性能差异
现代 CPU 有多级缓存，访问连续内存时会预取相邻数据。数组连续存放，遍历时缓存命中率高；链表节点分散，每次跳转都可能是一次缓存未命中（cache miss），从内存里重新加载。所以即使理论复杂度相同，遍历数组通常比遍历链表快很多。这也是工程上偏爱 ArrayList、ArrayDeque 的重要原因。
四、动态数组：数组「不能变长」的补丁
真实语言里的 ArrayList（Java）、vector（C++）、list（Python）都是动态数组：底层还是数组，容量不够时申请一块更大的（通常 1.5 或 2 倍）连续内存，把旧数据拷过去。所以尾部追加是均摊 O(1)（偶尔一次扩容 O(n)，摊到多次插入上平均是常数）。
五、怎么选（结论）
- 需要随机访问、按下标频繁读、大小相对稳定 → 数组 / 动态数组。
- 需要频繁在头部或已知位置插入删除、大小频繁剧烈变化 → 链表。
- 需要频繁两端操作（队列/双端队列）→ 优先
ArrayDeque（数组实现的双端队列），而不是LinkedList。
面试里不要只背“数组查询快、链表增删快”。更准确的表达是：数组下标访问 O(1)，链表在“已定位节点”时改指针 O(1)，定位成本通常另算。
| 场景 | 数组/动态数组 | 链表 |
|---|---|---|
| 访问第 100000 个元素 | 直接地址计算，O(1) | 从头走到第 100000 个，O(n) |
| 在头部插入 1 个元素 | 后面 n 个元素整体后移，O(n) | 改头指针，O(1) |
| 删除已持有的中间节点 | 仍可能需要搬移元素，O(n) | 改前后指针，O(1) |
| 顺序遍历 100 万个整数 | 连续内存，缓存友好 | 指针跳转，缓存不友好 |
举个数字例子：int 通常 4 字节，100 万个 int 数组主体约 4MB 且连续；单链表除了数据，还要为每个节点保存 next 指针和对象/节点开销，实际占用明显更高。即使两者都遍历 100 万次，数组也常因为连续访问而跑得更快。
数组第 i 个元素地址 = base + i * elementSize
链表第 i 个节点 = 从 head 出发沿 next 走 i 步六、常见误区与追问
- 误区：链表插入删除永远比数组快。 只有已经拿到插入/删除位置附近节点时，链表改指针才是 O(1)；如果还要按下标或按值查找，整体通常是 O(n)。
- 误区：数组不能变化，所以实际开发不用数组。
ArrayList、vector、Pythonlist都是动态数组，底层仍靠连续数组提供 O(1) 随机访问。 - 误区：复杂度一样时性能也一样。 数组和链表顺序遍历都是 O(n)，但数组缓存命中率高，常数因子通常更小。
- 追问：为什么数组可以随机访问？ 因为元素定长且连续存储，可以用
base + index * elementSize直接算地址。 - 追问：什么情况下链表真正有优势？ 频繁在头部、尾部或已知节点附近增删，并且不依赖下标随机访问时，链表才更合适。
- 追问：为什么 Java 里不推荐把
LinkedList当队列首选？ 多数队列场景两端操作用ArrayDeque更紧凑、缓存更友好，除非确实需要链表节点级操作。
七、加强记忆
数组是「连续+下标」，胜在随机访问和缓存友好；链表是「离散+指针」，胜在持有节点时的增删。绝大多数场景数组（动态数组）更优，只有在「频繁增删且能直接拿到节点」时链表才真正划算。