💓 博客主页：C-SDN花园GGbond
⏩ 文章专栏：数据结构经典题目刨析(c语言)
目录
顺序表和链表的区别
一、底层存储空间
二、插入和删除操作
三、随机访问
四、空间利用率
五、应用场景
六、高速缓存
为什么顺序表的缓存利用率高于链表呢？
顺序表和链表的区别
一、底层存储空间
- 顺序表：底层存储空间连续，即顺序表中的所有元素都存储在连续的内存地址中。这种连续性使得顺序表在访问元素时非常高效，但也限制了其动态扩展的灵活性。
- 链表：底层存储空间不连续，链表由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针（或引用）。这种非连续性的存储方式使得链表在插入和删除元素时更加灵活，但访问元素时可能需要从头开始遍历。
二、插入和删除操作
- 顺序表：在顺序表中插入或删除元素时，可能需要移动大量元素以保持连续性。例如，在顺序表的第i个位置插入一个新元素，需要将第i个位置及其后面的所有元素都向后移动一位。这种操作的时间复杂度通常为O(n)，其中n是顺序表的长度。
- 链表：在链表中插入或删除元素时，通常只需要改变相邻节点的指针（或引用）即可。这种操作的时间复杂度通常为O(1)，但如果需要找到特定位置的节点，则可能需要从头开始遍历链表，时间复杂度为O(n)。然而，在链表中进行插入和删除操作的总体效率仍然高于顺序表，因为不需要移动大量元素。
三、随机访问
- 顺序表：支持随机访问，即可以通过索引直接访问顺序表中的任意元素。这种访问方式的时间复杂度为O(1)，非常高效。
- 链表：不支持随机访问，访问链表中的特定元素需要从头开始遍历链表，直到找到目标元素。这种访问方式的时间复杂度为O(n)，相对较慢。
四、空间利用率
- 顺序表：在预先分配的内存空间内连续存储元素，空间利用率通常较高。但是，如果分配的空间过大而实际存储的元素较少，则会造成内存浪费。
- 链表：每个节点除了存储数据外，还需要存储指向下一个节点的指针（或引用），因此每个节点的空间开销相对较大。但是，链表可以动态地添加或删除节点，更灵活地使用内存。
五、应用场景
- 顺序表：适合于需要频繁随机访问的场景，如索引数组、快速查找等。此外，顺序表的实现相对简单，因为它本质上就是数组。
- 链表：适合于插入和删除操作频繁的场景，如实现栈、队列等数据结构。链表的灵活性使得它可以在不同长度的数据结构中高效工作，而无需担心内存浪费或连续性问题。
六、高速缓存
为什么顺序表的缓存利用率高于链表呢？
这是因为CPU在访问数据时，为了更快速的访问，CPU会把内存中的数据放在更快的存储设备（高速缓存），如果访问数据在缓存，缓存命中，直接访问，不在缓存叫不命中，要把数据从内存加载到缓存，再访问，但在放入时，CPU会以自身字长（可相当于好几个要访问的数据空间大小）大小的空间把要访问的数据放入缓存中，又因顺序表是连续的所以一次可以把好几个数据放入缓存。所以缓存利用率高
| 不同点 | 顺序表（动态） | 链表 |
| 存储空间上 | 物理上和逻辑上都连续 | 逻辑上连续，物理上比一定连续 |
| 随机访问 | 支持 O（1） | 不支持 O（n） |
| 在任意位置插入和删除数据 | 可能需要搬移元素，效率低 | 只需要改变指针指向 |
| 插入 | 空间不够时需要扩容 | 没有容量概念 |
| 应用场景 | 适合于需要频繁随机访问的场景 | 适合于插入和删除操作频繁的场景 |
| 缓存利用率（高速缓存） | 高 | 低 |
