线性表之顺序表
链表相关博客线性表之单链表
线性表之双向带头循环链表
典例：单链表典例
单链表典例2
顺序表和链表之间的区别链表中最优秀的结构是：双向带头循环链表
| 顺序表 | 链表 | |
| 优点 | 1.物理空间是连续的，方便用下标随机访问。 | 1.任意位置插入和删除效率高。 |
| 2.CPU高速缓存命中率高。 | 2.按需申请和释放空间。 | |
| 缺点 | 1.由于需要物理空间连续，空间不够需要扩容，扩容本身有一定的消耗。扩容机制还存在相应的空间浪费。 | 不支持下标的随机访问。有些算法不支持在它上面进行。如：二分查找，排序等。 |
| 2.头部或者中部插入删除数据，挪动数据，效率低。O(N) |
解释 CPU高速缓存命中率高
命中率：CPU不会直接访问内存，因为它嫌弃内存速度太慢了，会把数据加载到 三级缓存或者寄存器。
4或8 byte 小数据就放到寄存器，大数据就放到缓存。
CPU会看数据是否缓存，在就叫命中，直接访问，
不在就是不命中，先把数据从内存中加载到缓存中再访问。
