顺序表和链表的区别

学习完上两篇的顺序表和链表之后，对它们的结构都有了大致的了解，两者同为线性表，非常的相似，那么它们有什么不同呢，本篇咱们一起来找不同吧！

• 顺序表和链表的区别
• • 1. 存储空间上
  • 黎2. 元素访问
  • 閭3. 新增
  • 璉4. 插入或删除
  • 5. 应用
  • ️6. 缓存利用率
  • 怜7. 概括

顺序表：物理空间一定连续。
链表：逻辑上连续，但物理上不一定连续。

顺序表：可以随机访问，使用[i]（下标引用操作符）来得到第i个元素的数据。

链表：通过节点指针来遍历访问。

//顺序表的第2个元素
printf("%dn", list->a[1]);
//链表的第2个结点的数据
printf("%dn", head->next->data);

因为顺序表实际上就是数组，a[i] --> *(a+i)。a是数组首地址，+i将向后移动i个数组元素的空间，再*解引用的到该位置的数组元素。而链表空间不一定连续，通过->next向后移动。

顺序表：需要判断容量，不足需要realloc()，然后才能再添加。

链表：没有容量的概念，新增就创建一个节点。

SeqListIncrease(ps);//判断是否需要扩容
newnode = BuySListNode(x);//动态申请一个节点

对于顺序表扩容，为了减少多次扩容的时间的损耗，一般每次会以原容量的2倍或1.5倍进行扩容，用空间的浪费来换时间。而链表则不存在空间的浪费。

顺序表：可能需要搬移元素，效率低，O(n)

链表：只用修改指针

顺序表：元素高效存储+频繁访问

链表：任意位置插入和删除频繁

顺序表：高

链表：低

因为程序运行时，数据都是存放在内存（主存DRAM）里，当使用到数据时，再放到CPU里进行操作，从内存–>CPU的数据调用过程，并不是用多少，拿多少，而是一块一块的加载，一般是64字节(16个32位的int)，因为顺序表的物理空间连续，一次加载就能使用好几个元素，而链表则大概率不行。因此，顺序表的缓存利用率高，链表相对较低。

呂呂观看

待续~