第3章 数组与列表
3.1 引言
数组（Array）是计算机科学中最基础的线性数据结构，其核心思想是通过连续内存空间存储相同类型元素，实现对数据的高效组织与访问。从早期的机器语言到现代编程语言，数组始终是数据处理的基石——操作系统的内存管理、数据库的索引结构、图像的像素存储等底层实现，均依赖数组的高效随机访问特性。
Python中的列表（List）虽常被视为“数组的扩展”，但本质上是动态数组（Dynamic Array）的实现：它突破了传统数组“固定大小”的限制，通过自动扩容机制支持动态元素增减，同时兼容不同类型元素的存储。理解数组的底层原理与Python列表的实现逻辑，是掌握数据结构设计思想的第一步，也是优化代码性能的关键。本章将从数组的基本概念出发，深入剖析Python列表的动态扩容机制，手动实现动态数组，并通过稀疏矩阵案例展示其工程应用。
3.2 数组的基本概念
3.2.1 数组的定义与核心特性
定义3.1 数组：由相同数据类型的元素组成的有序集合，元素在内存中连续存储，通过索引（Index） 唯一标识元素位置。
数组的核心特性源于其连续内存存储方式，具体表现为：

顺序存储：元素在内存中按逻辑顺序连续排列，相邻元素的物理地址差值等于单个元素的大小（如int型元素占4字节，索引i与i+1的地址差为4字节）。

随机访问：通过索引可直接计算元素的内存地址，访问时间复杂度为O(1)。设数组首地址为base，元素大小为size，则索引i的元素地址为：
address(i)=base+i×size ext{address}(i) = ext{base} + i imes ext{size} address(i)=base+i×size

固定大小：传统数组（如C语言数组）在创建时需指定长度，且运行时不可修改。若需调整大小，需手动申请新内存并复制元素，时间复杂度为O(n)。

3.2.2 数组的内存存储模型
以一个包含5个int型元素的数组[10, 20, 30, 40, 50]为例（假设int型占4字节，首地址为0x1000），其内存布局如下：
索引i 元素值 内存地址计算 实际地址（示例）

0	10	0x1000 + 0×4	0x1000
1	20	0x1000 + 1×4	0x1004
2	30	0x1000 + 2×4	0x1008
3	40	0x1000 + 3×4	0x100C
4	50	0x1000 + 4×4	0x1010

这种连续存储模型使得数组能通过简单的地址计算实现随机访问，这是数组区别于链表等其他线性结构的核心优势。
3.2.3 数组的优缺点
优点：
访问高效：随机访问时间复杂度O(1)，是所有数据结构中最快的。
空间紧凑：无需额外存储指针或引用（如链表的节点指针），空间利用率接近100%。
缓存友好：连续内存存储符合计算机缓存机制（局部性原理），频繁访问相邻元素时缓存命中率高。
缺点：
大小固定：创建时需确定长度，扩容需O(n)时间（复制元素），灵活性差。
插入/删除低效：在中间或头部插入/删除元素时，需移动后续所有元素，时间复杂度O(n)。例如，在索引1插入元素需移动索引1及之后的所有元素（平均移动n/2个元素）。
3.2.4 不同语言中的数组
静态数组（如C/C++、Java）：需显式声明长度和元素类型，大小固定，不支持动态扩容。例如，int arr[5];（C语言）创建长度为5的int数组，越界访问会导致内存错误。
动态数组（如Python列表、Java ArrayList）：自动管理容量，支持动态扩容，元素类型可灵活（Python）或受限（Java需指定泛型）。
多维数组：逻辑上为“数组的数组”，物理存储可采用行优先（C语言）或列优先（Fortran）方式，本质仍是连续内存块。
3.3 Python列表的实现原理
Python列表（List）并非传统意义上的数组（因其支持不同类型元素），但底层基于动态数组实现，通过自动扩容机制突破固定大小限制，同时保留数组的随机访问特性。理解列表的内部实现，是编写高效Python代码的基础。
3.3.1 动态数组的核心概念
动态数组在静态数组基础上增加了容量（Capacity） 管理机制，核心属性包括：
大小（Size）：当前存储的元素数量（len(list)返回的值）。
容量（Capacity）：当前内存空间可容纳的最大元素数量（用户不可见，由解释器管理）。
元素区（Items）：指向连续内存空间的指针，存储元素的引用（Python中所有元素均为对象，列表存储的是对象引用而非值）。
核心思想：当size == capacity时，自动申请更大的内存空间，复制元素后释放旧空间，从而实现“动态大小”的效果。
3.3.2 动态扩容机制
Python列表的扩容策略是其性能优化的关键，具体步骤如下：

