顺序表和链表的区别
学习完上两篇的顺序表和链表之后,对它们的结构都有了大致的了解,两者同为线性表,非常的相似,那么它们有什么不同呢,本篇咱们一起来找不同吧!
🐧1. 存储空间上
顺序表:物理空间一定连续。 链表:逻辑上连续,但物理上不一定连续。
🦉2. 元素访问
顺序表:可以随机访问,使用[i] (下标引用操作符)来得到第i个元素的数据。
链表:通过节点指针来遍历访问。
printf("%d\n", list->a[1]);
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) | 只需要修改指针指向 | 应用 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 | 缓存利用率高 | 高 | 低 |
🦀🦀观看
待续~
|