前言
顺序表是用一段
物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
| 不同点 | 顺序表 | 链表 |
| 存储空间 | 物理空间一定连续 | 逻辑上是连续的，物理上不一定连续 |
| 对于随机访问 | 可以随机访问，O(1) | 不支持随机访问，O(N) |
| 对任意位置插入或删除元素 | 可能需要搬移元素，效率低，复杂度O(N) | 实现只需修改指针指向 |
| 插入元素 | 对于动态顺序表，空间不够是需要扩容 | 不需要扩容，没有容量的概念 |
| 适用场景 | 元素高效存储和频繁访问（下标随机访问） | 对任意位置插入和删除频繁 O(1) |
| 缓存利用率 | 高 | 低 |
对于缓存命中率高低理解：
数据存储在内存中，cpu和内存交换数据时，会有一个高速缓存区（SRAM)，缓存区一次性读取一定字节的数据，顺序表由于物理空间是连续的，读取开头的地址时会把后面的数据一起带进去，这样就会减少遍历的时间。而链表物理空间不一定连续，就会需要更长的遍历时间，因此缓存利用率更低。
图示：存储器层次结构
更加深入了解请参考耗子叔的一篇博客：CPU缓存知识
