点击蓝字
山月
关注我们
第十六节 顺序表与链表的比较
我们从几点特性来对两种线性表进行比较：
| 特性 | 顺序表 | 链表 |
|---|---|---|
| 存储方式 | 连续的内存空间 | 分散的内存空间 |
| 插入操作 | 在中间或头部插入需要移动元素 | 在中间或头部插入不需要移动元素 |
| 删除操作 | 删除元素后需要移动元素 | 删除元素后不需要移动元素 |
| 随机访问 | 时间复杂度为 O(1) | 时间复杂度为 O(n) |
| 内存分配 | 静态分配或动态扩展 | 动态分配 |
| 空间使用 | 可能有一定的空间浪费（预留足够的空间） | 没有空间浪费 |
| 内存管理 | 不需要频繁的内存分配和释放 | 需要频繁的内存分配和释放 |
| 插入删除效率 | 中间和头部插入删除效率低 | 中间和头部插入删除效率高 |
| 内存访问 | 可以利用 CPU 缓存提高访问效率 | 由于存储位置分散，可能导致缓存未命中 |
由于两种线性表具有不同的特性，它们分别具有以下优缺点：
顺序表的优点：
随机访问速度快：可以通过下标直接访问元素，时间复杂度为 O(1)。
内存利用率高：顺序存储在连续的内存空间中，没有额外的指针开销，内存利用率高。
CPU 缓存友好：连续存储可以利用 CPU 缓存，提高访问效率。
适合频繁的查找操作：由于支持随机访问，适合频繁的查找操作。
顺序表的缺点：
插入删除效率低：在中间或头部插入删除元素时，需要移动元素，时间复杂度为 O(n)。
静态大小限制：顺序表的大小在创建时就固定了，如果需要扩容，可能会涉及大量的数据迁移。
内存碎片问题：在频繁的插入删除操作后，可能会造成内存碎片，影响内存的利用效率。
链表的优点：
插入删除效率高：在中间或头部插入删除元素时，不需要移动元素，时间复杂度为 O(1)。
动态扩展：链表的大小可以动态增长，不受固定大小限制。
灵活性：链表对内存的利用更加灵活，可以动态分配内存，减少内存浪费。
适合频繁的插入删除操作：由于插入删除操作效率高，适合频繁的插入删除操作。
链表的缺点：
随机访问效率低：无法通过下标直接访问元素，需要遍历查找，时间复杂度为 O(n)。
内存开销大：每个节点需要额外的指针空间，增加了内存开销。
CPU 缓存不友好：存储位置分散，可能导致 CPU 缓存未命中，访问效率降低。
前面我们提到了动态与静态，什么是静态，什么是动态？
| 类型 | 特点 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|---|
| 静态顺序表 | 使用静态数组实现，大小固定，编译时确定 | 存储连续，访问效率高 | 大小固定，插入删除困难 | 空间需求明确，大小不变化的场景 |
| 动态顺序表 | 使用动态数组实现，大小可以动态调整，运行时确定 | 大小可动态调整，适应性强 | 动态调整可能导致频繁的内存分配与释放 | 数据量不确定，需要动态管理大小的场景 |
| 静态链表 | 使用静态数组实现链表，大小固定，编译时确定 | 可以动态插入删除节点，不需要频繁的内存分配与释放 | 大小固定，空间利用率低 | 数据量确定，但需要频繁插入删除节点的场景 |
| 动态链表 | 使用动态分配内存实现链表，大小可以动态调整，运行时确定 | 大小可动态调整，适应性强 | 动态调整可能导致频繁的内存分配与释放 | 数据量不确定，需要频繁插入删除节点的场景 |
总而言之，静态表是指在程序运行前就确定了大小的表，其内存空间在编译或运行前就已经分配好，并且在程序运行过程中大小不会改变。静态表通常使用数组来实现，因此具有较高的访问效率。比如说使用静态数组实现的静态顺序表，大小固定，不具备动态扩展的能力。使用数组实现的静态链表，静态链表的实现利用了数组元素中的指针成员来模拟链表节点之间的指针关系。它的具体实现是将数组中的每个元素看作一个节点，节点中除了存储数据之外，还存储一个指向下一个节点的索引（通常是数组下标）。
而动态表是一种可以动态地调整大小以适应存储数据的需求的数据结构。动态表通常基于动态内存分配技术实现，能够在运行时动态地增加或减少存储空间。比如说动态顺序表是一种基于数组实现的动态数据结构。它具有顺序表的特点，支持随机访问、元素的插入和删除等操作。当数组空间不足以存储新增的元素时，动态顺序表会动态地扩展数组的大小，以容纳更多的元素。比如使用动态数组（vector）等数据结构。动态链表是一种通过节点之间的指针来组织数据的线性表结构，比如说单链表，循环链表与双向链表，list容器就是动态链表的实现。动态表相比于静态表具有更高的灵活性，能够在运行时动态地适应数据的变化。
这节的知识学习就到这里，感谢观看！欢迎各位的点赞与关注！您的点赞和关注是我学习更新的动力！
往期推荐
• end •
喜欢我们的内容就点“在看”分享给小伙伴哦
