ArrayList 在百万数据量下的遍历性能显著优于 LinkedList，尤其是使用索引访问时，LinkedList 可能慢 10 倍以上。随机访问场景必须选 ArrayList，LinkedList 仅适合频繁头尾插入且使用迭代器遍历的场景。
先说结论：百万数据遍历首选 ArrayList，LinkedList 仅在与迭代器配合且频繁增删时考虑。
- 适合：读多写少、随机访问、内存敏感场景
- 重点看：遍历方式是否触发指针跳跃
- 别忽略：LinkedList 百万级数据内存占用可能高出 5 倍
快速处理思路
代码中涉及 List 遍历优化时，先确认底层实现类型，再调整遍历写法。若无法修改集合类型，必须避免在 LinkedList 上使用索引循环。
1. 检查 List 实现类：确认是 ArrayList 还是 LinkedList。
2. 检查遍历方式：索引 for 循环、增强 for 循环或 Iterator。
3. 调整策略：LinkedList 强制改用迭代器，ArrayList 保持索引或增强 for 均可。
为什么会这样
内存布局决定了 CPU 缓存命中率，ArrayList 连续内存适合预取，LinkedList 分散节点导致缓存失效。ArrayList 底层是动态数组，内存连续，通过索引计算偏移量直接访问，时间复杂度 O(1)。LinkedList 底层是双向链表，节点分散在堆内存中，每次访问需顺着指针跳转，时间复杂度 O(n)。
百万级数据下，linkedList.get(500000) 可能比 arrayList.get(500000) 慢 10 倍以上，这是指针跳跃带来的 CPU 缓存失效和分支预测失败导致的实测结果。内存方面，100 万个 Integer 对象，ArrayList 约占 4MB，LinkedList 因额外存储前后指针轻松突破 20MB。
分步处理
1. 定位热点代码：使用性能分析工具查看 List 遍历耗时。
2. 确认集合类型：检查初始化代码是 new ArrayList<>() 还是 new LinkedList<>()。
3. 修改遍历逻辑：若为 LinkedList 且使用 for(int i=0;i<list.size();i++)，改为增强 for 循环或 Iterator。
4. 评估内存影响：若数据量极大，确认 LinkedList 额外内存开销是否在堆内存承受范围内。
5. 回归测试：修改后重新运行性能测试，确认耗时下降且功能正常。
怎么验证是否生效
使用 Java Microbenchmark Harness (JMH) 或简单的时间戳日志对比修改前后耗时。记录遍历开始和结束的系统毫秒时间，计算差值。观察 GC 日志，LinkedList 因创建更多 Node 对象，Young GC 频率可能更高，修改为 ArrayList 后 GC 压力应降低。
常见坑
1. 在 LinkedList 上使用索引 for 循环：这是最严重的性能陷阱，每次 get(i) 都会重新遍历链表。
2. 泛型工具类隐式调用 get(0)：某些框架内部可能调用 get 方法，传入 LinkedList 会触发遍历。
3. 误用 ArrayList 模拟队列头部插入：ArrayList.add(0, e) 需要移动所有元素，性能远差于 LinkedList.addFirst(e)。
4. 忽略内存开销：百万级数据下 LinkedList 内存占用可能是 ArrayList 的 5 倍以上，易引发 OOM。
常见问题
LinkedList 应该用什么方式遍历？
必须使用增强 for 循环或 Iterator，严禁使用索引 for 循环。
ArrayList 和 LinkedList 内存差多少？
百万级 Integer 数据下，ArrayList 约占 4MB，LinkedList 可能超过 20MB。
什么时候必须用 LinkedList？
仅在频繁头部插入删除且不使用随机访问的场景，如命令栈或日志缓冲。
随机访问性能差多少？
百万数据量下，LinkedList 随机访问可能比 ArrayList 慢 10 倍以上。
参考来源
1. Java 开发者必看!ArrayList 和 LinkedList 的性能厮杀：选错一次，代码慢成蜗牛
2. Java 中的 ArrayList 和 LinkedList 有什么区别_性能对比与选型指南
3. Java 中关于 ArrayList 和 LinkedList 遍历效率
4. ArrayList 与 LinkedList 性能对比