触发条件：调用append()添加元素后，若size == capacity，触发扩容。

新容量计算：Python采用1.5倍扩容策略（早期为2倍，后改为1.5倍以减少空间浪费）。设原容量为cap，新容量为：
1.new_cap=⌊cap×1.5⌋ ext{new_cap} = lfloor ext{cap} imes 1.5 floor new_cap=⌊cap×1.5⌋
例如，容量4→6→9→13→19...（1.5倍向下取整）。

内存申请与复制：

o申请可容纳new_cap个元素引用的连续内存；
o将原元素区的size个引用复制到新内存（耗时O(n)，但均摊到每次append操作后为O(1)）；
o更新元素区指针指向新内存，释放旧内存。
示例：初始容量为4的列表扩容过程
python

	lst = [] # size=0, capacity=4, items=[None, None, None, None] 
	lst.append(1) # size=1, capacity=4 
	lst.append(2) # size=2, capacity=4 
	lst.append(3) # size=3, capacity=4 
	lst.append(4) # size=4, capacity=4 → 触发扩容，new_cap=6 
	# 复制元素：items变为[1, 2, 3, 4, None, None]，size=4, capacity=6 
	lst.append(5) # size=5, capacity=6（无需扩容）

3.3.3 列表操作的时间复杂度分析
列表的核心操作性能取决于是否涉及元素移动或内存复制，具体时间复杂度如下：
操作 语法示例 时间复杂度 说明
索引访问 lst[i] O(1) 直接通过地址计算访问，与元素数量无关。
尾部添加 lst.append(x) O(1)均摊 无扩容时O(1)；扩容时O(n)，但均摊到n次操作后每次为O(1)。
指定位置插入 lst.insert(k, x) O(n) 需移动k及之后的所有元素（平均移动n/2个元素），时间与元素数量成正比。
尾部删除 lst.pop() O(1) 直接减少size，无需移动元素。
指定位置删除 lst.pop(k) O(n) 需移动k之后的所有元素（平均移动n/2个元素）。
成员检查 x in lst O(n) 线性扫描所有元素，最坏情况需遍历全部元素。
3.3.4 列表与静态数组的关键区别

