序言

• 序言
• • 链表
  • • 顺序表

序言

本篇博客主要讨论的是顺序表以及双向循环链表的一些比较
但是两个结构都是相辅相成的

链表

优点：
1，任意位置插入删除数据效率高
2，按需申请释放开辟内存
缺点：
不支持下标的随机访问，不支持一些算法，如二分，排序等

顺序表

缺点
1.由于空间是连续的，空间不够是需要扩容，扩容本身存在一定消耗，且有事会有大量空间浪费
2.头部或者中间的插入删除数据时效率教低
优点
1，物理空间是连续的，方便用下表随机访问
2.CPU高速缓存命中率更高
这篇短篇博客主要想讲的是这个。

我们先看一张图

编译链接生成后，生成一个可执行程序，CPU要去访问内存，这个时候假设有两个程序，分别是双向循环链表的打印以及顺序表的打印

CPU要去内存中拿它们，虽然内存很快，但那是相对于硬盘而言的，相对于CPU的话，内存的速度是很慢的，所以为了方便CPU，所以有了三级缓存和寄存器，这两个是同一个等级的，但是寄存器稍微比三级缓存快点
因此

CPU不会直接访问内存，因为它嫌弃内存速度太慢了，会把数据加载到三级缓存或寄存器
4或8byte小数据放到寄存器
较大数据就到三级缓存

所以，因此加入有这两串数字，一个是数组，还有一个是链表，
CPU会先看数据是否在缓存，（主要是看三级缓存中是否有数据）在就叫命中，直接访问，不在就叫不命中，得先把数据加载到缓存，再访问。

因此，如果都是从头开始遍历数据的话，缓存中肯定是没有数据的，要从头开始加载，加载时有局部性原理的，不会一byte一byte的加载会是一连串一连串的空间加载。打个比方，数组只需要加载一次就可以全部命中，但是由于链表的空间不是连续的，加载一次或者是更多次都不一定会加载完，所以这样比较的话顺序表的CPU缓存命中率高。