← 返回数据结构与算法目录
← 返回学习笔记首页
专题： 数据结构与算法系统学习
关键词： 数据结构, 算法, 数组, 动态数组, 列表, list, 时间复杂度, 扩容, 多维数组
一、数组基础概念
数组（Array）是计算机科学中最基础、最广泛使用的数据结构之一。它是一组连续内存空间中存储的相同类型元素的集合。数组的核心价值在于：通过下标（索引）可以在 O(1) 时间内访问任意元素，这一特性使其成为几乎所有高级数据结构的构建基石。
从内存布局来看，数组将所有元素按顺序存放在一块连续的内存区域中。假设数组的起始地址为 base，每个元素占用 size 字节，那么第 i 个元素的地址就是 base + i × size。这种线性寻址方式让数组具备了随机访问的能力——无论数组有多大，访问任意一个元素的时间都是恒定的。
数组的三大特性：
1. 连续内存：元素在内存中连续存放，这是数组最根本的特征。
2. 相同类型：传统数组中所有元素类型相同（Python 列表略有不同，下文详述）。
3. 随机访问：通过索引可在 O(1) 时间内访问任意元素。
1.1 数组的抽象数据类型
从抽象数据类型（ADT）的角度看，数组主要支持以下操作：读取指定位置的元素（get）、修改指定位置的元素（set）、获取数组长度（length）、遍历所有元素（traverse）。这些操作的时间复杂度直接影响着基于数组构建的各种算法的效率。
from abc import ABC, abstractmethod
class ArrayADT (ABC):
"""数组的抽象数据类型定义"""
@abstractmethod
def get (self , index: int ):
"""获取指定索引的元素"""
pass
@abstractmethod
def set (self , index: int , value):
"""设置指定索引的元素"""
pass
@abstractmethod
def length (self ) -> int :
"""返回数组长度"""
pass
@abstractmethod
def traverse (self ):
"""遍历所有元素"""
pass
二、静态数组与动态数组
根据容量是否可变，数组分为静态数组（Static Array）和动态数组（Dynamic Array）两大类。理解两者的区别是掌握数组使用的关键。
2.1 静态数组
静态数组在创建时其大小就已固定，在整个生命周期中不能改变。C 语言中的原生数组就是静态数组的典型代表。静态数组的优点是性能极高——没有扩容的开销，内存分配一次完成；缺点是灵活性差，必须预先知道数据规模。
/* C 语言静态数组示例 */
int arr[5 ] = {10 , 20 , 30 , 40 , 50 };
// 访问第3个元素
int val = arr[2 ]; // O(1) 时间复杂度
// 数组大小固定为5，无法再添加第6个元素
在静态数组中，如果我们尝试访问超出边界的索引，在 C 语言中会导致"缓冲区溢出"（buffer overflow）——这是许多安全漏洞的根源。Java 和 Python 等语言会进行边界检查，抛出 IndexOutOfBoundsException 或 IndexError。
2.2 动态数组
动态数组可以在运行时按需增长或收缩。Python 的 list、Java 的 ArrayList、C++ 的 vector 都是动态数组的实现。动态数组的核心思想是"预分配 + 按需扩容"：当元素数量达到当前容量上限时，申请一块更大的内存空间，将原有元素复制过去，然后释放旧空间。
# Python 动态数组（list）示例
arr = [10 , 20 , 30 ] # 创建一个包含3个元素的列表
arr.append(40 ) # 自动扩容，添加第4个元素
arr.append(50 ) # 继续添加
print (arr) # 输出: [10, 20, 30, 40, 50]
print (len (arr)) # 输出: 5
核心区别： 静态数组大小固定，不能动态变化；动态数组可以自动扩容，但扩容需要 O(n) 的时间（然而均摊后为 O(1)）。在大多数实际应用中，动态数组是更实用的选择。
三、Python 列表的底层实现
Python 的 list 是动态数组的经典实现，但其底层机制与 C 语言的传统数组有显著区别。理解 Python list 的实现原理，有助于编写更高效的 Python 代码。
3.1 PyListObject 结构
Python 的 list 在 CPython 中由 PyListObject 结构体表示。与 C 数组直接存储元素值不同，Python list 存储的是指向 PyObject 的指针数组。这意味着：第一，list 中的元素可以是任意类型（因为它们都是 PyObject 指针）；第二，每个指针占用固定大小（64 位系统中为 8 字节），这使得寻址计算保持简单。
# Python list 可以存储不同类型的元素
mixed = [42 , "hello" , 3.14 , True , [1 , 2 ]]
for item in mixed:
print (f" { type (item).__name__ } : { item} " )
# 输出:
# int: 42
# str: hello
# float: 3.14
# bool: True
# list: [1, 2]
3.2 内存布局示意
当我们创建 list arr = [10, 20, 30] 时，CPython 内部会分配一个能容纳 4 个指针（实际容量 capacity = 4）的数组，但只使用前 3 个（长度 size = 3）。第 4 个位置预留，为下一次 append 操作做准备。如果继续 append 直到 size 达到 capacity，就会触发扩容。
理解关键： Python list 的"长度"（len() 返回值）和"容量"（内部 allocated 字段）是两个不同的概念。长度是实际存储的元素个数，容量是底层数组能容纳的最大元素个数。容量总是大于等于长度。
# 演示 Python list 的底层容量变化
import sys
arr = []
for i in range (10 ):
print (f"长度= { len (arr)} , 占用字节= { sys.getsizeof(arr)} " )
arr.append(i)
# 注意 getsizeof 返回的是整个 list 对象占用的内存
# 当它跳变时，说明触发了扩容
四、数组基本操作与时间复杂度分析
时间复杂度是评价数据结构操作效率的核心指标。下表总结了动态数组各操作的时间复杂度，并以 Python 代码演示每种操作的具体实现。
操作
平均时间复杂度
最坏时间复杂度
说明
访问 (get/set)
O(1)
O(1)
通过索引直接计算地址
末尾追加 (append)
O(1)
O(n)*
*扩容时 O(n)，均摊后 O(1)
末尾弹出 (pop)
O(1)
O(1)
只需减少 size 计数
任意位置插入 (insert)
O(n)
O(n)
需要移动后续元素
任意位置删除 (del)
O(n)
O(n)
需要移动后续元素
搜索 (index/in)
O(n)
O(n)
线性搜索
排序 (sort)
O(n log n)
O(n log n)
Timsort 算法
4.1 访问操作 O(1)
数组的随机访问是其最大的优势。通过索引访问元素只需要一次内存读取操作，与数组大小无关。这就是为什么在需要频繁按位置读取数据的场景中，数组总是首选。
# O(1) 随机访问演示
arr = [100 , 200 , 300 , 400 , 500 ]
# 不论数组多大，访问指定索引只需一步
first = arr[0 ] # 100
third = arr[2 ] # 300
last = arr[-1 ] # 500（Python 支持负索引）
# 修改也是 O(1)
arr[1 ] = 250 # 将第二个元素改为250
print (arr) # [100, 250, 300, 400, 500]
4.2 插入与删除操作 O(n)
在数组中间位置插入或删除元素时，需要移动后续所有元素来维持内存的连续性。这是数组最主要的性能短板。
# O(n) 插入操作
arr = [1 , 2 , 3 , 4 , 5 ]
# 在索引2处插入 99，需要移动 3,4,5 三个元素
arr.insert(2 , 99 )
print (arr) # [1, 2, 99, 3, 4, 5]
# 删除索引3处的元素，也需要移动后续元素
deleted = arr.pop(3 )
print (arr) # [1, 2, 99, 4, 5]
# 使用 del 关键字也可以删除
del arr[0 ]
print (arr) # [2, 99, 4, 5]
优化建议： 如果需要在数组中间频繁插入或删除元素，考虑使用 collections.deque（双端队列）或链表替代。但如果大多数操作是访问和末尾追加，数组仍然是最优选择。
4.3 搜索操作 O(n)
在无序数组中查找特定元素，必须逐个比较，因此时间复杂度为 O(n)。如果数组是有序的，可以使用二分查找将复杂度降低到 O(log n)。
# 线性搜索 O(n)
arr = [34 , 78 , 12 , 90 , 45 , 67 ]
def linear_search (data, target):
for i, val in enumerate (data):
if val == target:
return i # 找到，返回索引
return -1 # 未找到
print (linear_search(arr, 90 )) # 输出: 3
print (linear_search(arr, 99 )) # 输出: -1
# Python 内置的 in 操作符也是 O(n)
print (90 in arr) # True
print (arr.index(90 )) # 3
五、动态数组的扩容策略
动态数组的核心机制是"按需扩容"。当元素数量达到当前容量上限时，数组会申请一个更大的内存空间，将原数据复制过去。扩容策略直接决定了动态数组的性能表现。
5.1 扩容因子
不同的编程语言采用不同的扩容因子（growth factor）。Python 的扩容策略大致是：当需要扩容时，新容量 ≈ 旧容量 × 1.125 + 6（针对小列表有优化）。C++ 的 vector 通常使用 2 倍扩容，Java 的 ArrayList 使用 1.5 倍扩容。
# 模拟 Python 动态数组的扩容过程
class DynamicArray :
def __init__ (self , capacity=1 ):
self ._data = [None ] * capacity
self ._size = 0
self ._capacity = capacity
def append (self , value):
if self ._size == self ._capacity:
self ._resize(self ._capacity * 2 ) # 2倍扩容
self ._data[self ._size] = value
self ._size += 1
def _resize (self , new_capacity):
new_data = [None ] * new_capacity
for i in range (self ._size):
new_data[i] = self ._data[i] # O(n) 复制
self ._data = new_data
self ._capacity = new_capacity
print (f"扩容至 {new_capacity} " )
def __len__ (self ):
return self ._size
def __getitem__ (self , index):
if index < 0 or index >= self ._size:
raise IndexError ("索引越界" )
return self ._data[index]
def __repr__ (self ):
return "[" + ", " .join(str (self ._data[i])
for i in range (self ._size)) + "]"
# 测试动态数组
da = DynamicArray()
for i in range (10 ):
da.append(i)
print (f"追加 {i} : {da} , 长度= { len (da)} " )
5.2 均摊时间复杂度分析
虽然单次扩容操作需要 O(n) 时间，但如果我们把多次 append 操作放在一起看，扩容的成本被分摊到了每一次追加中。这就是"均摊分析"（Amortized Analysis）的思想。
假设数组初始容量为 1，每次扩容翻倍。从空数组开始，连续追加 n 个元素，扩容发生的次数为大约 log₂(n) 次，每次复制的元素数量分别为 1, 2, 4, 8, ..., n/2。复制总次数为 1 + 2 + 4 + ... + n/2 = n - 1。因此，n 次 append 的总时间复杂度为 O(n)，均摊到每次 append 就是 O(1)。
均摊分析结论： 虽然动态数组的单次 append 操作在最坏情况下是 O(n)（触发扩容时），但连续 n 次 append 的均摊时间复杂度为 O(1)。这就是为什么在实际应用中，动态数组的 append 操作被认为是"常数时间"的。
5.3 不同的扩容策略对比
扩容策略
平摊复杂度
空间浪费
典型实现
固定增量（+k）
O(n)
较少
某些嵌入式系统
翻倍扩容（×2）
O(1)
最多浪费一半
C++ vector
1.5 倍扩容
O(1)
最多浪费 1/3
Java ArrayList
混合策略
O(1)
优化小列表
Python list
有趣的事实： Python 的 list 对小列表（长度 < 9 时）采用了特殊的优化策略。这是因为实际应用中大多数列表都很小，优化小列表的扩容可以显著提升整体性能。具体来说，Python 会按照 0, 4, 8, 16, 24, 32, 40, ... 的序列扩容，避免了小列表时的过度分配。
六、多维数组与矩阵运算
数组可以扩展为多维形式，最常见的是一维数组（向量）和二维数组（矩阵）。多维数组在图像处理、机器学习、科学计算等领域有广泛应用。
6.1 二维数组的实现
Python 中可以使用嵌套列表来实现二维数组。但需要注意的是，Python 标准库的 list 并非为数值计算优化，大规模矩阵运算应使用 NumPy。
# Python 原生二维列表
matrix = [
[1 , 2 , 3 ],
[4 , 5 , 6 ],
[7 , 8 , 9 ]
]
# 访问第2行第3列的元素（行列均从0开始）
print (matrix[1 ][2 ]) # 输出: 6
# 矩阵转置
transposed = [[matrix[j][i] for j in range (len (matrix))]
for i in range (len (matrix[0 ]))]
print (transposed)
# 输出: [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
# 矩阵乘法（2x3 × 3x2）
A = [[1 , 2 , 3 ],
[4 , 5 , 6 ]]
B = [[7 , 8 ],
[9 , 10 ],
[11 , 12 ]]
result = [[0 ] * len (B[0 ]) for _ in range (len (A))]
for i in range (len (A)):
for j in range (len (B[0 ])):
for k in range (len (B)):
result[i][j] += A[i][k] * B[k][j]
print (result)
# 输出: [[58, 64], [139, 154]]
6.2 NumPy 数组的威力
Python 原生的嵌套列表在数值计算中性能不佳。NumPy 使用 C 语言实现的连续内存块存储数据，配合向量化操作，性能可以提升数十倍甚至上百倍。
import numpy as np
# 创建 NumPy 数组
arr = np.array([1 , 2 , 3 , 4 , 5 ])
print (arr) # [1 2 3 4 5]
print (arr.shape) # (5,) —— 一维数组，5个元素
# 二维数组（矩阵）
matrix = np.array([[1 , 2 ], [3 , 4 ], [5 , 6 ]])
print (matrix.shape) # (3, 2) —— 3行2列
# 向量化运算（无 Python 循环）
a = np.array([1 , 2 , 3 ])
b = np.array([4 , 5 , 6 ])
print (a + b) # [5 7 9] 逐元素加法
print (a * b) # [4 10 18] 逐元素乘法
print (a.dot(b)) # 32 点积：1*4 + 2*5 + 3*6
# 广播机制
print (a + 10 ) # [11 12 13] 标量广播到每个元素
# 矩阵乘法
A = np.array([[1 , 2 ], [3 , 4 ]])
B = np.array([[5 , 6 ], [7 , 8 ]])
print (A @ B) # Python 3.5+ 矩阵乘法运算符
# [[19 22]
# [43 50]]
七、数组与链表对比
数组和链表是两种最基本的数据结构，它们在内存布局、操作性能、适用场景上有着本质的区别。透彻理解两者的差异，是成为一名合格程序员的必修课。
对比维度
数组
链表
内存布局
连续内存
分散内存（通过指针连接）
随机访问
O(1) —— 优势
O(n) —— 需要遍历
头部插入
O(n) —— 需要移动所有元素
O(1) —— 修改头指针
尾部插入
O(1) 均摊
O(1)（有尾指针）或 O(n)
删除操作
O(n) —— 移动元素
O(1)（已知前驱节点）
空间开销
较低，仅有数据本身
较高，每个节点多一个指针
缓存友好性
高（空间局部性好）
低（跳跃式访问）
内存碎片
不产生碎片
可能产生大量碎片
选择原则：
• 需要频繁随机访问 → 选数组。例如：游戏中的角色列表，按索引快速查找。
• 需要频繁在中间插入/删除 → 选链表。例如：文本编辑器的撤销栈（Undo Stack）。
• 数据量不大且操作简单 → 选数组。现代 CPU 的缓存机制使数组在大多数场景下都更快。
• 数据量巨大且插入删除频繁 → 选链表。但要考虑额外的内存开销。
八、数组的经典应用场景
8.1 作为哈希表的底层结构
哈希表（Hash Table / Dictionary）的底层通常使用数组实现。通过哈希函数将键映射到数组的索引，实现 O(1) 的查找、插入和删除。Python 的 dict 就是基于数组的哈希表实现。
8.2 实现栈和队列
栈（后进先出）可以用数组轻松实现。队列（先进先出）也可以用数组实现，但需要考虑头部删除的效率问题。Python 的 collections.deque 就是基于数组的双端队列优化实现。
# 用 Python list 实现栈
stack = []
stack.append("A" ) # 入栈
stack.append("B" )
stack.append("C" )
print (stack.pop()) # 出栈: C
print (stack.pop()) # B
print (stack) # ['A']
# 用 collections.deque 实现高效队列
from collections import deque
queue = deque()
queue.append("任务1" ) # 尾部入队
queue.append("任务2" )
queue.append("任务3" )
print (queue.popleft()) # 头部出队: 任务1（O(1)）
print (queue.popleft()) # 任务2
8.3 动态规划中的 DP 表
动态规划问题通常使用多维数组（DP 表）来存储中间状态。经典的例子包括斐波那契数列、背包问题、最长公共子序列等。
# 用数组实现动态规划：斐波那契数列
def fibonacci (n: int ) -> int :
"""动态规划求斐波那契数列第 n 项"""
if n <= 1 :
return n
dp = [0 ] * (n + 1 )
dp[0 ], dp[1 ] = 0 , 1
for i in range (2 , n + 1 ):
dp[i] = dp[i - 1 ] + dp[i - 2 ]
return dp[n]
print (fibonacci(10 )) # 输出: 55
print (fibonacci(50 )) # 输出: 12586269025
九、Python 数组操作进阶技巧
9.1 列表推导式（List Comprehension）
列表推导式是 Python 中最优雅的特性之一，它可以用简洁的语法创建新的列表，通常比等价的 for 循环更快。
# 列表推导式 vs 传统 for 循环
# 传统方式
squares = []
for i in range (10 ):
squares.append(i ** 2 )
print (squares)
# 列表推导式（更简洁、更高效）
squares = [i ** 2 for i in range (10 )]
print (squares)
# 带条件的列表推导式
evens = [x for x in range (20 ) if x % 2 == 0 ]
print (evens) # [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
# 嵌套列表推导式
matrix = [[i * j for j in range (1 , 4 )] for i in range (1 , 4 )]
print (matrix) # [[1, 2, 3], [2, 4, 6], [3, 6, 9]]
9.2 切片操作
切片（Slicing）是 Python 数组操作中的利器，可以灵活地获取子数组、复制、反转等。切片返回的是原数组的浅拷贝（shallow copy）。
# Python 切片操作详解
arr = [0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ]
# 基本切片: arr[start:stop:step]
print (arr[2 :6 ]) # [2, 3, 4, 5]
print (arr[:4 ]) # [0, 1, 2, 3] 默认从开头开始
print (arr[6 :]) # [6, 7, 8, 9] 默认到结尾结束
print (arr[::2 ]) # [0, 2, 4, 6, 8] 步长为 2
# 反转数组
print (arr[::-1 ]) # [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
# 复制整个数组
copy_arr = arr[:]
copy_arr[0 ] = 999
print (arr) # [0, 1, 2, ...] 原数组不变
# 切片赋值
arr[3 :6 ] = [33 , 44 , 55 ]
print (arr) # [0, 1, 2, 33, 44, 55, 6, 7, 8, 9]
9.3 常见陷阱与注意事项
⚠️ 常见陷阱：
1. 不要用 [obj] * n 创建包含可变对象的列表
row = [[]] * 5 产生的是包含 5 个指向同一个空列表的引用的列表，修改一个会影响所有。
正确做法： row = [[] for _ in range(5)]
2. 循环中删除元素要谨慎
在遍历列表时删除元素会导致索引错位，建议使用列表推导式或创建新列表。
3. 大量数据预分配
如果预先知道数据量，使用 [None] * size 预分配内存，避免多次扩容。
# 陷阱1: 可变对象的引用复制
# 错误方式
bad = [[0 ] * 3 ] * 3
bad[0 ][0 ] = 1
print (bad) # [[1, 0, 0], [1, 0, 0], [1, 0, 0]] 全部被修改
# 正确方式
good = [[0 ] * 3 for _ in range (3 )]
good[0 ][0 ] = 1
print (good) # [[1, 0, 0], [0, 0, 0], [0, 0, 0]] 符合预期
# 陷阱2: 遍历时删除
# 错误方式：删除所有偶数
nums = [1 , 2 , 3 , 4 , 5 , 6 ]
for i, num in enumerate (nums):
if num % 2 == 0 :
del nums[i] # 索引错位！
print (nums) # [1, 3, 5] 看起来对了，但这是巧合
# 正确方式：列表推导式
nums = [1 , 2 , 3 , 4 , 5 , 6 ]
nums = [x for x in nums if x % 2 != 0 ]
print (nums) # [1, 3, 5]
# 陷阱3: 默认参数中不要用可变对象
def add_item (item, lst=[]):
lst.append(item)
return lst
print (add_item(1 )) # [1]
print (add_item(2 )) # [1, 2] —— 不是 [2]！
十、核心要点总结
数组与动态数组 —— 核心要点总结：
1. 数组的本质 ：连续内存空间中相同类型元素的集合，通过下标可在 O(1) 时间内访问任意元素。
2. 静态 vs 动态 ：静态数组大小固定；动态数组可自动扩容，均摊后 append 为 O(1)。
3. Python list ：是动态数组的经典实现，存储的是 PyObject 指针而非实际值，因此可包含任意类型。
4. 时间复杂度 ：访问 O(1)、末尾追加 O(1) 均摊、中间插入/删除 O(n)、搜索 O(n)。
5. 扩容策略 ：Python 采用混合策略，小列表优化 + 按需扩容，不同语言采用不同扩容因子。
6. vs 链表 ：数组优势在随机访问和缓存友好；链表的优势在频繁的中间插入/删除。
7. 多维数组 ：NumPy 是 Python 中进行大型矩阵运算的标准工具，性能远优于原生嵌套列表。
8. 最佳实践 ：合理使用列表推导式、切片操作，警惕可变对象引用陷阱。
十一、进一步思考与实践
延伸问题：
1. 为什么 Python 3 的 range() 返回的不是列表而是一个可迭代对象？这与内存优化有什么关系？
2. 如果动态数组的扩容因子是 1.25（即每次扩容 25%），其均摊复杂度还是 O(1) 吗？为什么？
3. Python 的 array.array 模块和内置 list 有什么区别？在什么场景下应该使用 array.array？
4. 如何用数组实现一个循环队列？循环队列相比普通队列的优点是什么？
# 实践练习：自定义动态数组类（完整版）
class ArrayList :
"""一个完整的动态数组实现"""
def __init__ (self , items=None ):
self ._capacity = 4
self ._size = 0
self ._data = [None ] * self ._capacity
if items:
for item in items:
self .append(item)
def append (self , value):
if self ._size == self ._capacity:
self ._resize(int (self ._capacity * 1.5 ) + 1 )
self ._data[self ._size] = value
self ._size += 1
def pop (self , index=-1 ):
if self ._size == 0 :
raise IndexError ("pop from empty list" )
if index < 0 :
index += self ._size
if index < 0 or index >= self ._size:
raise IndexError ("index out of range" )
value = self ._data[index]
for i in range (index, self ._size - 1 ):
self ._data[i] = self ._data[i + 1 ]
self ._size -= 1
return value
def insert (self , index, value):
if index < 0 :
index += self ._size
if index < 0 or index > self ._size:
raise IndexError ("index out of range" )
if self ._size == self ._capacity:
self ._resize(int (self ._capacity * 1.5 ) + 1 )
for i in range (self ._size, index, -1 ):
self ._data[i] = self ._data[i - 1 ]
self ._data[index] = value
self ._size += 1
def _resize (self , new_capacity):
new_data = [None ] * new_capacity
for i in range (self ._size):
new_data[i] = self ._data[i]
self ._data = new_data
self ._capacity = new_capacity
def __len__ (self ):
return self ._size
def __getitem__ (self , index):
if index < 0 :
index += self ._size
if index < 0 or index >= self ._size:
raise IndexError ("index out of range" )
return self ._data[index]
def __repr__ (self ):
items = [repr (self ._data[i]) for i in range (self ._size)]
return "ArrayList([" + ", " .join(items) + "])"
# 测试
al = ArrayList([1 , 2 , 3 ])
al.append(4 )
al.insert(1 , 99 )
print (al) # ArrayList([1, 99, 2, 3, 4])
print (al.pop()) # 4
print (al[0 ]) # 1
print (len (al)) # 4