顺序表和链表优缺点以及区别
顺序表和链表的区别
- 顺序表
- 优点
- 缺点
- 链表
- 优点
- 缺点
- 顺序表和链表不同点
顺序表
优点
1.尾插尾删效率高
2.支持随机访问
3/相比于链，cpu高速缓存命中率更高
缺点
1.在头部和中部插入删除效率底
2.需要大片连续空间，改变容量不方便
链表
优点
1.不需要大片连续空间，改变容量方便
2.任意位置插入删除效率高
缺点
1.不支持随机访问
顺序表和链表不同点
| 不同点 | 顺序表 | 链表 |
|---|---|---|
| 存储空间 | 物理上一定连续 | 逻辑上连续，但物理上不一定连续 |
| 随机访问 | 支持O(1) | 不支持O(N) |
| 任意位置插入或删除元素 | 可能需要搬移元素，效率低)O(N) | 只需要修改指针即可 |
| 插入 | 动态顺序表，空间不够时需要扩容 | 按需申请 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
| 缓存利用率 | 高 | 低 |
解释一下什么是命中率
看下面一张图
cpu执行指令，不会直接访问内存（主存）
1.先看数据在不在三级缓存（L1，L2，L3），在（命中），直接访问
2.不在（不命中），先加载到缓存，在访问