Python实现动态数组：增删改查与扩容

"该资源提供了一个Python实现的动态数组示例，主要目的是为了演示如何创建一个支持动态扩容的数组，并实现基本的增删改查功能。动态数组在添加和删除元素时能自动调整其容量，以适应数据的变化。" 在这个Python实现的动态数组中，我们首先了解动态数组的特点： 1. **连续内存空间**：动态数组占用一段连续的内存空间，这使得我们可以通过索引来快速访问数组中的元素，时间复杂度为O(1)。 2. **随机访问**：支持通过索引进行随机访问，提高了数据处理的效率。 3. **动态扩容**：当数组满时，它能够自动扩大容量以容纳更多的元素。在这个例子中，默认的扩容策略是将当前容量翻倍。 接下来，我们将详细分析给出的动态数组类`Arr`的各个方法： - **构造函数 (`__init__`)**：初始化动态数组，设置初始容量（默认为10）和数组有效元素的数目（初始化为0）。同时，创建一个全由`None`填充的列表`_data`，用于模拟固定容量的数组。 - **获取元素 (`__getitem__`)**：这个方法实现了索引操作，允许用户通过索引获取数组中的元素。 - **获取大小 (`getSize`)**：返回数组中有效元素的数量。 - **获取容量 (`getCapacity`)**：返回当前数组的总容量，即可以存储的最大元素数量。 - **判断是否为空 (`isEmpty`)**：检查数组的有效元素个数是否为0，如果是，则返回True，表示数组为空。 - **添加元素 (`add`)**：在指定位置插入元素。此方法需要检查索引是否有效，如果数组已满，会调用`_resize`方法进行扩容。插入元素时，需要将后面的所有元素依次向后移动一位，以保持连续的内存空间。添加操作的时间复杂度为O(n)，因为可能需要移动所有元素。 - **扩容 (`_resize`)**：当数组满时，`_resize`方法被调用以增加数组容量。在这个例子中，容量翻倍以达到扩容的目的，这种策略可以降低平均插入操作的时间复杂度。 - **删除元素**：虽然在提供的代码中没有直接实现删除元素的方法，但通常删除元素的操作会涉及到移动后续元素以填补空位，其时间复杂度也是O(n)。 - **修改元素**：可以通过索引直接修改`_data`列表中的元素，实现对动态数组的修改操作。 这个动态数组类`Arr`提供了基本的数组操作，包括初始化、查询、获取大小、判断是否为空以及添加元素等功能。它的设计目标是模拟一种固定容量且支持动态扩容的数据结构，以适应数据量的变化。虽然在Python中，内置的`list`类型已经具备了这些特性，但这个实现可以帮助理解动态数组的工作原理，并可以作为教学或练习用例。