顺序表和链表的比较

这两个结构各有优势，相辅相成。

顺序表：

优点：

1.支持随机访问。

2.CPU高速缓存命中率更高。(物理空间连续)

缺点：

1.头部和中部插入和删除时间效率低(O(n))。

2.连续的物理空间，空间不够后需要增容：

a.增容有一定程度的消耗。

b.为了避免频繁的进行增容，我们一般都按照倍数去增容，用不完会有一定的空间浪费。

链表(带头循环双链表)

优点：

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

2.按需申请和释放空间。

缺点：

1.不支持随机访问。(一些排序和二分查找不适用)

2.每存一个值需要存储两个指针地址，有一定的消耗。

3.CPU高速缓存命中率较低。(物理空间不连续)