顺序表和链表的区别_顺序表与链表的异同

由上表可总结出：

顺序表优点：

1. 物理空间是连续的，方便用下标随机访问。

2. CPU高速缓存命中率更高

顺序表缺点：

1. 由于需要物理空间连续，空间不够需要扩容。扩容有性能消耗。每次扩容还存在一定的空间浪费

2. 头部或者中部插入删除，挪动数据，效率低。O(N)

链表优点：

1. 任意位置插入删除数据效率高。O(1)

2. 按需申请和释放空间

链表缺点：

不支持下标的随机访问。有些算法不适合在它上面进行。如：二分查找、排序等。

注：缓存利用率指的的是高速缓存的命中率

CPU在读取数据时，CPU是不会直接访问内存，因为它嫌弃内存的速度太慢了，所以会把数据加载到三级缓存或者寄存器上，4/8byte小数据就放到寄存器上，大数据就放到缓存

高速缓存的命中率是指：CPU会看数据是否在缓存，在就叫命中，直接访问；不在就叫不命中，先把数据从内存加载到缓存，再进行访问

CPU认为你有可能除了访问当前这块内存的数据以外，还会访问当前这块内存的后面的内存的数据，所以在读取时，还会预读取后面那块内存的数据，而在数组中由于物理空间和逻辑空间都是连续的，所以命中率会更高，链表是逻辑空间是连续的，物理空间不一定是连续的，所以命中率更低。

                                                        存储器的层次结构

更多的CPU缓存知识：与程序员相关的CPU缓存知识