数据结构和算法学习记录——总结顺序表和链表（双向带头循环链表）的优缺点、CPU高速缓存命中率

顺序表和链表

两个结构各有优势，严格来说，他们是相辅相成的。

顺序表

优点

1. 支持随机访问（用下标访问），需要随机访问结构支持的算法可以很好的适用。
   
2. CPU高速缓存命中率较高

缺点

1. 在头部或中部插入删除数据时，时间效率低。O（N）
   
2. 是占用的连续的物理空间，空间不够时需要进行扩容。
   

• 扩容有一定程度的空间消耗
  
• 为了避免频繁扩容，一般我们都按倍数去扩容，用不完的这个空间就存在了空间浪费

链表（双向带头循环链表）

优点

1. 任意位置插入删除数据都很方便，时间效率高。O（1）
   
2. 可以按需申请空间。（用多少申请多少，且不会造成空间消耗）
   

缺点

1. 不支持随机访问（用下标访问）。这意味着：一些排序和二分查找等在这种结构上并不适用。
   
2. 链表存储一个值，同时也要存储链接指针，也有一定的消耗（很小）。
   
3. CPU高速缓存命中率较低。

简单解释CPU高速缓存命中率

存储体系大类别的分，可以分为带电存储和不带电存储。

主存往上是带电存储，往下是不带电存储。

了解CPU高速缓存命中率需要多加了解的两个存储设备：三级缓存、寄存器

寄存器的速度是非常快的，而主存的速度相对来说很慢，当CPU要进行计算时，对于小的数据：会将数据从主存加载到寄存器中，计算完之后再返回内存；对于大的数据：则是会将数据加载到三级缓存中，寄存器从缓存中拿取数据进行计算，计算完再返回内存。

在访问存储数据1的内存位置 0x00123400时，会先看它是否存在于缓存中。

如果在，就直接访问；如果不在，就先加载到缓存中，再进行访问。

加载时，会加载一块连续的内存，假设一次加载20个字节（具体大小取决于硬件体系）。那顺序表的一块空间就能一次被命中到多个（即加载到多个的数据）；而链表的内存空间不一定连续，可能加载的一块连续空间中命中不到链表的下一个结点。

end