链表遍历和数组遍历谁快(CPU 缓存角度)
答案要点
- 两者都是 O(n),但数组遍历通常明显更快
- CPU 按缓存行加载,数组连续存放,空间局部性好
- 顺序访问便于硬件预取
- 链表节点分散,容易缓存未命中,主存延迟高
- 指针追逐形成依赖链,预取和乱序执行难以发挥,且指针占额外空间
易错点
- 只用大 O 比较,认为两者一样快
- 以为链表插入删除总是更快,忽略定位位置的开销
- 忽略链表节点额外的指针和分配开销
面试官常见追问
- 怎么让链表遍历更快?
- 什么时候链表比数组更合适?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。