Python实现动态数组：详解与示例代码

"本文将详细介绍如何在Python中实现动态数组，并提供相关示例代码，以帮助读者理解动态数组的概念和操作。动态数组是一种可以自动调整大小的数组，它在需要时能够扩大或缩小容量，以适应存储数据的需求。在Python中，虽然内置的列表已经具备了动态扩展的功能，但为了深入理解动态数组的原理，我们将创建一个自定义的动态数组类，模拟类似C++中的vector。" 在计算机科学中，动态数组是一种数据结构，它允许在数组的末尾添加或删除元素，同时自动调整数组的大小。在Python中，尽管内置的`list`类型已经具备了这些特性，但为了学习和理解动态数组的工作机制，我们可以自行创建一个类来实现这一功能。 首先，我们需要了解动态数组的一些基本特点： 1. **连续的内存空间**：动态数组中的元素存储在一段连续的内存区域中，这使得随机访问元素（通过索引）的时间复杂度为O(1)。 2. **动态扩容**：当数组满时，需要增加其容量以容纳更多元素，这通常涉及复制现有元素到新的更大的内存区域。 3. **插入和删除操作**：在数组中间插入或删除元素时，可能需要移动后面的元素，这会导致O(n)的时间复杂度。 以下是一个简单的Python动态数组实现： ```python class Arr: def __init__(self, capacity=10): self._capacity = capacity self._size = 0 # 数组有效元素的数目，初始化为0 self._data = [None] * self._capacity # 使用None表示无效元素 def __getitem__(self, item): return self._data[item] def get_size(self): return self._size def get_capacity(self): return self._capacity def is_empty(self): return self._size == 0 def add(self, index, elem): if index < 0 or index > self._size: # 插入位置无效 raise Exception('AddFailed. Require 0 <= index <= self._size') if self._size == self._capacity: # 满了 self._resize(2 * self._capacity) # 扩容至原来的两倍 for i in range(self._size - 1, index, -1): # 从后向前挪动元素 self._data[i + 1] = self._data[i] self._data[index] = elem self._size += 1 def _resize(self, new_capacity): old_data = self._data self._data = [None] * new_capacity for i in range(self._size): self._data[i] = old_data[i] # 其他方法，如删除、查找等可按需添加 ``` 在这个`Arr`类中，我们实现了动态数组的基本操作： - `__init__`: 初始化动态数组，设置初始容量和无效元素。 - `__getitem__`: 支持索引访问，返回指定位置的元素。 - `get_size`和`get_capacity`: 分别返回数组的有效元素数量和当前容量。 - `is_empty`: 检查数组是否为空。 - `add`: 向数组中添加元素。如果数组已满，会调用`_resize`方法进行扩容。注意插入操作需要从后向前移动元素以保持连续性。 - `_resize`: 内部方法，用于调整数组容量。新容量通常是旧容量的两倍，这是常见的扩容策略，可以减少频繁扩容造成的开销。 这个简单的动态数组类展示了动态数组的核心概念。在实际应用中，可能还需要添加更多的功能，例如删除元素、在数组末尾添加元素（`append`）、在数组开头插入元素（`prepend`）等。同时，对于性能敏感的应用，可以考虑更高效的扩容策略，如每次只扩展原容量的一定比例，而非翻倍。