跳转至

顺序表

定义

顺序表（Sequence List），即线性表的顺序存储结构，用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻，通常基于数组实现。

数组
数组
图片来源：数组 | Hello 算法

数组 vs 顺序表

数组（Array）：

  • 更倾向于一个具象且底层的概念，是物理存储结构，几乎是每一个高级编程语言中原生的数据结构（包括底层的 C）

  • 各个编程语言的封装有所差异，概念上往往只关注储存和索引

顺序表（Sequence List）：

  • 偏抽象一些，是抽象数据类型/逻辑结构

  • 在数据结构中是一个通用的概念，通常封装一些基本操作（如动态扩容、插入、删除等）

顺序表在本质上可看作是数组，其“顺序存储”的特性在编程语言中通常基于数组实现，故二者的数据结构特征基本相同：如连续存储、随机访问（时间复杂度为 \(O(1)\)）等；因此二者在大多数情况下都可理解为同一个东西。

Tip

  • 编程语言与数据结构中的某些概念之间具有一些微妙的关系。无论是上面提到的顺序表还是后面的各种线性表（如栈、队列等），其在数据结构中的概念都是抽象的逻辑结构，在实际应用中都需要基于不同编程语言中对应的封装来实现，理解二者之间的区别与联系对于进一步理解数据结构的抽象概念是学习过程中可能会遭遇到的重难点。

常用操作

由于顺序表的实现基于数组，且在形式上没有更加复杂的结构，若无特殊说明，下文中提到的"数组"基本就是指代"顺序表"。

初始化

数组的初始化分为无初始值与给定初始值两种方式。在未指定初始值的情况下，大多数编程语言会将数组元素的值初始化为 \(0\)。

访问元素

数组元素的存储基于连续的内存空间，这意味着寻址会非常容易——只需记录数组中的首个元素的地址，其余元素的地址均可通过它们与首元素的地址偏移量得出，这个偏移量就是数组的元素索引。

连续的物理空间存储（这里特指数组，只有数组具有“连续物理空间”这个概念，但这不妨碍数组能够实现顺序表的逻辑结构）使得数组的访问效率极高，能够在 \(O(1)\) 时间内随机访问其中的任一元素： 

def array_access(nums: list[int]) -> int:
    """随机访问元素"""
    random_index = random.randint(0, len(nums) - 1)
    random_num = nums[random_index]
    return random_num

插入元素

由于数组元素储存的连续性，元素与元素之间没有可以用于存放数据的余地，因此，想要在数组中插入一个元素，就需要将该元素后的所有元素都向后移动一位，然后再重新分配元素索引：

数组-插入元素
数组-插入元素
图片来源：数组-插入元素 | Hello 算法

def array_insert(nums: list[int], num: int, index: int) -> None:
    """将 num 插入 nums 的 index 处"""
    for i in range(len(nums) - 1, index, -1):
        # 从右往左向后移动数组元素，搬运区间 [index + 1, len(nums) - 1]
        nums[i] = nums[i - 1]
    nums[index] = num

有一点需要注意的是，在定长数组中，这样的不加修饰的插入算法会导致最后一个元素在插入后溢出，从而丢失数据，解决的方法是在移动元素前先对原数组执行扩容操作： 

def array_insert_improve(nums: list[int], num: int, index: int) -> None:
    """将 num 插入 nums 的 index 处，插入前执行扩容操作"""
    if index < 0 or index > len(nums):
        raise IndexError("Index out of range")
    nums.append(0)  # 先扩一位
    for i in range(len(nums) - 1, index, -1):
        # 从右往左向后移动数组元素，搬运区间 [index + 1, len(nums) - 1]
        nums[i] = nums[i - 1]
    nums[index] = num

可视化运行

全屏查看>>>

删除元素

与插入同理，删除元素就需要将待删除元素后的所有元素都向前移动一位：

数组-删除元素
数组-删除元素
图片来源：数组-删除元素 | Hello 算法

def array_remove(nums: list[int], index: int) -> None:
    """删除 nums 中 索引为 index 的元素（元素左移覆盖待删除元素）"""
    for i in range(index, len(nums) - 1):
        # 从左往右移动数组元素，搬运区间为 [index + 1, len(nums)]
        nums[i] = nums[i + 1]

