手写 List 容器的动态扩容实现

动态扩容是 List 容器的核心特性，通过以下步骤实现从固定大小到无限扩展：

1. 核心设计思想

• 初始固定容量：创建时分配固定大小的底层数组
• 扩容触发条件：当添加元素时检测到数组已满
• 扩容策略：创建新数组（通常为原容量的 $1.5$ 或 $2$ 倍）
• 数据迁移：将原数组元素复制到新数组
• 引用更新：将底层数组引用指向新数组

2. Python 实现代码

class DynamicList:
    def __init__(self, initial_capacity=10):
        self._capacity = initial_capacity  # 当前容量
        self._size = 0  # 当前元素数量
        self._data = [None] * initial_capacity  # 底层存储数组
    
    def __len__(self):
        return self._size
    
    def __getitem__(self, index):
        if index < 0 or index >= self._size:
            raise IndexError("Index out of range")
        return self._data[index]
    
    def __str__(self):
        return "[" + ", ".join(str(x) for x in self._data[:self._size]) + "]"
    
    def append(self, value):
        # 检测是否需要扩容
        if self._size == self._capacity:
            self._resize(int(self._capacity * 1.5) + 1)  # 1.5倍扩容
        
        # 添加新元素
        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]
        
        # 更新引用和容量
        self._data = new_data
        self._capacity = new_capacity
        print(f"扩容至 {new_capacity} 容量")  # 调试信息

# 测试用例
if __name__ == "__main__":
    lst = DynamicList(initial_capacity=3)
    
    print("初始状态:", lst)
    print("添加元素 1, 2, 3...")
    lst.append(1)
    lst.append(2)
    lst.append(3)
    print("当前状态:", lst)
    
    print("添加元素 4 (触发扩容)...")
    lst.append(4)
    print("扩容后状态:", lst)
    
    print("添加元素 5, 6, 7...")
    lst.append(5)
    lst.append(6)
    lst.append(7)
    print("当前状态:", lst)

3. 关键特性说明

1. 时间复杂度：

   • 添加元素平均时间复杂度 $O(1)$
   • 扩容操作时间复杂度 $O(n)$
   • 均摊分析后添加操作仍为 $O(1)$

2. 扩容因子选择：

   • 使用 $1.5$ 倍扩容（示例代码）
   • 也可采用 $2$ 倍扩容（常见实现）
   • 数学证明：当扩容因子 $>1$ 时可保证均摊时间复杂度为 $O(1)$

3. 内存管理：

   • 旧数组在扩容后由垃圾回收器自动回收
   • 避免频繁扩容：根据预估数据量设置合理初始容量

4. 执行结果示例

初始状态: []
添加元素 1, 2, 3...
当前状态: [1, 2, 3]
添加元素 4 (触发扩容)...
扩容至 4 容量
扩容后状态: [1, 2, 3, 4]
添加元素 5, 6, 7...
扩容至 6 容量
当前状态: [1, 2, 3, 4, 5, 6, 7]

此实现完整展示了动态扩容的核心机制，可根据需求扩展插入、删除等功能，同时保持高效的内存管理和时间复杂度特性。