【数据结构】顺序表和链表的对比，在各种情况下如何选择

顺序表详���内容：

【数据结构】线性表 顺序表（动态、静态分配，插入删除查找基本操作）解析+完整代码

单链表详细内容：

【数据结构】单链表解析+完整代码（插入、删除、尾插法、头插法、按值和按位查找、前插和后插）带头结点和不带两种实现

3.5 顺序表和链表的对比

• 逻辑结构上

  • 相同：都属于线性表，都是线性结构。

  • 存储结构上

    • 不同点：

      	顺序表	链表
      优点	支持随机存取、存储密度高	离散空间分配方便，改变容量容易
      缺点	大量连续内存不方便，改变容量麻烦	不可随机存取，存储密度低

    • 基本操作

      • 1.创建

        顺序表：容易浪费内存。

        链表：方便拓展。

      • 2.销毁操作

        顺序表：修改Length=0，静态分配系统自动回收空间，动态分配需要手动free。

        链表：依次free结点。

      • 3.增、删

        顺序表：需要将元素前移/后移，时间复杂度 O ( n ) O(n) O(n)，开销来自移动元素。

        链表：只 O ( n ) O(n) O(n)，开销主要来自查找目标元素。 代价更低。

      • 4.查找操作

        顺序表：按位查找 O ( 1 ) O(1) O(1)，按值查找 O ( n ) O(n) O(n)。效率更高。

        链表：两种查找都是 O ( n ) O(n) O(n)。

      • 如何选择用链表or顺序表？

        • 表长难估计，经常增、删元素 ——链表。

        • 表长可估计，查询操作多 ——顺序表。