顺序表和链表
两个结构各有优势，严格来说，他们是相辅相成的。
顺序表
优点
- 支持随机访问（用下标访问），需要随机访问结构支持的算法可以很好的适用。
- CPU高速缓存命中率较高
缺点
- 在头部或中部插入删除数据时，时间效率低。O（N）
- 是占用的连续的物理空间，空间不够时需要进行扩容。
- 扩容有一定程度的空间消耗
- 为了避免频繁扩容，一般我们都按倍数去扩容，用不完的这个空间就存在了空间浪费
链表（双向带头循环链表）
优点
- 任意位置插入删除数据都很方便，时间效率高。O（1）
- 可以按需申请空间。（用多少申请多少，且不会造成空间消耗）
缺点
- 不支持随机访问（用下标访问）。这意味着：一些排序和二分查找等在这种结构上并不适用。
- 链表存储一个值，同时也要存储链接指针，也有一定的消耗（很小）。
- CPU高速缓存命中率较低。
简单解释CPU高速缓存命中率
存储体系大类别的分，可以分为带电存储和不带电存储。
主存往上是带电存储，往下是不带电存储。
了解CPU高速缓存命中率需要多加了解的两个存储设备：三级缓存、寄存器
寄存器的速度是非常快的，而主存的速度相对来说很慢，当CPU要进行计算时，对于小的数据：会将数据从主存加载到寄存器中，计算完之后再返回内存；对于大的数据：则是会将数据加载到三级缓存中，寄存器从缓存中拿取数据进行计算，计算完再返回内存。
在访问存储数据1的内存位置 0x00123400时，会先看它是否存在于缓存中。
如果在，就直接访问；如果不在，就先加载到缓存中，再进行访问。
加载时，会加载一块连续的内存，假设一次加载20个字节（具体大小取决于硬件体系）。那顺序表的一块空间就能一次被命中到多个（即加载到多个的数据）；而链表的内存空间不一定连续，可能加载的一块连续空间中命中不到链表的下一个结点。
end
