Python中数组数据结构的深度解析

补充数组前置知识 

数组（array）是一种线性数据结构，其将相同类型的元素存储在连续的内存空间中。

元素在数组中的位置称为该元素的索引（index）。

元素内存地址 = 数组内存地址(首元素地址) + [元素长度 * 元素索引](地址偏移量)。

索引本质上是内存地址的偏移量。

关于首个元素的索引为0可以这么理解：因为索引本质上是内存地址的偏移量，由于首个元素没有偏移量，或者可以说首个元素的内容地址偏移量为0，因此首个元素的索引为0。

在数组中访问元素是非常高效的，我们可以在O(1)时间内随机访问数组中的任意一个元素。

静态数组

「静态数组」就是一块连续的内存空间，我们可以通过索引来访问这块内存空间中的元素，这才是数组的原始形态。

静态数组的使用

 静态数组的定义方法：

严格来说，Python 没有静态数组的定义方式 

我们暂且使用列表模拟静态数组

# 定义一个大小为10的静态数组
arr = [0] * 10

# 使用索引赋值
arr[0] = 1
arr[1] = 2

# 使用索引取值
a = arr[0]

# 初始化数组
arr: list[int] = [0] * 10
nums: list[int] = [1,2,3,4,5]

静态数组本质上就是一块连续的内存空间

数组的访问

def random_access(nums: list[int]) -> int:
    """随机访问元素"""
    # 在区间 [0, len(nums)-1] 中随机抽取一个数字
    random_index = random.randint(0, len(nums) - 1)
    # 获取并返回随机元素
    random_num = nums[random_index]
    return random_num

静态数组的增：

情况一：在数组的尾部追加（append）元素

# 大小为10的数组已经装了4个元素
arr = [0] * 10
for i in range(4):
    arr[i] = i

# 现在想在数组末尾追加一个元素4
arr[4] = 4

# 再在数组末尾追加一个元素5
arr[5] = 5

情况二，数组中间插入（insert）元素

# 大小为 10 的数组已经装了 4 个元素
arr = [0] * 10
for i in range(4):
    arr[i] = i

# 在索引 2 的位置插入元素 666
# 需要把索引 2 以及之后的元素都往后移动一位
# 注意要倒着遍历数组中已有元素避免覆盖
for i in range(4, 2, -1):
    arr[i] = arr[i - 1]

# 现在第 3 个位置空出来了，可以插入新元素
arr[2] = 666

# 编写一个在数组中插入元素的方法
def insert_element(nums:list[int],num:int,index:int):
    # 首先向数组中插入元素，会导致在插入下标后的元素都向后移
    # 因此需要从后向前遍历元素，是元素后移一位
    for i in range(len(nums)-1 , index ,-1):
        nums[i] = nums[i-1]
    # 把所有的元素都向后移动完后，此时想要插入元素的index位置就空了出来
    # 进行赋值
    nums[index]  = num

情况三，数组空间已满

连续内存必须一次性分配，分配完了之后就不能随意增减了。

此时要进行扩容操作：重新申请一块更大的内存空间，把原来的数据复制过去，再插入新的元素，这就是数组的「扩容」操作。

# 大小为10的数组已经装满了
arr = [i for i in range(10)]

# 现在想在数组的末尾追加一个新的元素10
# 需要先扩容数组
newArr = [0] * 20

# 把原来的10个元素复制过去
for i in range(10):
    newAarr[i] = arr[i]

# 在新的大数组中追加新的元素
newArr[10] = 10

# 扩容数组
def extend(nums:list[int],large:int) -> int:
    # 先初始化一个长度为扩充后的数组
    res = [0] * (len(nums) + large)
    for i in range(len(nums)):
        # 将原数组进行复制
        res[i] = nums[i]
    # 返回新数组
    return res

静态数组的删:

情况一，删除末尾元素

直接把末尾元素标记为一个特殊值(-1)代表已删除就行了

