可变数组的底层实现是基于静态数组的，通过动态申请内存空间、重新分配内存空间等方式来实现可变长度。

当可变数组的扩容通常是在数组元素个数到达容量上限时进行。

具体实现方式： 重新申请一块更大的内存空间，将原数组的元素拷贝到新的内存空间中，并释放原内存空间。

Python list扩容的主要过程和实现方式：

  1. 初始化：当创建一个空列表时，Python会分配一个最小的初始容量（例如0或者某个小的默认值）。

  2. 添加元素：当列表需要添加元素且当前容量不足时，Python会进行扩容。

  3. 扩容策略：Python使用一种几何级数的扩容策略。通常是将当前容量扩大为原来的1.5倍或2倍。这种策略能够在均摊情况下将每次添加操作的时间复杂度保持在O(1)。

  4. 内存复制：扩容时，Python会分配一块新的、更大的内存空间，并将旧数组中的元素复制到新的内存空间中。

import sys

# 创建一个空列表
my_list = []

# 打印列表的容量和长度
print(f"初始容量: {sys.getsizeof(my_list)}, 长度: {len(my_list)}")

# 向列表中添加元素，并打印扩容后的容量和长度
for i in range(20):
    my_list.append(i)
    print(f"添加元素 {i} 后，容量: {sys.getsizeof(my_list)}, 长度: {len(my_list)}")

Python中常见的可变数组

  • list（列表）：

    • 最常用的可变数组类型。

    • 支持各种元素类型，可以动态扩容。

    • 适合大多数通用用途的场景。

  • deque（双端队列）：

    • 位于collections模块中。

    • 支持在两端快速添加和删除元素，适合需要频繁在两端操作的场景。

    • 内部实现为双向链表，具有O(1)时间复杂度的append和pop操作。

from collections import deque

dq = deque([1, 2, 3])
dq.append(4)        # 在右端添加元素
dq.appendleft(0)    # 在左端添加元素
dq.pop()            # 删除右端元素
dq.popleft()        # 删除左端元素

  • array（数组）：

    • 位于array模块中。

    • 只能存储同类型的元素，比list更加节省内存。

    • 提供基本的数组操作，适合需要固定类型、节省内存的场景。

import array

arr = array.array('i', [1, 2, 3])  # 创建一个整数类型的数组
arr.append(4)
arr.extend([5, 6])

  • bytearray（字节数组）：

    • 用于处理二进制数据。

    • 支持类似列表的操作，可以动态扩展。

    • 适合处理字节数据和二进制文件的场景。

ba = bytearray(b'hello')
ba.append(33)  # 添加一个字节
ba.extend(b' world')

  • numpy.ndarray（NumPy数组）：

    • 位于第三方库NumPy中。

    • 支持多维数组和大量的数值计算操作。

    • 适合需要高性能数值计算和矩阵运算的场景。

import numpy as np

np_arr = np.array([1, 2, 3, 4])
np_arr = np.append(np_arr, [5, 6])

  • string（字符串）：

    • 虽然字符串本身是不可变的，但通过将其转换为list或bytearray可以实现可变操作。

s = "hello"
s_list = list(s)  # 转换为列表以进行可变操作
s_list.append('!')
result = ''.join(s_list)  # 转换回字符串