【数据结构】二、线性表：6.顺序表和链表的对比不同（从数据结构三要素讨论：逻辑结构、物理结构（存储结构）、数据运算（基本操作））

文章目录

• • • 6.对比：顺序表&链表
    • • 6.1逻辑结构
      • 6.2物理结构（存储结构）
      • • 6.2.1顺序表
        • 6.2.2链表
        • 6.3数据运算（基本操作）
        • • 6.3.1初始化
          • 6.3.2销毁表
          • 6.3.3插入、删除
          • 6.3.4���找

            6.对比：顺序表&链表

            6.1逻辑结构

            顺序表和链表都是线性结构。

            6.2物理结构（存储结构）

            6.2.1顺序表

            顺序存储

            优点：

            1. 使用顺序存储，每个数据元素大小相同，所以可以随机访问，即可以在O(1)时间内找到第i个元素。
            2. 存储密度高，每个节点只存储数据元素。

            缺点：

            1. 拓展容量不方便，使用大片连续的空间，即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高。
            2. 插入、删除操作不方便，需要移动大量元素。

            6.2.2链表

            链式存储

            优点：

            1. 离散分配空间，分配方便，改变容量方便。
            2. 单链表的节点是通过指针来连接的，因此在插入、删除节点时不需要移动其他节点，只需要修改指针的指向即可。

            缺点：

            1. 由于链表每个节点只存储了指向下一个节点的指针，只能顺序存储，不可随机存储，所以访问节点时需要从头指针开始依次遍历访问，直到找到需要的节点，或者到达链表的结尾。
            2. 存储密度低，每个结点除了存储数据元素，还存储了指针。

            6.3数据运算（基本操作）

            6个基本操作：创销增删改查

            	顺序表	链表
            数据弹性（可扩容）		√
            增、删		√
            查找	√

            6.3.1初始化

            顺序表：

            需要预分配大片连续空间。若分配空间过小,则之后不方便拓展容量；若分配空间过大，则浪费内存资源。

            • 静态分配：静态数组，容量不可以改变。
            • 动态分配：动态数组（malloc、free）：容量可改变，但需要移动大量元素，时间代价高。

              链表：

              只需分配一个头结点(也可以不要头结点，只声明一个头指针），之后方便拓展。

              6.3.2销毁表

              顺序表：

              1. 修改Length = 0
              2. 释放空间
                 • 静态分配：静态数组，系统自动回收空间。
                 • 动态分配：动态数组（malloc、 free），需要手动free。

              链表：

              依次删除各个结点（free）。

              6.3.3插入、删除

              顺序表：

              插入/删除元素要将后续元素都后移/前移。

              时间复杂度O(n)，时间开销主要来自移动元素。

              链表：

              插入/删除元素只需修改指针即可。

              时间复杂度O(n)，时间开销主要来自查找目标元素。

              若元素占用空间很大，那么移动元素花费的时间要比查找元素花费是时间代价更大。

              6.3.4查找

              顺序表：

              按位查找：使用顺序存储，每个数据元素大小相同，所以可以随机访问，即可以在**O(1)**时间内找到第i个元素。

              按值查找：O(n)。若表内元素有序，可在 O(log_2n) 时间内找到。

              链表：

              按位查找：由于单链表每个节点只存储了指向下一个节点的指针，只能顺序存储，不可随机存储，所以访问节点时需要从头指针开始依次遍历访问，直到找到需要的节点O(n)。

              按值查找：只能遍历O(n)