python实现动态数组的示例代码

Python 动态数组是一种数据结构，它允许在运行时改变其大小。在Python中，列表（list）本质上就是一种动态数组，因为它可以自动调整大小以适应新的元素。然而，为了更好地理解动态数组的概念，我们可以自定义一个类来模拟这种数据结构，就像在给定的代码中所做的那样。 在自定义的动态数组类`Arr`中，我们有以下几个关键功能： 1. **构造函数** (`__init__`)：初始化动态数组，设置初始容量（默认为10），并创建一个全由`None`填充的列表，以表示数组的内存空间。 2. **索引操作** (`__getitem__`)：使得`Arr`类支持索引访问，返回指定索引处的元素。这是Python中实现自定义数据结构常用的方法，使得我们可以像操作列表一样操作自定义的类实例。 3. **getSize**：返回数组中有效元素的数量，即实际存储的元素个数。 4. **getCapacity**：返回当前数组的总容量，即数组能够存储的最大元素数量。 5. **isEmpty**：检查数组是否为空，如果有效元素数量为0，则返回True，否则返回False。 6. **add**：向数组中指定位置插入元素。此方法首先检查插入位置是否合法，然后判断数组是否已满。如果满，则通过`_resize`方法进行扩容。扩容时，默认将容量扩大一倍，以保持平均时间复杂度为O(1)。在插入元素后，需要将所有后续元素向后移动一位以保持连续性。 7. **addLast**：在数组末尾添加元素，这是最高效的添加方式，时间复杂度为O(1)，因为它直接调用`add`方法，传入当前的`_size`作为索引。 8. **addFirst**：在数组开头添加元素，需要将所有元素向前移动一位，因此时间复杂度为O(n)。 9. **get**：获取指定索引处的元素，时间复杂度为O(1)，因为Python列表的索引访问是常数时间复杂度。 10. **_resize**：这个私有方法用于扩容数组。当数组满时，将容量增加到原来的两倍，并重新分配内存。这确保了在大多数操作中，平均时间复杂度保持为O(1)。 这个自定义的动态数组类`Arr`虽然在Python中不是必需的，但它提供了一个理解动态数组概念的机会，并展示了如何在Python中实现基本的数据结构操作。在实际编程中，Python的内置列表通常足以满足大多数需求，但自定义实现可以帮助我们更好地控制内存管理和性能。