同样的，这段原始算法在不加以修饰的情况下有一个比较明显的问题，就是由于数组长度并未缩短，删除操作后会导致最后一个元素的冗余。解决方法也很简单——直接移除最后一个元素即可：

Note

若在“定长数组”模型中，通常保留长度不变并只左移，尾部可填充哨兵值。

def array_remove_improve(nums: list[int], index: int) -> None:
    """删除 nums 中 索引为 index 的元素"""
    if index < 0 or index >= len(nums):
        raise IndexError("Index out of range")
    for i in range(index, len(nums) - 1):
        # 从左往右移动数组元素，搬运区间为 [index + 1, len(nums)]
        nums[i] = nums[i + 1]
    nums.pop()
可视化运行

全屏查看>>>

遍历

顺序表的的遍历通常通过循环结构实现。根据不同编程语言的封装，通常有索引遍历与对象迭代遍历（直接遍历）两种方式： 

def traversal_index(nums: list[int]) -> int:
    """通过索引遍历数组元素，并求和"""
    count = 0
    for i in range(len(nums)):
        count += nums[i]
    return count

def traversal_object(nums: list[int]) -> int:
    """直接对可迭代封装进行迭代遍历，并求和"""
    count = 0
    for num in nums:
        count += num
    return count

def traversal_enumerate(nums: list[int]) -> list[int]:
    """同时遍历数据索引与元素，并数组元素求和"""
    count = 0
    sum = 0
    for i, num in enumerate(nums):
        count += nums[i]
        sum += num
    return [count, sum]

查找元素

在数组中查找元素需要遍历数组元素，在遍历过程中匹配待查找元素，若匹配则返回对应索引，即线性查找： 

def linear_search(nums: list[int], target: int):
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    raise ValueError("Target not Found")
线性查找的时间复杂度为 \(O(n - i)\)，最坏情况下为 \(O(n)\)，即始终为匹配到待查找元素。

扩容

为保证程序安全性，避免溢出问题，绝大多数编程语言封装的数组无法直接进行任意扩容，即长度不可变。

基于这种“定长数组”模型而实现的顺序表，想要实现扩容，就只能新建一个更大的数组，然后将原数组的元素逐一复制过去： 

def array_extend(nums: list[int], enlarge: int) -> list[int]:
    """将 nums 的长度扩展 enlarge 个单位
    """
    # 初始化目标数组
    res = [0] * (len(nums) + enlarge)
    for i in range (len(nums)):
        # 复制原数组元素
        res[i] = nums[i]
    return res

整个扩展过程的操作时间主要消耗在逐一复制数组元素过程上，相当于遍历原有数组，时间复制为 \(O(n)\)。

顺序表的优缺点

优点

  • 空间效率高：元素存储在连续的内存空间，且无需考虑因为表示表中元素之间的逻辑关系而产生额外的结构开销

  • 支持随机访问：可在 \(O(1)\) 时间内访问表中的任意元素

缺点

  • 插入与删除效率低：执行插入或删除元素操作时需要大批量移动表中元素，时间复杂度为 \(O(n)\)

  • 定长数组模型约束：当线性表长度变化较大时，难以确定存储空间的容量；若需扩容，开销很大

  • 空间利用率不高：

    • 静态分配（基于定长数组）时大小可能会超过实际需求，造成内部内存碎片化

    • 动态扩容（基于动态数组）时，编程语言的扩容策略会导致一些空间浪费，形成外部内存碎片

Tip

  • 空间效率 \(\not =\) 空间利用率

  • 内部内存碎片：指分配的内存块中未被使用的部分。上面指的是在基于数组初始化一个顺序表时分配了固定大小的空间但未完全利用

  • 外部内存碎片：指内存中存在多个小的、不连续的空闲内存块，无法分配给较大的连续内存需求。上面指当（基于动态数组的）顺序表容量不足时在重新分配一块更大的连续内存，将原有元素复制到新内存，然后释放旧内存的过程中形成的小的、不连续的空闲内存块