数组和链表查询效率区别

CPU 寄存器 – immediate access (0-1个CPU时钟周期)
CPU L1 缓存  – fast access (3个CPU时钟周期)
CPU L2 缓存 – slightly slower access (10个CPU时钟周期)
内存 (RAM)   – slow access (100个CPU时钟周期)
硬盘 (file system) – very slow (10,000,000个CPU时钟周期)

​ CPU缓存会把一片连续的内存空间读入，因为数组结构是连续的内存地址，所以数组全部或者部分元素被连续存在CPU缓存里面，平均读取每个元素的时间只要3个CPU时钟周期。 而链表的节点是分散在堆空间里面的，这时候CPU缓存帮不上忙，只能是去读取内存，平均读取时间需要100个CPU时钟周期。这样算下来，数组访问的速度比链表快33倍！ （这里只是介绍概念，具体的数字因CPU而异）。

操作系统局部性原理

• 时间局部性
• 空间局部性