顺序表和链表的区别
学习完上两篇的顺序表和链表之后，对它们的结构都有了大致的了解，两者同为线性表，非常的相似，那么它们有什么不同呢，本篇咱们一起来找不同吧！
🐧1. 存储空间上
顺序表：物理空间一定连续。
链表：逻辑上连续，但物理上不一定连续。
🦉2. 元素访问
顺序表：可以随机访问，使用[i]（下标引用操作符）来得到第i个元素的数据。
链表：通过节点指针来遍历访问。
//顺序表的第2个元素
printf("%d\n", list->a[1]);
//链表的第2个结点的数据
printf("%d\n", head->next->data);
因为顺序表实际上就是数组，a[i] --> *(a+i)。a是数组首地址，+i将向后移动i个数组元素的空间，再*解引用的到该位置的数组元素。而链表空间不一定连续，通过->next向后移动。
🦆3. 新增
顺序表：需要判断容量，不足需要realloc()，然后才能再添加。
链表：没有容量的概念，新增就创建一个节点。
SeqListIncrease(ps);//判断是否需要扩容
newnode = BuySListNode(x);//动态申请一个节点
对于顺序表扩容，为了减少多次扩容的时间的损耗，一般每次会以原容量的2倍或1.5倍进行扩容，用空间的浪费来换时间。而链表则不存在空间的浪费。
🦔4. 插入或删除
顺序表：可能需要搬移元素，效率低，O(n)
链表：只用修改指针
🐘5. 应用
顺序表：元素高效存储+频繁访问
链表：任意位置插入和删除频繁
🐿?6. 缓存利用率
顺序表：高
链表：低
因为程序运行时，数据都是存放在内存（主存DRAM）里，当使用到数据时，再放到CPU里进行操作，从内存–>CPU的数据调用过程，并不是用多少，拿多少，而是一块一块的加载，一般是64字节(16个32位的int)，因为顺序表的物理空间连续，一次加载就能使用好几个元素，而链表则大概率不行。因此，顺序表的缓存利用率高，链表相对较低。
🦬7. 概括
| 不同 | 顺序表 | 链表 |
|---|---|---|
| 存储空间 | 物理上一定连续 | 逻辑上连续 |
| 随机访问 | 支持，O(1) | 不支持，O(n) |
| 新增 | 空间不够需要扩容 | 没有容量的概念 |
| 插入或删除 | 可能移动元素，O(n) | 只需要修改指针指向 |
| 应用 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
| 缓存利用率高 | 高 | 低 |
🦀🦀观看
待续~
