顺序表和链表的区别
| 不同点 | 顺序表 | 链表（带头双向循环） |
|---|
| 存储空间 | 物理上一定连续 | 逻辑上连续物理上不一定连续 |
| 随机访问（用下标随机访问） | 支持：O(1) | 不支持：O(N) |
| 任意位置插入或者删除元素 | 可能需要搬移元素，效率低O(N) | 只需修改指针指向 |
| 插入 | 动态顺序表，空间不够时需要扩容（扩容本身有消耗，空间浪费（通常每次扩大为原来的2倍）） | 没有容量的概念（按需申请释放） |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入或删除频繁 |
| 缓存利用率 | 高 | 低（可能造成缓存污染） |
从表中对比可以看出，二者是互补的
链表纵有万般好，但是也有明显的不足：不支持用下标随机访问
小的数据加载到寄存器，大的数据加载的和缓存
