为什么数组与链表的遍历都是O(n)，数组仍可能更快？

为什么数组与链表的遍历都是O(n)，数组仍可能更快？

1. Big-O保证数组使用更少的CPU指令。
2. 相邻数组槽位的缓存局部性可能优于单独分配的节点。
3. 链表必须在遍历时对节点排序。
4. 数组总会内联存储语言中的每一种值。