# 大小为10的数组已经装了5个元素
arr = [0] * 10
for i in range(5):
    arr[i] = i

# 删除末尾元素，用-1来代表元素已经删除
arr[4] = -1

情况二，删除中间元素

# 编写一个删除数组中索引i处元素的方法
def remove(nums:list[int],index:int):
    # 删除某处的元素其实就是让后面的元素覆盖前面的元素
    # 经过覆盖后，索引i处后面的元素相当于都往前移动了1格
    for i in range(index, len(nums)-1):
        nums[i] = nums[i+1]

# 大小为10的数组已经装了5个元素
arr = [0] * 10
for i in range(5):
    arr[i] = i


# 删除arr[1]
# 需要把arr[1]之后的元素都往前移动一位
# 注意要正着遍历数组中已有元素避免覆盖
for i in range(1,4):
    arr[i] = arr[i+1]

# 最后一个元素标记为-1，代表已删除
arr[4] = -1

数组插入与删除的特点 

时间复杂度高：数组的插入和删除的平均时间复杂度均为 O(n) ，其中 n 为数组长度。

丢失元素：由于数组的长度不可变，因此在插入元素后，超出数组长度范围的元素会丢失。

内存浪费：我们可以初始化一个比较长的数组，只用前面一部分，这样在插入数据时，丢失的末尾元素都是“无意义”的，但这样做会造成部分内存空间浪费。

查找元素 

在数组中查找指定元素需要遍历数组，每轮遍历都会进行判断，查看元素值是否匹配，若匹配则输出对应索引。

因为数组是线性数据结构，所以上述查找操作被称为“线性查找”。

# 查找元素
def find(nums:list[int],target:int) -> int:
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1

动态数组 

「动态数组」是编程语言为了方便我们使用，在静态数组的基础上帮我们添加了一些常用的 API，比如 push, insert, remove 等等方法，这些 API 可以让我们更方便地操作数组元素，不用自己去写代码实现这些操作。

动态数组底层还是静态数组，只是自动帮我们进行数组空间的扩缩容，并把增删查改操作进行了封装，让我们使用起来更方便而已。

# 创建动态数组
# 不用显式指定数组大小，它会根据实际存储的元素数量自动扩缩容量
arr = []

for i in range(10):
    # 在末尾追加元素 时间复杂度为O(1)
    arr.append(i)

# 在中间插入元素 时间复杂度为O(N)
# 在索引2的位置插入元素666
arr.insert(2, 666)

# 在头部插入元素 时间复杂度为O(1)
arr.insert(0, -1)

# 删除末尾元素 时间复杂度O(1)
arr.pop()

# 删除中间元素 时间复杂度O(N)
# 删除索引为2的元素
arr.pop(2)

# 根据索引查询元素 时间复杂度O(1)
a = arr[0]

# 根据索引修改元素，时间复杂度 O(1)
arr[0] = 100

# 根据元素值查找索引，时间复杂度 O(N)
index = arr.index(666)

 动态数组代码实现

