顺序表和链表的优缺点

顺序表

定义：在内存中用地址连续的一块存储空间顺序存放线性表的各元素。在程序设计语言中，一维数组在内存中占用的存储空间是一维连续的存储空间，因此我们用一维数组存储数据来表示顺序表。

优点：

1. 由于顺序表是用数组来存储数据，内存空间连续，当访问数据时可以达到使用数组下标的方式随机访问。
2. CPU高速缓存的命中率高。

解释：

数据保存在内存中，数据是在CPU里进行运算的(逻辑和算术)。但是CPU速度太快，内存的速度跟不上CPU的速度。于是在CPU和内存之间存在一些寄存器和缓存器，用来保存数据。当CPU要使用数据时先在这些缓存器里读取数据，没有读到时就到内存中读取数据，然而数据读到缓存器不是一个数据一个数据读的，它是按照计算机的不同，在内存中连续读一段数据存在缓存器中，由于数组空间连续，读到缓存器中的有效数据多，所以缓存命中率高。

缺点：

1. 空间有限，不够时需要增容(性能有消耗)，并且会存在一定的空间浪费。(扩容一般按2倍或者1.5倍进行增容，如果数据存储过少，导致空间浪费)。
2. 头部或者中间插入/删除数据，要挪动数据，效率低。时间复杂度O(N)。

链表(带头双向循环链表)

定义：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

优点：

1. 按需分配内存，需要存储一个数据时，就申请一块空间，不会存在空间浪费。
2. 可以在任意位置插入和删除数据，时间复杂度位O(N)。

缺点：

1. 不支持随机访问。
2. 导致缓存污染，低命中率。

缓存拿数据为在内存中连续读一段数据，由于链表物理结构非连续，导致拿取数据时有效数字大概率只有一个，其他数据为非有效数据，可能会覆盖缓存器中的其它有效数据。

总结

顺序表和链表相辅相成的，各有的的优点和缺点。我们并不能说哪一个更好。他们应用在不同的领域会有不同的效果，所以两者我们都需要好好掌握。