顺序表和链表的区别
- 存储空间上
顺序存储结构用一段连续的存储单元依次存储线性表的数据元素，物理上连续
链式存储结构用一组任意的存储单元存放线性表的元素，逻辑上连续，但物理上不一定连续(逻辑上就是我们想象出来的，看着它是链式的，好像是连续的)
- 随机访问性能
顺序存储结构随机访问一个元素可以用下标的方式直接访问，时间复杂度为O(1)
链式存储结构随机访问一个元素，需要从头到尾遍历，时间复杂度为O(N)
- 任意位置插入或者删除元素
顺序存储结构可能需要搬移元素，效率较低，时间复杂度为O(N)
链式存储结构只需修改指针的指向，时间复杂度为O(1)
- 插入元素容量
顺序存储结构动态顺序表中，空间不够时需要扩容，扩容会有一定的消耗，扩容后可能存在一定的空间浪费
链式存储结构没有容量的概念，按需申请空间
- 应用场景
若线性表需要频繁查找，很少进行插入和删除操作时，适合采用顺序存储结构。若需要频繁插入和删除时，适合采用单链表结构。当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构。总之，线性表的顺序存储结构和链式存储结构各有优缺点，不能简单的说哪个好，哪个不好，需要根据实际情况，来综合考虑性能
- 缓存命中率
| 不同点 | 顺序表 | 链表 |
|---|---|---|
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定连续 |
| 随机访问 | 支持O(1) | 不支持：O(N) |
| 任意位置插入或者删除元素 | 可能需要搬移元素，效率低O(N) | 只需修改指针指向 |
| 插入 | 动态顺序表，空间不够时需要扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
| 缓存命中率 | 高 | 低 |
缓存利用率
存储器的层次结构如下：
存储体系是分层的，寄存器和三级缓存是一层，这一层是围绕在cpu附近的，第二层是主存，比如就是手机的运行内存就是主存，6G，8G这些，它的特点是带电存储，第三层就是我们平时买的硬盘，第四层就是远程存储，比如你可以把你的一些数据存在云服务器上去，比如华为云，iCloud，百度网盘等等
我们的缓存命中率主要与寄存器、三级缓存与主存有关，我们下面来看这三个的关系：
寄存器和三级缓存是围绕在cpu附近的，我们大部分的数据还是在主存上的，比如我们主存上存着顺序表和链表：
假设我们写了一个程序，实现分别对顺序表和链表上的每个数据+1，这个程序会编译成指令，cpu执行指令，cpu要加数据，那加数据cpu就要访问内存，但是有可能有这种情况：cpu访问内存，cpu的速度很快，主存的速度有点慢，那么cpu总会在等主存取数据这个过程。
那么基于这个原因，cpu一般不会直接访问内存，而是把要访问的数据先加载到缓存体系，如果是<=8字节的数据会直接到寄存器，大数据就会到三级缓存，cpu直接跟缓存交互。
那么对于顺序表，cpu执行指令运算要访问内存，先要取顺序表的第一个数据，拿第一个数据的地址去缓存中找，发现没有(不命中)，因为读4个字节和读一段空间的成本是一样的，这时会把主存中这个地址开始的一段空间都读进缓存，下一次访问第二个、第三个数据等就会命中。故顺序表缓存命中率高
而对于链表，cpu要执行指令，访问内存，先取第一个节点的地址在缓存中找，发现不命中，因为链表大概率是不连续存储的，所以就算把连续的一段空间读进缓存，但可能大部分都不是我们想要的数据，再取第二个节点的地址去缓存找，发现不命中，然后一直这样进行，会有很多不命中，故这就叫缓存命中率低，并且还会造成一定的缓存污染。
这张图形象的翻译了上面的这些关系，我们要做饭，材料(数据)这些需要找，我们首先在桌子上找(即一级缓存和二级缓存)，找不到然后在冰箱里去找(三级缓存)，冰箱里没有那就需要去楼下的蔬菜水果市场(内存)去找