class MyArrayList:
    # 默认初始容量
    INIT_CAP = 1

    def __init__(self, init_capacity=None):
        self.data = [None] * (init_capacity if init_capacity is not None else self.__class__.INIT_CAP)
        self.size = 0
    
    # 增
    def add_last(self, e):
        cap = len(self.data)
        # 看 data 数组容量够不够
        if self.size == cap:
            self._resize(2 * cap)
        # 在尾部插入元素
        self.data[self.size] = e
        self.size += 1

    def add(self, index, e):
        # 检查索引越界
        self._check_position_index(index)

        cap = len(self.data)
        # 看 data 数组容量够不够
        if self.size == cap:
            self._resize(2 * cap)

        # 搬移数据 data[index..] -> data[index+1..]
        # 给新元素腾出位置
        for i in range(self.size-1, index-1, -1):
            self.data[i+1] = self.data[i]
        
        # 插入新元素
        self.data[index] = e

        self.size += 1

    def add_first(self, e):
        self.add(0, e)

    # 删
    def remove_last(self):
        if self.size == 0:
            raise Exception("NoSuchElementException")
        cap = len(self.data)
        # 可以缩容，节约空间
        if self.size == cap // 4:
            self._resize(cap // 2)

        deleted_val = self.data[self.size - 1]
        # 删除最后一个元素
        self.data[self.size - 1] = None
        self.size -= 1

        return deleted_val

    def remove(self, index):
        # 检查索引越界
        self._check_element_index(index)

        cap = len(self.data)
        # 可以缩容，节约空间
        if self.size == cap // 4:
            self._resize(cap // 2)

        deleted_val = self.data[index]

        # 搬移数据 data[index+1..] -> data[index..]
        for i in range(index + 1, self.size):
            self.data[i - 1] = self.data[i]

        self.data[self.size - 1] = None
        self.size -= 1

        return deleted_val

    def remove_first(self):
        return self.remove(0)

    # 查
    def get(self, index):
        # 检查索引越界
        self._check_element_index(index)

        return self.data[index]

    # 改
    def set(self, index, element):
        # 检查索引越界
        self._check_element_index(index)
        # 修改数据
        old_val = self.data[index]
        self.data[index] = element
        return old_val

    # 工具方法
    def get_size(self):
        return self.size

    def is_empty(self):
        return self.size == 0

    # 将 data 的容量改为 newCap
    def _resize(self, new_cap):
        temp = [None] * new_cap
        for i in range(self.size):
            temp[i] = self.data[i]
        self.data = temp

    def _is_element_index(self, index):
        return 0 <= index < self.size

    def _is_position_index(self, index):
        return 0 <= index <= self.size

    def _check_element_index(self, index):
        if not self._is_element_index(index):
            raise IndexError(f"Index: {index}, Size: {self.size}")

    def _check_position_index(self, index):
        if not self._is_position_index(index):
            raise IndexError(f"Index: {index}, Size: {self.size}")

    def display(self):
        print(f"size = {self.size}, cap = {len(self.data)}")
        print(self.data)


# Usage example
if __name__ == "__main__":
    arr = MyArrayList(init_capacity=3)

    # 添加 5 个元素
    for i in range(1, 6):
        arr.add_last(i)

    arr.remove(3)
    arr.add(1, 9)
    arr.add_first(100)
    val = arr.remove_last()

    # 100 1 9 2 3
    for i in range(arr.get_size()):
        print(arr.get(i))

数组的优点和局限性

优点

空间效率高：数组为数据分配了连续的内存块，无须额外的结构开销。

支持随机访问：数组允许在 O(1) 时间内访问任何元素。

缓存局部性：当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓存来提升后续操作的执行速度。

局限性

插入与删除效率低：当数组中元素较多时，插入与删除操作需要移动大量的元素。

长度不可变：数组在初始化后长度就固定了，扩容数组需要将所有数据复制到新数组，开销很大。

空间浪费：如果数组分配的大小超过实际所需，那么多余的空间就被浪费了。

数组的应用 

随机访问：如果我们想随机抽取一些样本，那么可以用数组存储，并生成一个随机序列，根据索引实现随机抽样。

排序和搜索：数组是排序和搜索算法最常用的数据结构。快速排序、归并排序、二分查找等都主要在数组上进行。

查找表：当需要快速查找一个元素或其对应关系时，可以使用数组作为查找表。假如我们想实现字符到 ASCII 码的映射，则可以将字符的 ASCII 码值作为索引，对应的元素存放在数组中的对应位置。

机器学习：神经网络中大量使用了向量、矩阵、张量之间的线性代数运算，这些数据都是以数组的形式构建的。数组是神经网络编程中最常使用的数据结构。

数据结构实现：数组可以用于实现栈、队列、哈希表、堆、图等数据结构。例如，图的邻接矩阵表示实际上是一个二维数组。

作者：Xin Z