目录
顺序表：
首先我们先来随意定义一个顺序表
#include<stdio.h>
typedef int SLDataType;
typedef struct SeqList {
SLDataType* arr;//指向开辟的数组
size_t size;//有效数
size_t capacity;//开辟的空间总数
}SeqList;
我们这里就可以直观的看出顺序表的优点
顺序表的优点：
在物理空间上是连续的，用下标可以很方便的访问（擅长二分法等）
但是缺点也是显而易见的
顺序表的第一个缺点：
如果我的size==capacity，即我数放满了，需要扩容的话，那么我们就有两种方式扩容
（一）频繁的少量扩容，一次扩一个，一次扩一个，这样使得扩容的消耗变得非常巨大
（二）大量的扩容，比如翻倍从100个—>200个，那么假如我只存放101个数，就会浪费99个额外的空间，就会造成大量空间浪费
顺序表的第二个缺点：
如果我需要修改数据（比如头插尾插）
以尾插举例，那么我需要遍历整个数组找到末尾的数字，然后在他后面插入。
如果这个数组有1亿个数字，那么计算机需要遍历1亿个数（有些夸张但是那个意思），才能插入，这种挪动数字的效率非常低下O（N）；
链表：
我们这里随意定义一个带头双向循环链表
typedef int LTDatatype;
typedef struct ListNode {
LTDatatype Data;//存储数据
struct ListNode* next;//指向下一个数
struct ListNode* prev;//回指
}ListNode;
?我们这里也可以直观的看出链表的优点
链表的第一个优点：
链表是在内存中任意位置开辟的，能够按需申请和释放空间，不会造成空间浪费
链表的第二个优点：
如果我现在需要修改数据（头插，尾插等）
这里拿尾插举例，我们只需要malloc一个新的结点，让结构体的最后一个指针（tail=phead->prev）指向新的结点
（直接就能找到最后一个结点，不用遍历数组），所以修改数据效率非常高O（1）；
?链表的缺点：
因为是在内存中随机开辟，所以像二分查找，排序等需要物理空间上连续的算法无法支持
?总结：
顺序表的优点：
1、物理空间是连续的，方便用下标访问。
2、CPU高速缓存命中率高（看后文补充知识，了解即可）
缺点：
1、由于物理空间连续，扩容时容易造成空间浪费和频繁扩容。
2、挪动数据的效率低下O（N）；
链表的优点：
1、挪动数据的效率高O（1）；
2。能按需申请释放空间，不会造成内存浪费。
缺点：
不支持下标随机访问，二分法或排序等算法不适合运行。
补充知识CPU高速缓存命中率：
编译链接，生成可执行程序，cpu会执行这个程序，然后cup就会去访问内存。
但是对于处理数据，cup相对于内存处理的速度快很多。
打个比方，一个二十岁的青壮年和一个九十岁的老大爷一起合作搬砖，那么这个二十岁的青壮年大部分时间都在等待老大爷给他递砖头，那么这样处理的效率就会非常低下。
所以cpu会把数据存储到三级缓存或者寄存器，而不会直接访问内存。
一些4或者8byte的小数据就放到寄存器，而一些很大的数据就放到缓存里面。
那么具体cpu会怎么做呢，下面是顺序表和链表的情况
?顺序表：
假如我们cpu是第一次遇到这个数字，图中顺序表的”1”（因为在实际过程中，有可能在运行其他程序的时候偶然间访问过这个数字，所以我们这里假设第一次遇到），那么cpu没有见过，我们就说这次cpu没有命中
那么cup就会接连访问”1”这个数的后面连续的几个空间（这个和电脑配置有关，每台可能不一样），然后访问的接下来几个数，就是cpu已经知道的数，所以cpu命中
?链表：
那么同理，如果是链表，那么因为链表是在内存中随即开辟和生成的，假如我的1，2,3,4都在内存中隔得很远，我cup访问”1”的时候，连续访问1的后面几个空间，都没有访问到2，那么接下来访问2的时候cpu还是不认识2，所以cup会一直未命中