3.4 动态数组的设计与实现
为深入理解动态数组的工作原理，本节手动实现一个简化版动态数组（DynamicArray），模拟Python列表的核心功能，包括初始化、添加、插入、删除及动态扩容/缩容。
3.4.1 核心功能设计
目标：实现支持以下操作的动态数组：
init(self, capacity=4)：初始化数组，指定初始容量（默认4）。
append(self, x)：尾部添加元素，自动扩容。
insert(self, k, x)：在索引k处插入元素，自动扩容。
pop(self, k=None)：删除索引k处元素（默认尾部），支持缩容。
getitem(self, k)：通过索引k访问元素（支持arr[k]语法）。
len(self)：返回元素数量（支持len(arr)语法）。
3.4.2 完整实现代码
python

	import ctypes # 用于调用C语言风格的内存分配函数（模拟底层内存操作） 
	
	class DynamicArray: 
	def __init__(self, capacity=4): 
	self.size = 0 # 当前元素数量 
	self.capacity = capacity # 当前容量（至少为1） 
	if self.capacity < 1: 
	self.capacity = 4 
	# 申请容量为capacity的连续内存，存储Python对象引用（ctypes.py_object对应对象指针） 
	self.items = (ctypes.py_object * self.capacity)() 
	
	def append(self, x): 
	"""尾部添加元素，自动扩容""" 
	if self.size == self.capacity: 
	self._resize(self.capacity * 2) # 简化为2倍扩容（实际Python为1.5倍） 
	self.items[self.size] = x 
	self.size += 1 
	
	def _resize(self, new_capacity): 
	"""扩容/缩容：申请新内存，复制元素，释放旧内存""" 
	if new_capacity < self.size: 
	raise ValueError("新容量小于当前元素数量") 
	# 1. 申请新内存 
	new_items = (ctypes.py_object * new_capacity)() 
	# 2. 复制元素（仅复制已存储的size个元素） 
	for i in range(self.size): 
	new_items[i] = self.items[i] 
	# 3. 更新指针与容量 
	self.items = new_items 
	self.capacity = new_capacity 
	
	def insert(self, k, x): 
	"""在索引k处插入元素，k范围：0 ≤ k ≤ size""" 
	if k < 0 or k > self.size: 
	raise IndexError("插入索引越界") 
	# 容量不足时扩容 
	if self.size == self.capacity: 
	self._resize(self.capacity * 2) 
	# 移动k及之后的元素（从后往前移，避免覆盖） 
	for i in range(self.size, k, -1): 
	self.items[i] = self.items[i-1] 
	self.items[k] = x 
	self.size += 1 
	
	def pop(self, k=None): 
	"""删除索引k处元素，返回被删除值，默认删除尾部（k=size-1）""" 
	if self.size == 0: 
	raise IndexError("无法删除空数组元素") 
	if k is None: 
	k = self.size - 1 # 默认删除尾部 
	if k < 0 or k >= self.size: 
	raise IndexError("删除索引越界") 
	# 记录被删除值 
	x = self.items[k] 
	# 移动k之后的元素（从前往后移） 
	for i in range(k, self.size - 1): 
	self.items[i] = self.items[i+1] 
	self.size -= 1 
	# 缩容：当size < capacity//4时，缩容至capacity//2（节省空间） 
	if self.size < self.capacity // 4 and self.capacity > 4: 
	self._resize(self.capacity // 2) 
	return x 
	
	def __getitem__(self, k): 
	"""支持arr[k]语法访问元素""" 
	if k < 0 or k >= self.size: 
	raise IndexError("访问索引越界") 
	return self.items[k] 
	
	def __len__(self): 
	"""支持len(arr)语法返回元素数量""" 
	return self.size 
	
	def __str__(self): 
	"""格式化输出数组内容""" 
	return "[" + ", ".join(map(str, [self.items[i] for i in range(self.size)])) + "]" 

3.4.3 实现解析

1. **内存管理**：通过`ctypes.py_object * capacity`申请连续内存块，存储Python对象引用（模拟Python列表的底层实现）。 
2. **扩容策略**：为简化实现，采用2倍扩容（实际Python为1.5倍），需注意扩容时新容量不得小于当前元素数量。 
3. **插入/删除元素**： 
- **插入**：从后往前移动元素，避免覆盖待移动元素（如在索引1插入时，需先移动索引3→4、2→3、1→2，再插入新元素到索引1）。 
- **删除**：从前往后移动元素，覆盖被删除元素，减少size后更新内存。 
4. **缩容机制**：当元素数量小于容量的1/4时，缩容至原容量的1/2（如容量16、size=3时缩容至8），避免空间浪费（Python列表不会主动缩容，需通过`lst = lst[:]`触发）。 

3.4.4 使用示例

python

	# 创建动态数组 
	arr = DynamicArray() 
	print(arr) # 输出：[]（初始size=0） 
	
	# 尾部添加 
	arr.append(1) 
	arr.append(2) 
	arr.append(3) 
	print(arr) # 输出：[1, 2, 3]（size=3, capacity=4） 
	
	# 插入元素 
	arr.insert(1, 10) # 在索引1插入10 
	print(arr) # 输出：[1, 10, 2, 3]（size=4, capacity=4 → 插入后size=5，触发扩容至8） 
	
	# 删除元素 
	arr.pop(1) # 删除索引1的元素（10） 
	print(arr) # 输出：[1, 2, 3]（size=3, capacity=8 → 因size=3 < 8//4=2不成立，不缩容） 
	
	# 访问元素 
	print(arr[2]) # 输出：3（通过索引访问）

3.5 实战：基于列表的稀疏矩阵实现
3.5.1 问题背景
在科学计算、图像处理等领域，稀疏矩阵（矩阵中大部分元素为0）是常见数据结构。例如，1000×1000的社交网络邻接矩阵中，非0元素（表示用户间的连接）可能仅占0.1%，若用普通二维列表存储（[[0]*1000 for _ in range(1000)]），需存储10⁶个元素，其中99.9%为0，空间浪费严重。
解决方案：采用三元组列表法存储稀疏矩阵，仅记录非0元素的（行索引, 列索引, 值），显著节省空间并提升操作效率。
3.5.2 稀疏矩阵的存储策略
三元组列表法：用列表存储所有非0元素的三元组(i, j, val)，其中i为行索引，j为列索引，val为元素值，同时记录矩阵的总行数（rows）和总列数（cols）。例如，矩阵：
[003400050] egin{bmatrix} 0 & 0 & 3 4 & 0 & 0 0 & 5 & 0 end{bmatrix} ​040​005​300​​
可表示为rows=3, cols=3, data=[(0,2,3), (1,0,4), (2,1,5)]。
3.5.3 稀疏矩阵类的实现
python

	class SparseMatrix: 
	def __init__(self, rows, cols): 
	self.rows = rows # 矩阵行数 
	self.cols = cols # 矩阵列数 
	self.data = [] # 存储非0元素：[(i, j, val), ...]，按行优先排序（非必须，便于查找） 
	
	def set(self, i, j, val): 
	"""设置(i,j)位置元素值，val=0时删除该元素""" 
	if not (0 <= i < self.rows and 0 <= j < self.cols): 
	raise IndexError("矩阵索引越界") 
	# 查找是否已存在(i,j)元素（遍历data列表，O(k)，k为非0元素数） 
	for idx in range(len(self.data)): 
	x, y, _ = self.data[idx] 
	if x == i and y == j: 
	if val == 0: 
	del self.data[idx] # 值为0时删除该三元组 
	else: 
	self.data[idx] = (i, j, val) # 更新值 
	return 
	# 新元素且val≠0时添加三元组 
	if val != 0: 
	self.data.append((i, j, val)) 
	# 可选：保持data按行/列索引排序，便于后续二分查找优化 
	self.data.sort(key=lambda x: (x[0], x[1])) 
	
	def get(self, i, j): 
	"""获取(i,j)位置元素值，默认返回0""" 
	# 线性查找（O(k)），可优化为二分查找（需保证data有序） 
	for x, y, val in self.data: 
	if x == i and y == j: 
	return val 
	return 0 
	
	def add(self, other): 
	"""矩阵加法：返回self + other的结果矩阵""" 
	if self.rows != other.rows or self.cols != other.cols: 
	raise ValueError("矩阵尺寸不匹配（行数或列数不同）") 
	result = SparseMatrix(self.rows, self.cols) 
	# 添加self的所有非0元素 
	for i, j, val in self.data: 
	result.set(i, j, val) 
	# 添加other的所有非0元素，重叠位置自动求和 
	for i, j, val in other.data: 
	result.set(i, j, result.get(i, j) + val) 
	return result 
	
	def __str__(self): 
	"""格式化输出矩阵（仅用于小矩阵可视化）""" 
	# 构建全0矩阵，填充非0元素 
	matrix = [[0]*self.cols for _ in range(self.rows)] 
	for i, j, val in self.data: 
	matrix[i][j] = val 
	return "
".join([" ".join(map(str, row)) for row in matrix]) 

3.5.4 性能分析与应用

**空间复杂度**：仅存储非0元素，空间复杂度为O(k)（k为非0元素数），远优于普通矩阵的O(rows×cols)。例如，1000×1000矩阵若k=1000，空间占用仅为普通矩阵的0.1%。 

**时间复杂度**： 
- `set`/`get`操作：线性查找时O(k)，若对`data`排序后采用二分查找，可优化至O(log k)。 
- 矩阵加法：遍历两个矩阵的非0元素，时间复杂度O(k1 + k2)（k1、k2为两个矩阵的非0元素数），优于普通矩阵加法的O(rows×cols)。 

**应用场景**：社交网络邻接矩阵、自然语言处理的词向量矩阵、有限元分析的系数矩阵等稀疏数据场景。 

3.6 本章总结

- **数组**是连续内存存储的线性结构，核心优势是O(1)随机访问，缺点是大小固定、插入删除低效； 
- **Python列表**基于动态数组实现，通过1.5倍扩容策略支持动态大小，`append`均摊O(1)，`insert/pop(k)`为O(n)； 
- **动态数组设计**需关注容量管理（扩容/缩容策略）、元素移动（插入/删除时）和内存效率（如1.5倍扩容平衡时间与空间）； 
- **稀疏矩阵案例**展示了列表在非连续数据存储中的优势，通过三元组列表法显著节省空间，提升操作效率。 

数组与列表作为最基础的线性结构，是实现栈、队列、哈希表等高级数据结构的基石，后续章节将基于列表进一步展开线性结构的应用与优化。 

思考题

1. 分析以下Python列表操作的时间复杂度，并解释原因： 

python

	lst = [1, 2, 3, 4, 5] 
	lst.append(6) # 操作1 
	lst.insert(0, 0) # 操作2 
	lst.pop(3) # 操作3 
	5 in lst # 操作4

动态数组扩容时，若采用“每次+1”的扩容策略（而非倍数扩容），则n次append操作的总时间复杂度是多少？（提示：分析第i次append的耗时，求和后除以n）

设计一个基于列表的“循环缓冲区”（固定大小的队列），支持enqueue(x)（入队）和dequeue()（出队）操作，当缓冲区满时新元素覆盖最早入队的元素，要求所有操作时间复杂度为O(1)。
稀疏矩阵的get方法当前为线性查找（O(k)），如何通过排序和二分查找优化为O(log k)？实现优化后的get方法（提示：对三元组按行、列索引排序，使用bisect模块定位）。

本站原创，转载请注明出处：