ArrayList在随机访问和顺序遍历中均占优：随机访问为O(1)，依赖连续内存与缓存预取；顺序遍历因内存局部性高，CPU缓存命中率远超LinkedList的离散节点访问。
随机访问和顺序遍历是两种常见操作，但 ArrayList 和 LinkedList 在海量数据下表现差异显著——关键不在“快慢”本身，而在底层结构决定的访问路径是否匹配你的使用方式。
随机访问：ArrayList 明显占优
随机访问指通过索引（如 get(50000)）直接定位元素。ArrayList 底层是连续数组，CPU 可高效利用缓存行，一次内存预取就能覆盖多个相邻元素；时间复杂度稳定为 O(1)。实测在百万级元素中执行 1 万次随机访问，ArrayList 耗时通常在 2–5 毫秒内。
LinkedList 没有索引映射能力，get(i) 必须从头或尾出发遍历链表（JDK 中做了优化，会自动选择较短路径，但仍是 O(n)）。同样百万数据、1 万次随机访问，耗时常达 15–40 毫秒，且随数据量增长线性恶化。
- 不推荐用 LinkedList 做下标读取，尤其在循环中反复调用 get(i)
- 若业务强依赖索引查询（如分页跳转、坐标映射），ArrayList 是唯一合理选择
- 注意：即使 LinkedList 实现了 List 接口，它未实现 RandomAccess 标记接口，Java 集合工具类（如 Collections.binarySearch）会据此规避低效路径
顺序遍历：ArrayList 依然更稳更快
很多人误以为“链表遍历应该不差”，但实际在海量数据下，ArrayList 的顺序遍历（for-each 或传统 for 循环）仍普遍优于 LinkedList。原因在于内存局部性：数组元素物理连续，CPU 缓存命中率高；而 LinkedList 的 Node 分散在堆中，每次访问 next 指针都可能触发一次缓存未命中，带来显著延迟。
测试显示：遍历 100 万个整数，ArrayList 平均耗时约 1.8 毫秒，LinkedList 约 12–16 毫秒。差距主要来自硬件层面的访存效率，而非算法逻辑。
- 遍历时优先用增强 for 循环（本质调用 iterator），对两者都适用，但 ArrayList 的迭代器是索引驱动，开销极小
- 避免在遍历 LinkedList 时混用 get(i) —— 这会让性能雪上加霜
- 如果遍历后常需插入/删除当前节点附近元素，LinkedList 的迭代器（ListIterator）支持 add()、remove() 等 O(1) 操作，这是它的独特优势场景
什么情况下 LinkedList 遍历才可能“不拖后腿”？
仅当满足全部以下条件时，LinkedList 的遍历劣势才可能被弱化：
- 数据规模不大（例如几千以内），缓存影响不明显
- 遍历与频繁的首尾增删交织（如实现栈、队列、滑动窗口），此时 LinkedList 的结构性优势抵消了遍历开销
- 运行环境内存带宽极高、CPU 缓存足够大（如某些云原生容器场景），但这类情况非常规
纯检索、纯读取、高吞吐遍历——ArrayList 几乎总是更合适的选择。
