链表缓存效率差主因是节点内存分布不连续，破坏空间局部性，导致高缓存未命中率、低缓存行利用率及分支预测与预取器失效；优化可采用块节点、对齐、软件预取或改用数组等缓存友好结构。

链表在处理大批量数据时，缓存行（cache line）效率通常较差，核心原因在于其节点在内存中**非连续分布**，导致 CPU 缓存局部性严重缺失。

链表破坏空间局部性，加剧缓存未命中

现代 CPU 缓存以固定大小的缓存行（常见 64 字节）为单位加载内存。数组等连续结构能一次预取多个相邻元素，而链表节点通常由 malloc 或 new 动态分配，物理地址随机分散。遍历一个含百万节点的链表时，每访问下一个节点，大概率触发一次新的缓存行加载——即使节点本身很小（如仅两个指针），也无法共享同一缓存行，造成大量缓存未命中（cache miss）。

• 典型表现：L1/L2 缓存命中率可能低于 20%，远低于数组的 90%+；
• 实测对比：对 10M 元素做顺序求和，链表耗时常是数组的 3–5 倍，主因即缓存失效引发的内存延迟放大；
• 影响被进一步放大：若节点跨页或遭遇 NUMA 远程内存访问，延迟更高。

节点大小与缓存行对齐的实际影响

单个链表节点若远小于缓存行（如 16 字节的 int + two pointers），会造成显著的**缓存行利用率浪费**。64 字节缓存行中仅用 16 字节，其余 48 字节空载加载，带宽和缓存容量都被低效占用。

• 优化思路：可将多个逻辑项打包进一个“块节点”（chunked list / unrolled linked list），例如每节点存 8 个数据 + 1 个 next 指针，提升单次缓存行有效载荷；
• 注意对齐：确保节点起始地址按缓存行边界对齐（如 alignas(64)），避免单节点跨两个缓存行，否则一次访问触发两次加载；
• 但过度对齐会增加内存碎片和分配开销，需权衡。

指针跳转带来分支与预取器失效

链表遍历本质是不可预测的间接跳转（indirect branch）：CPU 无法可靠推测 next 指针目标地址，导致硬件分支预测器失准，流水线频繁清空。同时，多数硬件预取器（hardware prefetcher）针对**固定步长的线性访问模式**设计，对随机指针跳转基本无效，无法提前加载后续节点。

• 软件预取（__builtin_prefetch）可部分缓解，但需手动插入且时机敏感；
• 某些场景下，改用“数组+索引”模拟链表（如 arena allocator + free list），保留逻辑链式关系，但物理布局可控，能恢复部分局部性；
• 若必须用链表，考虑将热点链表节点预先 pin 到 L3 缓存附近（如使用 mlock 或 NUMA 绑定），减少迁移开销。

替代方案：何时该放弃链表？

当数据量达十万级以上且需高频顺序访问时，应优先评估更缓存友好的结构：

• 动态数组（vector）：支持 O(1) 随机访问、高缓存友好，插入/删除尾部廉价；
• 分段数组（deque）：两端高效，内部由小块连续数组组成，兼顾局部性与增删灵活性；
• B-tree 变体（如 B+ tree）：节点大小接近缓存行，天然适配层级存储，适合磁盘/内存混合场景；
• 跳表（skip list）虽也是指针结构，但多层索引可降低平均跳转次数，配合合理层级设计，缓存表现优于朴素链表。