hello-algo 源码解析用 Python 从零实现自动扩容的动态数组 MyList【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo导读本文围绕《Hello 算法》仓库中 ru/codes/pythontutor/chapter_array_and_linkedlist/my_list.md 这份“Python Tutor 可视化运行”文档展开——它表面只有一行被 URL 编码的长链接解码后其实是一份完整的MyList动态列表类源码与驱动用例。读完本文你将掌握数组实现“列表”为何需要记录容量与长度、扩容机制如何在运行时自动触发、get/set/add/insert/remove每一步背后发生了什么并能直接运行仓库源码观察实测输出从而真正理解 Python 内建list这类“动态数组”的底层工作方式。一、为什么需要“动态数组”列表与数组的区别要理解MyList的用途需要先回到基础概念。在《Hello 算法》中列表list被定义为“元素的有序集合”支持访问、修改、添加、删除、遍历等操作且使用者无须考虑容量限制。它既可以基于链表实现也可以基于数组实现链表天然可以视为列表增删改查灵活可动态扩容数组也支持增删改查但长度不可变只能看作一个“有长度上限”的列表。基于数组实现列表时“长度不可变”会严重限制实用性——我们很难在程序运行前预测要存储多少数据长度定小了装不下定大了又浪费内存。解决方案正是动态数组dynamic array它继承数组的所有优点连续的存储、$O(1)$ 随机访问同时可以在运行期自动扩容。正如 docs/chapter_array_and_linkedlist/list.md 中所指出的许多编程语言标准库中的列表正是基于动态数组实现的例如 Python 的list、Java 的ArrayList、C 的vector、C# 的List。因此“列表”与“动态数组”在该书的语境下常被视为等同概念而手写一个简易列表是理解这一切的绝佳途径。二、可视化文档里到底装着什么从一行 URL 到完整类本文的关联文档 ru/codes/pythontutor/chapter_array_and_linkedlist/my_list.md 是俄语本地化版本中的一个 Python Tutor 可视化页面占位文件。文件正文只有一行经过百分号编码URL-encoded的长链接将其解码后可以还原出一份可读的 Python 源码其逻辑核心正是《Hello 算法》“列表”一章“列表实现”小节中所讲解的简易列表类。从仓库结构看这套可视化 md 文件在中文区位于 codes/pythontutor/chapter_array_and_linkedlist/my_list.md且在 zh-hant、ja、ru 等本地化目录中都有对应副本。之所以文档头部带有 HTML 注释[file]{my_list}-[class]{my_list}-[func]{}是在标记“本次可视化对应的源码文件是my_list、定位目标是其中的MyList类”方便读者把动画化的逐步执行与真实源码一一对应起来。该可视化文档所承载的代码与仓库中可独立运行的 Python 源码是同一份教学内容两者互为表里中文完整版codes/python/chapter_array_and_linkedlist/my_list.py俄语完整版ru/codes/python/chapter_array_and_linkedlist/my_list.py。把可视化文档解码后与上述两个源文件逐一对照可以发现它是一份“为可视化而精简”的版本主要有三点差异省略了输出辅助方法to_array()以及驱动代码里的全部print(...)因为 Python Tutor 的逐步演示不依赖终端打印重点在于观察变量与堆内存的变化省去了大量中文/俄文注释使代码更紧凑insert()方法内部略有简化完整版只有当“长度等于容量”时才调用扩容见 my_list.py而可视化版直接调用了extend_capacity()。从两份文件的对比可以推断这是为压缩演示代码所作的简化功能结果不受影响只是会提前触发一次扩容。值得强调的是编码形式不影响代码本质。无论从哪一份 md 解码得到的都是同一套“动态列表”实现思路这也是我们接下来逐行拆解的对象。三、三个核心设计初始容量、数量记录与扩容倍数仿照内建列表的实现思路MyList的设计围绕三个重点展开可对照 docs/chapter_array_and_linkedlist/list.md 的“列表实现”小节设计点本实现中的取值作用初始容量_capacity 10构造时一次性预分配 10 个元素的底层数组避免频繁申请内存数量记录_size 0实时记录“已使用”的元素个数用于定位尾部、判断是否扩容扩容倍数_extend_ratio 2容量不足时把底层数组扩为原来的 2 倍其中“数量记录”是关键桥梁_size与_capacity是两个容易混淆但又必须区分的量——_capacity是底层数组最多能装多少元素物理上限_size是当前实际存了多少元素逻辑长度。任何访问、插入、删除操作都以_size为界而不是以_capacity为界这从下文各方法的越界判断中可以得到印证。四、类的内部状态与构造方法MyList的构造方法定义了四个实例属性完整源码位于 codes/python/chapter_array_and_linkedlist/my_list.pyclass MyList: 列表类 def __init__(self): 构造方法 self._capacity: int 10 # 列表容量 self._arr: list[int] [0] * self._capacity # 数组存储列表元素 self._size: int 0 # 列表长度当前元素数量 self._extend_ratio: int 2 # 每次列表扩容的倍数需要特别留意的初始化细节是self._arr [0] * self._capacity这里一次性创建了长度为 10、元素全为 0 的底层数组。0仅是“占位值”后续真正属于列表的元素个数始终由_size决定未被_size覆盖到的槽位索引_size .. _capacity-1属于“预留空间”对使用者不可见。如果只把可视化文档解码后运行__init__会创建一个容量 10、长度 0 的空MyList实例——这正是驱动代码的第一句nums MyList()所做的事情。五、只读操作size、capacity、get、set 与越界保护MyList对外提供四个基础“查询/更新”方法my_list.pydef size(self) - int: 获取列表长度当前元素数量 return self._size def capacity(self) - int: 获取列表容量 return self._capacity def get(self, index: int) - int: 访问元素 # 索引如果越界则抛出异常下同 if index 0 or index self._size: raise IndexError(索引越界) return self._arr[index] def set(self, num: int, index: int): 更新元素 if index 0 or index self._size: raise IndexError(索引越界) self._arr[index] numget与set的核心是**“先校验、后操作”**合法索引必须同时满足index 0与index self._size。它不检查index _capacity因为对使用者而言凡是落在[_size, _capacity)区间内的槽位都是“越界”的不应被读到或改写校验失败时统一抛出IndexError(索引越界)。这是 Python 内建序列类型在越界时抛出的异常类型本实现沿用了这一惯例调用方可以用标准的try/except IndexError捕获二者时间复杂度均为 $O(1)$这也是“列表本质上是数组可以在 $O(1)$ 时间内访问和更新元素”的直接体现。注意set的参数顺序是set(num, index)即“先元素值、后索引”。驱动代码中的nums.set(0, 1)表示把索引 1 处的元素更新为 0与易混淆的“下标在前”习惯不同阅读源码时务必看清参数顺序。六、写操作add、insert、remove 与元素搬移6.1 在尾部添加元素 add()def add(self, num: int): 在尾部添加元素 # 元素数量超出容量时触发扩容机制 if self.size() self.capacity(): self.extend_capacity() self._arr[self._size] num self._size 1add()的逻辑my_list.py分三步若_size _capacity说明底层数组已满先调用extend_capacity()扩容把新元素写入_arr[_size]尾部第一个空闲槽位_size自增更新逻辑长度。由于扩容被“均摊”到多次添加中尾部添加的均摊时间复杂度为 $O(1)$而恰好触发扩容的那一次单次操作代价为 $O(n)$需要整体搬迁这一点在第七节的实测输出中会有直观体现。6.2 在中间插入元素 insert()def insert(self, num: int, index: int): 在中间插入元素 if index 0 or index self._size: raise IndexError(索引越界) # 元素数量超出容量时触发扩容机制 if self._size self.capacity(): self.extend_capacity() # 将索引 index 以及之后的元素都向后移动一位 for j in range(self._size - 1, index - 1, -1): self._arr[j 1] self._arr[j] self._arr[index] num # 更新元素数量 self._size 1insert()my_list.py是三种写操作里最容易写错边界的一处值得细看越界条件同样取index self._size即本实现不允许index self._size用insert在“末尾之后”追加会抛异常。这与 Python 内建list.insert的宽松语义允许插入到len(nums)位置超出时自动钳制到末尾并不相同属于教学版简化设计需要追加时请使用add()容量满时先扩容随后执行倒序搬移for j in range(self._size - 1, index - 1, -1)从最后一个有效元素开始逐个把_arr[j]复制到_arr[j 1]。必须倒序遍历——若正序搬移后面的元素会覆盖尚未搬走的元素搬移完成后在index处写入新值_size自增。搬移是线性开销因此中间插入的时间复杂度为 $O(n)$与普通数组完全一致。值得注意的是可视化版 md 中的insert()省略了“容量已满”判断而直接扩容属于上文中提到的精简差异之一。6.3 删除元素 remove()def remove(self, index: int) - int: 删除元素 if index 0 or index self._size: raise IndexError(索引越界) num self._arr[index] # 将索引 index 之后的元素都向前移动一位 for j in range(index, self._size - 1): self._arr[j] self._arr[j 1] # 更新元素数量 self._size - 1 # 返回被删除的元素 return numremove()my_list.py与insert互为镜像越界校验后先暂存待删元素num它作为返回值执行正序前移for j in range(index, self._size - 1)把后面的每个元素向左挪一位覆盖被删位置_size自减。这里有一个值得注意的实现细节删除只缩减_size并不会缩减底层数组容量也不会把“旧值”清零。最末位的残留值是冗余数据因为所有操作都以_size为边界它永远不会再被读到。换言之本实现“只扩容、不缩容”若需在删除大量元素后回收内存需要另行设计缩容逻辑。remove()返回被删元素这与内建list.pop(index)的行为一致。七、扩容机制 extend_capacity 深度拆解扩容是整个动态数组的“发动机”其实现my_list.py只有三行def extend_capacity(self): 列表扩容 # 新建一个长度为原数组 _extend_ratio 倍的新数组并将原数组复制到新数组 self._arr self._arr [0] * self.capacity() * (self._extend_ratio - 1) # 更新列表容量 self._capacity len(self._arr)拆开看它的工作过程[0] * capacity() * (_extend_ratio - 1)先构造一段“新增的占位区”。以容量 10、扩容倍数 2 为例即追加10 * (2 - 1) 10个 0self._arr self._arr [...]把旧数组与新占位区拼成一个新列表等价于“申请 2 倍新空间并把旧元素逐个复制过去”self._capacity len(self._arr)让容量属性与实际底层数组长度保持一致。这种利用列表运算符完成的扩容是 Python 版本特有的“偷懒”写法——底层仍是分配新空间 整体搬迁旧数据代价为 $O(n)$。同样的思想在 C 语言版 codes/c/chapter_array_and_linkedlist/my_list.c 中被显式地表达了出来先malloc一块capacity * extendRatio的新内存逐元素拷贝free旧数组再更新指针与容量。对比两个语言版本可以看出Python 依靠内置的列表拼接语法隐藏了内存管理细节而 C 版本必须手工完成分配、拷贝、释放的全过程——这也解释了为什么 C 没有内置动态数组需要自行实现MyList这类结构原书在list.c中注明的“C 未提供内置动态数组”。扩容的触发时机有两处入口add()与insert()在发现_size _capacity时都会调用extend_capacity()。由于每次扩容都把容量翻倍扩容次数是 $O(\log n)$ 量级把各次扩容的整体搬迁成本摊到每一次add()上就得到了动态数组“尾部添加均摊 $O(1)$”的经典结论——这正是动态数组相比固定长度数组的根本优势。八、完整类源码与驱动用例实测把上述方法汇总加上可视化版中省略的to_array()辅助方法就得到可独立运行的完整实现my_list.py 增加了用于打印的to_arrayclass MyList: 列表类 def __init__(self): 构造方法 self._capacity: int 10 # 列表容量 self._arr: list[int] [0] * self._capacity # 数组存储列表元素 self._size: int 0 # 列表长度当前元素数量 self._extend_ratio: int 2 # 每次列表扩容的倍数 def size(self) - int: 获取列表长度当前元素数量 return self._size def capacity(self) - int: 获取列表容量 return self._capacity def get(self, index: int) - int: 访问元素 # 索引如果越界则抛出异常下同 if index 0 or index self._size: raise IndexError(索引越界) return self._arr[index] def set(self, num: int, index: int): 更新元素 if index 0 or index self._size: raise IndexError(索引越界) self._arr[index] num def add(self, num: int): 在尾部添加元素 # 元素数量超出容量时触发扩容机制 if self.size() self.capacity(): self.extend_capacity() self._arr[self._size] num self._size 1 def insert(self, num: int, index: int): 在中间插入元素 if index 0 or index self._size: raise IndexError(索引越界) # 元素数量超出容量时触发扩容机制 if self._size self.capacity(): self.extend_capacity() # 将索引 index 以及之后的元素都向后移动一位 for j in range(self._size - 1, index - 1, -1): self._arr[j 1] self._arr[j] self._arr[index] num # 更新元素数量 self._size 1 def remove(self, index: int) - int: 删除元素 if index 0 or index self._size: raise IndexError(索引越界) num self._arr[index] # 将索引 index 之后的元素都向前移动一位 for j in range(index, self._size - 1): self._arr[j] self._arr[j 1] # 更新元素数量 self._size - 1 # 返回被删除的元素 return num def extend_capacity(self): 列表扩容 # 新建一个长度为原数组 _extend_ratio 倍的新数组并将原数组复制到新数组 self._arr self._arr [0] * self.capacity() * (self._extend_ratio - 1) # 更新列表容量 self._capacity len(self._arr) def to_array(self) - list[int]: 返回有效长度的列表 return self._arr[: self._size]配套的 Driver Codemy_list.py按“初始化 → 尾部添加 → 中间插入 → 删除 → 访问 → 更新 → 扩容”的顺序演示了全部操作。其中最后一个for i in range(10): nums.add(i)专门用来触发扩容。在仓库根目录执行python3 codes/python/chapter_array_and_linkedlist/my_list.py可以拿到如下实测输出运行于本仓库当前代码Python 3列表 nums [1, 3, 2, 5, 4] 容量 10 长度 5 在索引 3 处插入数字 6 得到 nums [1, 3, 2, 6, 5, 4] 删除索引 3 处的元素得到 nums [1, 3, 2, 5, 4] 访问索引 1 处的元素得到 num 3 将索引 1 处的元素更新为 0 得到 nums [1, 0, 2, 5, 4] 扩容后的列表 [1, 0, 2, 5, 4, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 容量 20 长度 15逐行对照可视化文档的驱动代码可以还原出每一步的内部状态步骤操作数组内容长度容量关键事件1MyList()[]010预分配 10 个槽位2依次add(1/3/2/5/4)[1, 3, 2, 5, 4]510尾部添加均摊 $O(1)$3insert(6, index3)[1, 3, 2, 6, 5, 4]610索引 3 及之后元素整体后移一位4remove(3)[1, 3, 2, 5, 4]510返回被删元素 65num get(1)———返回36set(0, 1)[1, 0, 2, 5, 4]510把索引 1 更新为 07再add(0..9)见上最后一行1520在i 5时容量用尽触发扩容 10 → 20第 7 步正是扩容机制的现场演示当第 6 个追加元素到达时i 5_size恰好等于_capacity 10add()检测到容量已满便调用extend_capacity()把底层数组翻倍为 20 个槽位随后继续完成剩余 4 次添加最终长度 15、容量 20、闲置槽位 5 个。这也验证了上文对扩容触发时机与“只扩不缩”行为的分析。九、设计取舍与边界行为小结从逐行拆解中可以提炼出这套教学实现的设计取向与边界约定初始容量与扩容倍数都是可调参数。仓库代码将初始容量定为 10、扩容倍数定为 2。现实中标准库对这两个参数的选择更为考究涉及内存利用率与搬迁次数之间的平衡这里选用小容量、2 倍增长的组合是为了让读者在可视化演示中尽快观察到扩容的发生越界判定统一使用index 0 or index _size。对空列表调用get/set/remove/insert均会抛出IndexError因为此时任何索引都不满足0 index 0insert不允许把元素插到逻辑末尾之后即index _size非法需要追加请走add()。这与内建list.insert的宽松语义存在差异是刻意简化后的边界行为删除操作只减_size不缩容。底层数组一旦扩容到 20 便保持该大小即使之后不断remove容量也不会自动回落可视化版与运行版的细微差异已在第二节说明md 中的版本省略了to_array()、打印语句和部分注释且insert()直接调用扩容。因此严格地说md 版是“演示剪辑版”本文第八节提供的完整源码才是与仓库 codes/python/chapter_array_and_linkedlist/my_list.py 完全一致的运行版本。若想用另一门语言加深理解可以对照 C 语言版 codes/c/chapter_array_and_linkedlist/my_list.c它用struct封装同样的四个字段arr/capacity/size/extendRatio用assert代替IndexError做越界保护用malloc/free手工完成扩容中的内存生命周期管理并把删除方法命名为removeItem避免与stdio.h中的remove()冲突。同一份设计在不同语言中的落地方案差异本身就是很好的对比学习素材。十、复杂度一览与延伸阅读把本节所有方法汇总可得完整的复杂度画像方法功能时间复杂度size()/capacity()查询长度 / 容量$O(1)$get(index)/set(num, index)随机访问 / 更新$O(1)$add(num)尾部添加均摊 $O(1)$单次扩容时 $O(n)$insert(num, index)中间插入$O(n)$元素搬移remove(index)删除并返回元素$O(n)$元素搬移extend_capacity()扩容$O(n)$新建数组 整体复制这套实现回答了一个关键问题Python 内建list为什么能“随便 append 而不必担心容量”。其答案是“动态数组 懒扩容”的设计组合——容量记录、长度记录、翻倍扩容这三板斧正是所有动态数组类容器共享的底层骨架。想继续深入可在仓库中结合以下文件系统学习“数组 ↔ 链表 ↔ 列表”的知识闭环可视化原始页codes/pythontutor/chapter_array_and_linkedlist/my_list.md含俄语副本 ru/codes/pythontutor/chapter_array_and_linkedlist/my_list.md完整 Python 源码codes/python/chapter_array_and_linkedlist/my_list.py 及俄语版 ru/codes/python/chapter_array_and_linkedlist/my_list.pyC 语言对照实现codes/c/chapter_array_and_linkedlist/my_list.c书本正文与背景知识docs/chapter_array_and_linkedlist/list.md、docs/chapter_array_and_linkedlist/array.md本章其余篇幅在《Hello 算法》的数组与链表章节中还有对静态数组、链表及内存布局的完整讲解可作为动态数组的前置知识一并阅读。下次当你写下nums.append(x)时不妨想想背后那个默默“翻倍扩容”的extend_capacity——这就是动态数组的魔法所在。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 hello-algo 源码解析：用 Python 从零实现自动扩容的动态数组 MyList
hello-algo 源码解析用 Python 从零实现自动扩容的动态数组 MyList【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo导读本文围绕《Hello 算法》仓库中 ru/codes/pythontutor/chapter_array_and_linkedlist/my_list.md 这份“Python Tutor 可视化运行”文档展开——它表面只有一行被 URL 编码的长链接解码后其实是一份完整的MyList动态列表类源码与驱动用例。读完本文你将掌握数组实现“列表”为何需要记录容量与长度、扩容机制如何在运行时自动触发、get/set/add/insert/remove每一步背后发生了什么并能直接运行仓库源码观察实测输出从而真正理解 Python 内建list这类“动态数组”的底层工作方式。一、为什么需要“动态数组”列表与数组的区别要理解MyList的用途需要先回到基础概念。在《Hello 算法》中列表list被定义为“元素的有序集合”支持访问、修改、添加、删除、遍历等操作且使用者无须考虑容量限制。它既可以基于链表实现也可以基于数组实现链表天然可以视为列表增删改查灵活可动态扩容数组也支持增删改查但长度不可变只能看作一个“有长度上限”的列表。基于数组实现列表时“长度不可变”会严重限制实用性——我们很难在程序运行前预测要存储多少数据长度定小了装不下定大了又浪费内存。解决方案正是动态数组dynamic array它继承数组的所有优点连续的存储、$O(1)$ 随机访问同时可以在运行期自动扩容。正如 docs/chapter_array_and_linkedlist/list.md 中所指出的许多编程语言标准库中的列表正是基于动态数组实现的例如 Python 的list、Java 的ArrayList、C 的vector、C# 的List。因此“列表”与“动态数组”在该书的语境下常被视为等同概念而手写一个简易列表是理解这一切的绝佳途径。二、可视化文档里到底装着什么从一行 URL 到完整类本文的关联文档 ru/codes/pythontutor/chapter_array_and_linkedlist/my_list.md 是俄语本地化版本中的一个 Python Tutor 可视化页面占位文件。文件正文只有一行经过百分号编码URL-encoded的长链接将其解码后可以还原出一份可读的 Python 源码其逻辑核心正是《Hello 算法》“列表”一章“列表实现”小节中所讲解的简易列表类。从仓库结构看这套可视化 md 文件在中文区位于 codes/pythontutor/chapter_array_and_linkedlist/my_list.md且在 zh-hant、ja、ru 等本地化目录中都有对应副本。之所以文档头部带有 HTML 注释[file]{my_list}-[class]{my_list}-[func]{}是在标记“本次可视化对应的源码文件是my_list、定位目标是其中的MyList类”方便读者把动画化的逐步执行与真实源码一一对应起来。该可视化文档所承载的代码与仓库中可独立运行的 Python 源码是同一份教学内容两者互为表里中文完整版codes/python/chapter_array_and_linkedlist/my_list.py俄语完整版ru/codes/python/chapter_array_and_linkedlist/my_list.py。把可视化文档解码后与上述两个源文件逐一对照可以发现它是一份“为可视化而精简”的版本主要有三点差异省略了输出辅助方法to_array()以及驱动代码里的全部print(...)因为 Python Tutor 的逐步演示不依赖终端打印重点在于观察变量与堆内存的变化省去了大量中文/俄文注释使代码更紧凑insert()方法内部略有简化完整版只有当“长度等于容量”时才调用扩容见 my_list.py而可视化版直接调用了extend_capacity()。从两份文件的对比可以推断这是为压缩演示代码所作的简化功能结果不受影响只是会提前触发一次扩容。值得强调的是编码形式不影响代码本质。无论从哪一份 md 解码得到的都是同一套“动态列表”实现思路这也是我们接下来逐行拆解的对象。三、三个核心设计初始容量、数量记录与扩容倍数仿照内建列表的实现思路MyList的设计围绕三个重点展开可对照 docs/chapter_array_and_linkedlist/list.md 的“列表实现”小节设计点本实现中的取值作用初始容量_capacity 10构造时一次性预分配 10 个元素的底层数组避免频繁申请内存数量记录_size 0实时记录“已使用”的元素个数用于定位尾部、判断是否扩容扩容倍数_extend_ratio 2容量不足时把底层数组扩为原来的 2 倍其中“数量记录”是关键桥梁_size与_capacity是两个容易混淆但又必须区分的量——_capacity是底层数组最多能装多少元素物理上限_size是当前实际存了多少元素逻辑长度。任何访问、插入、删除操作都以_size为界而不是以_capacity为界这从下文各方法的越界判断中可以得到印证。四、类的内部状态与构造方法MyList的构造方法定义了四个实例属性完整源码位于 codes/python/chapter_array_and_linkedlist/my_list.pyclass MyList: 列表类 def __init__(self): 构造方法 self._capacity: int 10 # 列表容量 self._arr: list[int] [0] * self._capacity # 数组存储列表元素 self._size: int 0 # 列表长度当前元素数量 self._extend_ratio: int 2 # 每次列表扩容的倍数需要特别留意的初始化细节是self._arr [0] * self._capacity这里一次性创建了长度为 10、元素全为 0 的底层数组。0仅是“占位值”后续真正属于列表的元素个数始终由_size决定未被_size覆盖到的槽位索引_size .. _capacity-1属于“预留空间”对使用者不可见。如果只把可视化文档解码后运行__init__会创建一个容量 10、长度 0 的空MyList实例——这正是驱动代码的第一句nums MyList()所做的事情。五、只读操作size、capacity、get、set 与越界保护MyList对外提供四个基础“查询/更新”方法my_list.pydef size(self) - int: 获取列表长度当前元素数量 return self._size def capacity(self) - int: 获取列表容量 return self._capacity def get(self, index: int) - int: 访问元素 # 索引如果越界则抛出异常下同 if index 0 or index self._size: raise IndexError(索引越界) return self._arr[index] def set(self, num: int, index: int): 更新元素 if index 0 or index self._size: raise IndexError(索引越界) self._arr[index] numget与set的核心是**“先校验、后操作”**合法索引必须同时满足index 0与index self._size。它不检查index _capacity因为对使用者而言凡是落在[_size, _capacity)区间内的槽位都是“越界”的不应被读到或改写校验失败时统一抛出IndexError(索引越界)。这是 Python 内建序列类型在越界时抛出的异常类型本实现沿用了这一惯例调用方可以用标准的try/except IndexError捕获二者时间复杂度均为 $O(1)$这也是“列表本质上是数组可以在 $O(1)$ 时间内访问和更新元素”的直接体现。注意set的参数顺序是set(num, index)即“先元素值、后索引”。驱动代码中的nums.set(0, 1)表示把索引 1 处的元素更新为 0与易混淆的“下标在前”习惯不同阅读源码时务必看清参数顺序。六、写操作add、insert、remove 与元素搬移6.1 在尾部添加元素 add()def add(self, num: int): 在尾部添加元素 # 元素数量超出容量时触发扩容机制 if self.size() self.capacity(): self.extend_capacity() self._arr[self._size] num self._size 1add()的逻辑my_list.py分三步若_size _capacity说明底层数组已满先调用extend_capacity()扩容把新元素写入_arr[_size]尾部第一个空闲槽位_size自增更新逻辑长度。由于扩容被“均摊”到多次添加中尾部添加的均摊时间复杂度为 $O(1)$而恰好触发扩容的那一次单次操作代价为 $O(n)$需要整体搬迁这一点在第七节的实测输出中会有直观体现。6.2 在中间插入元素 insert()def insert(self, num: int, index: int): 在中间插入元素 if index 0 or index self._size: raise IndexError(索引越界) # 元素数量超出容量时触发扩容机制 if self._size self.capacity(): self.extend_capacity() # 将索引 index 以及之后的元素都向后移动一位 for j in range(self._size - 1, index - 1, -1): self._arr[j 1] self._arr[j] self._arr[index] num # 更新元素数量 self._size 1insert()my_list.py是三种写操作里最容易写错边界的一处值得细看越界条件同样取index self._size即本实现不允许index self._size用insert在“末尾之后”追加会抛异常。这与 Python 内建list.insert的宽松语义允许插入到len(nums)位置超出时自动钳制到末尾并不相同属于教学版简化设计需要追加时请使用add()容量满时先扩容随后执行倒序搬移for j in range(self._size - 1, index - 1, -1)从最后一个有效元素开始逐个把_arr[j]复制到_arr[j 1]。必须倒序遍历——若正序搬移后面的元素会覆盖尚未搬走的元素搬移完成后在index处写入新值_size自增。搬移是线性开销因此中间插入的时间复杂度为 $O(n)$与普通数组完全一致。值得注意的是可视化版 md 中的insert()省略了“容量已满”判断而直接扩容属于上文中提到的精简差异之一。6.3 删除元素 remove()def remove(self, index: int) - int: 删除元素 if index 0 or index self._size: raise IndexError(索引越界) num self._arr[index] # 将索引 index 之后的元素都向前移动一位 for j in range(index, self._size - 1): self._arr[j] self._arr[j 1] # 更新元素数量 self._size - 1 # 返回被删除的元素 return numremove()my_list.py与insert互为镜像越界校验后先暂存待删元素num它作为返回值执行正序前移for j in range(index, self._size - 1)把后面的每个元素向左挪一位覆盖被删位置_size自减。这里有一个值得注意的实现细节删除只缩减_size并不会缩减底层数组容量也不会把“旧值”清零。最末位的残留值是冗余数据因为所有操作都以_size为边界它永远不会再被读到。换言之本实现“只扩容、不缩容”若需在删除大量元素后回收内存需要另行设计缩容逻辑。remove()返回被删元素这与内建list.pop(index)的行为一致。七、扩容机制 extend_capacity 深度拆解扩容是整个动态数组的“发动机”其实现my_list.py只有三行def extend_capacity(self): 列表扩容 # 新建一个长度为原数组 _extend_ratio 倍的新数组并将原数组复制到新数组 self._arr self._arr [0] * self.capacity() * (self._extend_ratio - 1) # 更新列表容量 self._capacity len(self._arr)拆开看它的工作过程[0] * capacity() * (_extend_ratio - 1)先构造一段“新增的占位区”。以容量 10、扩容倍数 2 为例即追加10 * (2 - 1) 10个 0self._arr self._arr [...]把旧数组与新占位区拼成一个新列表等价于“申请 2 倍新空间并把旧元素逐个复制过去”self._capacity len(self._arr)让容量属性与实际底层数组长度保持一致。这种利用列表运算符完成的扩容是 Python 版本特有的“偷懒”写法——底层仍是分配新空间 整体搬迁旧数据代价为 $O(n)$。同样的思想在 C 语言版 codes/c/chapter_array_and_linkedlist/my_list.c 中被显式地表达了出来先malloc一块capacity * extendRatio的新内存逐元素拷贝free旧数组再更新指针与容量。对比两个语言版本可以看出Python 依靠内置的列表拼接语法隐藏了内存管理细节而 C 版本必须手工完成分配、拷贝、释放的全过程——这也解释了为什么 C 没有内置动态数组需要自行实现MyList这类结构原书在list.c中注明的“C 未提供内置动态数组”。扩容的触发时机有两处入口add()与insert()在发现_size _capacity时都会调用extend_capacity()。由于每次扩容都把容量翻倍扩容次数是 $O(\log n)$ 量级把各次扩容的整体搬迁成本摊到每一次add()上就得到了动态数组“尾部添加均摊 $O(1)$”的经典结论——这正是动态数组相比固定长度数组的根本优势。八、完整类源码与驱动用例实测把上述方法汇总加上可视化版中省略的to_array()辅助方法就得到可独立运行的完整实现my_list.py 增加了用于打印的to_arrayclass MyList: 列表类 def __init__(self): 构造方法 self._capacity: int 10 # 列表容量 self._arr: list[int] [0] * self._capacity # 数组存储列表元素 self._size: int 0 # 列表长度当前元素数量 self._extend_ratio: int 2 # 每次列表扩容的倍数 def size(self) - int: 获取列表长度当前元素数量 return self._size def capacity(self) - int: 获取列表容量 return self._capacity def get(self, index: int) - int: 访问元素 # 索引如果越界则抛出异常下同 if index 0 or index self._size: raise IndexError(索引越界) return self._arr[index] def set(self, num: int, index: int): 更新元素 if index 0 or index self._size: raise IndexError(索引越界) self._arr[index] num def add(self, num: int): 在尾部添加元素 # 元素数量超出容量时触发扩容机制 if self.size() self.capacity(): self.extend_capacity() self._arr[self._size] num self._size 1 def insert(self, num: int, index: int): 在中间插入元素 if index 0 or index self._size: raise IndexError(索引越界) # 元素数量超出容量时触发扩容机制 if self._size self.capacity(): self.extend_capacity() # 将索引 index 以及之后的元素都向后移动一位 for j in range(self._size - 1, index - 1, -1): self._arr[j 1] self._arr[j] self._arr[index] num # 更新元素数量 self._size 1 def remove(self, index: int) - int: 删除元素 if index 0 or index self._size: raise IndexError(索引越界) num self._arr[index] # 将索引 index 之后的元素都向前移动一位 for j in range(index, self._size - 1): self._arr[j] self._arr[j 1] # 更新元素数量 self._size - 1 # 返回被删除的元素 return num def extend_capacity(self): 列表扩容 # 新建一个长度为原数组 _extend_ratio 倍的新数组并将原数组复制到新数组 self._arr self._arr [0] * self.capacity() * (self._extend_ratio - 1) # 更新列表容量 self._capacity len(self._arr) def to_array(self) - list[int]: 返回有效长度的列表 return self._arr[: self._size]配套的 Driver Codemy_list.py按“初始化 → 尾部添加 → 中间插入 → 删除 → 访问 → 更新 → 扩容”的顺序演示了全部操作。其中最后一个for i in range(10): nums.add(i)专门用来触发扩容。在仓库根目录执行python3 codes/python/chapter_array_and_linkedlist/my_list.py可以拿到如下实测输出运行于本仓库当前代码Python 3列表 nums [1, 3, 2, 5, 4] 容量 10 长度 5 在索引 3 处插入数字 6 得到 nums [1, 3, 2, 6, 5, 4] 删除索引 3 处的元素得到 nums [1, 3, 2, 5, 4] 访问索引 1 处的元素得到 num 3 将索引 1 处的元素更新为 0 得到 nums [1, 0, 2, 5, 4] 扩容后的列表 [1, 0, 2, 5, 4, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 容量 20 长度 15逐行对照可视化文档的驱动代码可以还原出每一步的内部状态步骤操作数组内容长度容量关键事件1MyList()[]010预分配 10 个槽位2依次add(1/3/2/5/4)[1, 3, 2, 5, 4]510尾部添加均摊 $O(1)$3insert(6, index3)[1, 3, 2, 6, 5, 4]610索引 3 及之后元素整体后移一位4remove(3)[1, 3, 2, 5, 4]510返回被删元素 65num get(1)———返回36set(0, 1)[1, 0, 2, 5, 4]510把索引 1 更新为 07再add(0..9)见上最后一行1520在i 5时容量用尽触发扩容 10 → 20第 7 步正是扩容机制的现场演示当第 6 个追加元素到达时i 5_size恰好等于_capacity 10add()检测到容量已满便调用extend_capacity()把底层数组翻倍为 20 个槽位随后继续完成剩余 4 次添加最终长度 15、容量 20、闲置槽位 5 个。这也验证了上文对扩容触发时机与“只扩不缩”行为的分析。九、设计取舍与边界行为小结从逐行拆解中可以提炼出这套教学实现的设计取向与边界约定初始容量与扩容倍数都是可调参数。仓库代码将初始容量定为 10、扩容倍数定为 2。现实中标准库对这两个参数的选择更为考究涉及内存利用率与搬迁次数之间的平衡这里选用小容量、2 倍增长的组合是为了让读者在可视化演示中尽快观察到扩容的发生越界判定统一使用index 0 or index _size。对空列表调用get/set/remove/insert均会抛出IndexError因为此时任何索引都不满足0 index 0insert不允许把元素插到逻辑末尾之后即index _size非法需要追加请走add()。这与内建list.insert的宽松语义存在差异是刻意简化后的边界行为删除操作只减_size不缩容。底层数组一旦扩容到 20 便保持该大小即使之后不断remove容量也不会自动回落可视化版与运行版的细微差异已在第二节说明md 中的版本省略了to_array()、打印语句和部分注释且insert()直接调用扩容。因此严格地说md 版是“演示剪辑版”本文第八节提供的完整源码才是与仓库 codes/python/chapter_array_and_linkedlist/my_list.py 完全一致的运行版本。若想用另一门语言加深理解可以对照 C 语言版 codes/c/chapter_array_and_linkedlist/my_list.c它用struct封装同样的四个字段arr/capacity/size/extendRatio用assert代替IndexError做越界保护用malloc/free手工完成扩容中的内存生命周期管理并把删除方法命名为removeItem避免与stdio.h中的remove()冲突。同一份设计在不同语言中的落地方案差异本身就是很好的对比学习素材。十、复杂度一览与延伸阅读把本节所有方法汇总可得完整的复杂度画像方法功能时间复杂度size()/capacity()查询长度 / 容量$O(1)$get(index)/set(num, index)随机访问 / 更新$O(1)$add(num)尾部添加均摊 $O(1)$单次扩容时 $O(n)$insert(num, index)中间插入$O(n)$元素搬移remove(index)删除并返回元素$O(n)$元素搬移extend_capacity()扩容$O(n)$新建数组 整体复制这套实现回答了一个关键问题Python 内建list为什么能“随便 append 而不必担心容量”。其答案是“动态数组 懒扩容”的设计组合——容量记录、长度记录、翻倍扩容这三板斧正是所有动态数组类容器共享的底层骨架。想继续深入可在仓库中结合以下文件系统学习“数组 ↔ 链表 ↔ 列表”的知识闭环可视化原始页codes/pythontutor/chapter_array_and_linkedlist/my_list.md含俄语副本 ru/codes/pythontutor/chapter_array_and_linkedlist/my_list.md完整 Python 源码codes/python/chapter_array_and_linkedlist/my_list.py 及俄语版 ru/codes/python/chapter_array_and_linkedlist/my_list.pyC 语言对照实现codes/c/chapter_array_and_linkedlist/my_list.c书本正文与背景知识docs/chapter_array_and_linkedlist/list.md、docs/chapter_array_and_linkedlist/array.md本章其余篇幅在《Hello 算法》的数组与链表章节中还有对静态数组、链表及内存布局的完整讲解可作为动态数组的前置知识一并阅读。下次当你写下nums.append(x)时不妨想想背后那个默默“翻倍扩容”的extend_capacity——这就是动态数组的魔法所在。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考