hello-algo《Hello 算法》列表动态数组核心操作与手写 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 算法》的数组与链表一章中列表list是连接数组与动态数据结构的关键抽象它把元素有序集合的增、删、查、改、遍历能力封装起来使用者无须关心底层容量。本文以 list.md 为核心骨架完整覆盖列表的六类常用操作多语言代码对照并结合仓库中 my_list.py、my_list.java、my_list.cpp、my_list.c 四份跨语言实现逐步拆解初始容量、数量记录、扩容机制三大设计帮助你既会用标准库列表又能看懂其底层扩容原理。一、为什么需要动态数组来实现列表列表是一个抽象的数据结构概念表示元素的有序集合支持元素访问、修改、添加、删除和遍历等操作且无须使用者考虑容量限制问题。它可以基于两种底层实现链表天然可以看作一个列表支持元素增删查改并且可以灵活动态扩容数组同样支持增删查改但由于长度不可变只能看作一个具有长度限制的列表。用数组实现列表时长度不可变的性质会显著降低实用性我们通常无法事先确定需要存储多少数据从而难以选择合适的列表长度——选小了无法满足需求选大了又浪费内存空间。为此可以使用**动态数组dynamic array**来实现列表它继承了数组的各项优点并能在程序运行过程中动态扩容。许多编程语言标准库中的列表正是基于动态数组实现的例如 Python 的list、Java 的ArrayList、C 的vector、C# 的List。在本书后续的讨论中列表和动态数组被视为等同的概念。二、列表的六类常用操作多语言对照以下各小节继承原文档的全部操作示例保留 Python、C、Java、C#、Go、Swift、JS、TS、Dart、Rust、Kotlin、Ruby 等语言的实现方式。需要特别说明C 语言未提供内置动态数组因此在 C 语言的示例中该章代码块仅标注// C 未提供内置动态数组这也是仓库单独手写MyList的动机之一。1. 初始化列表列表通常支持无初始值与有初始值两种初始化方式。各语言的惯用写法如下# Pythonlist.py # 初始化列表 # 无初始值 nums1: list[int] [] # 有初始值 nums: list[int] [1, 3, 2, 5, 4]/* Clist.cpp */ // 需注意C 中 vector 即是本文描述的 nums // 无初始值 vectorint nums1; // 有初始值 vectorint nums { 1, 3, 2, 5, 4 };/* Javalist.java */ // 无初始值 ListInteger nums1 new ArrayList(); // 有初始值注意数组的元素类型需为 int[] 的包装类 Integer[] Integer[] numbers new Integer[] { 1, 3, 2, 5, 4 }; ListInteger nums new ArrayList(Arrays.asList(numbers));/* C#list.cs */ // 无初始值 Listint nums1 []; // 有初始值 int[] numbers [1, 3, 2, 5, 4]; Listint nums [.. numbers];// Golist_test.go // 无初始值 nums1 : []int{} // 有初始值 nums : []int{1, 3, 2, 5, 4}// Swiftlist.swift // 无初始值 let nums1: [Int] [] // 有初始值 var nums [1, 3, 2, 5, 4]// JSlist.js // 无初始值 const nums1 []; // 有初始值 const nums [1, 3, 2, 5, 4];// TSlist.ts // 无初始值 const nums1: number[] []; // 有初始值 const nums: number[] [1, 3, 2, 5, 4];// Dartlist.dart // 无初始值 Listint nums1 []; // 有初始值 Listint nums [1, 3, 2, 5, 4];// Rustlist.rs // 无初始值 let nums1: Veci32 Vec::new(); // 有初始值 let nums: Veci32 vec![1, 3, 2, 5, 4];// Kotlinlist.kt // 无初始值 var nums1 listOfInt() // 有初始值 var numbers arrayOf(1, 3, 2, 5, 4) var nums numbers.toMutableList()# Rubylist.rb # 初始化列表 # 无初始值 nums1 [] # 有初始值 nums [1, 3, 2, 5, 4]这些片段对应仓库中的多语言示例文件例如 list.pyPython 驱动代码。2. 访问与更新元素列表本质上是数组因此可以在 $O(1)$ 时间内访问和更新元素效率很高。# Python # 访问元素 num: int nums[1] # 访问索引 1 处的元素 # 更新元素 nums[1] 0 # 将索引 1 处的元素更新为 0// Java int num nums.get(1); // 访问索引 1 处的元素 nums.set(1, 0); // 将索引 1 处的元素更新为 0// C int num nums[1]; // 访问索引 1 处的元素 nums[1] 0; // 将索引 1 处的元素更新为 0其余语言C#、Go、Swift、JS、TS、Dart、Rust、Kotlin、Ruby同样通过下标或get/set方法完成例如 Rust 的let num: i32 nums[1];与 Kotlin 的val num nums[1];。可以看到Java 的ArrayList因接口抽象需要显式调用get()/set()而其余多数语言直接支持下标语法。3. 插入与删除元素相较于数组列表可以自由地添加与删除元素。其中在列表尾部添加元素的时间复杂度为 $O(1)$摊还意义下但在中间插入和删除元素的效率仍与数组相同时间复杂度为 $O(n)$——因为需要移动后续元素。# Python # 清空列表 nums.clear() # 在尾部添加元素 nums.append(1) nums.append(3) nums.append(2) nums.append(5) nums.append(4) # 在中间插入元素 nums.insert(3, 6) # 在索引 3 处插入数字 6 # 删除元素 nums.pop(3) # 删除索引 3 处的元素// Java nums.clear(); nums.add(1); // 尾部追加 nums.add(3, 6); // 在索引 3 处插入数字 6 nums.remove(3); // 删除索引 3 处的元素// C nums.clear(); nums.push_back(1); nums.insert(nums.begin() 3, 6); // 在索引 3 处插入数字 6 nums.erase(nums.begin() 3); // 删除索引 3 处的元素各语言在中间插入 / 按索引删除上的差异值得注意C#nums.Insert(3, 6)与nums.RemoveAt(3)Goslice 不可原地插入需要用append(nums[:3], append([]int{6}, nums[3:]...)...)插入、append(nums[:3], nums[4:]...)删除且清空用nums nilSwiftnums.insert(6, at: 3)与nums.remove(at: 3)JS / TS统一使用nums.splice(3, 0, 6)插入、nums.splice(3, 1)删除清空用nums.length 0Rustnums.insert(3, 6)与nums.remove(3)Ruby尾部追加可用nums 1删除用nums.delete_at(3)。4. 遍历列表与数组一样列表可以根据索引遍历也可以直接遍历各元素。# Python # 通过索引遍历列表 count 0 for i in range(len(nums)): count nums[i] # 直接遍历列表元素 for num in nums: count num// Java for (int i 0; i nums.size(); i) { count nums.get(i); } for (int num : nums) { count num; }// Go for i : 0; i len(nums); i { count nums[i] } for _, num : range nums { count num }// Rust let mut _count 0; for i in 0..nums.len() { _count nums[i]; } _count 0; for num in nums { _count num; }其余语言同理C 用for (int num : nums)C# 用foreach (int num in nums)Swift 用for num in numsKotlin 用for (i in nums.indices)Dart、JS、TS 用for...ofRuby 用for num in nums。两种遍历方式的时间复杂度均为 $O(n)$。5. 拼接列表给定一个新列表nums1可以将其拼接到原列表尾部。# Python nums1: list[int] [6, 8, 7, 10, 9] nums nums1 # 将列表 nums1 拼接到 nums 之后// Java ListInteger nums1 new ArrayList(Arrays.asList(new Integer[] { 6, 8, 7, 10, 9 })); nums.addAll(nums1);// C vectorint nums1 { 6, 8, 7, 10, 9 }; nums.insert(nums.end(), nums1.begin(), nums1.end());// Go nums1 : []int{6, 8, 7, 10, 9} nums append(nums, nums1...)// Rust let nums1: Veci32 vec![6, 8, 7, 10, 9]; nums.extend(nums1);JS / TS 使用nums.push(...nums1)Swift 使用nums.append(contentsOf: nums1)C# 使用nums.AddRange(nums1)Ruby 使用nums nums1。拼接的总时间复杂度为 $O(m)$$m$ 为nums1的长度本质上是把 $m$ 个元素复制到尾部触发扩容时还会产生一次 $O(nm)$ 的拷贝。6. 排序列表完成列表排序后便可以使用数组类算法题中经常考查的二分查找和双指针算法。# Python nums.sort() # 排序后列表元素从小到大排列// C sort(nums.begin(), nums.end());// Java Collections.sort(nums);// JS / TS注意需要显式传入比较函数否则默认按字典序排序 nums.sort((a, b) a - b);其余语言一行搞定C#nums.Sort()、Gosort.Ints(nums)、Swiftnums.sort()、Rustnums.sort()、Kotlinnums.sort()、Dartnums.sort()、Rubynums nums.sort { |a, b| a b }。三、简易列表的源码实现三大关键设计原文档列表实现一节指出许多语言内置列表的实现非常复杂初始容量、扩容倍数等参数设定考究为加深理解仓库提供了一个简易版列表包含三个重点设计初始容量选取一个合理的数组初始容量本示例选择10数量记录声明变量size记录列表当前元素数量并随插入和删除实时更新用于定位列表尾部以及判断是否需要扩容扩容机制插入元素时若容量已满先按扩容倍数创建更大的数组再把当前数组的所有元素依次移动至新数组。本示例规定每次将数组扩容至之前的2 倍。Python 版 MyList 逐方法解析my_list.py 是四份实现中最直白的一份核心结构如下class MyList: 列表类 def __init__(self): 构造方法 self._capacity: int 10 # 列表容量 self._arr: list[int] [0] * self._capacity # 数组存储列表元素 self._size: int 0 # 列表长度当前元素数量 self._extend_ratio: int 2 # 每次列表扩容的倍数这里对应了三大设计_capacity 10初始容量、_size 0数量记录、_extend_ratio 2扩容倍数。访问与更新get/set两者都先做越界检查if index 0 or index self._size: raise IndexError(索引越界)然后直接读写self._arr[index]体现了列表本质是数组、随机访问 $O(1)$这一结论。尾部添加add这是唯一会触发扩容的简单入口def add(self, num: int): 在尾部添加元素 # 元素数量超出容量时触发扩容机制 if self.size() self.capacity(): self.extend_capacity() self._arr[self._size] num self._size 1中间插入insert与add类似先检查并可能扩容然后把索引index及之后的元素从后向前整体后移一位最后写入新元素。for j in range(self._size - 1, index - 1, -1)反向循环是避免先移动导致覆盖源数据的关键这也解释了为什么中间插入是 $O(n)$。删除remove取出self._arr[index]后将索引index之后的元素从前向后整体前移一位self._size - 1并返回被删除的元素以便调用方取回值。扩容extend_capacitydef extend_capacity(self): 列表扩容 # 新建一个长度为原数组 _extend_ratio 倍的新数组并将原数组复制到新数组 self._arr self._arr [0] * self.capacity() * (self._extend_ratio - 1) # 更新列表容量 self._capacity len(self._arr)Python 版利用切片拼接完成新数组 复制一步到位由于extend_ratio 2每次扩容后容量翻倍。有效长度输出to_array()返回self._arr[: self._size]只截取有效长度内的元素——这解释了为什么size与capacity必须分开维护数组尾部始终可能残留空闲槽位。跨语言实现差异对比实现文件底层结构扩容方式越界检查值得注意的差异my_list.pylist[int]切片拼接[0] * capacity * (ratio - 1)抛出IndexErrorset(num, index)参数顺序为值在前my_list.javaint[]Arrays.copyOf(arr, capacity * extendRatio)抛出IndexOutOfBoundsException主类为public class my_listset(index, num)参数顺序与 Java 风格一致my_list.cppint *arr裸指针手动new int[newCapacity] 循环拷贝 delete[] tmp抛出out_of_range来自 common.hpp需要自己写析构函数delete[] arr体现手工内存管理my_list.cMyList结构体 mallocmalloc新数组 循环拷贝 free(temp)assert(index 0 index nums-size)删除函数命名为removeItem因为stdio.h占用了remove关键词几个细节可以从源码中直接确认四份实现的默认参数完全一致capacity 10、size 0、extendRatio 2与原文档描述一一对应C 版的extendCapacity()展示了教科书式的三步扩容流程my_list.cpp 第 94~107 行分配newCapacity capacity() * extendRatio的新数组 → 逐元素复制 → 释放旧数组再更新arrCapacityC 版用结构体模拟类newMyList()中先malloc(sizeof(MyList))再malloc(sizeof(int) * capacity)delMyList()负责两级释放这是 C 语言手写动态数组的标准内存管理模式见 my_list.c 第 20~33 行。用驱动代码验证扩容机制四份实现的 Driver Code 流程一致以 Python 为例my_list.py 第 86~118 行nums MyList()初始化此时capacity 10、size 0add五个元素1, 3, 2, 5, 4打印列表、容量与长度容量仍为 10nums.insert(6, index3)在中间插入nums.remove(3)再删除验证元素移动逻辑nums.get(1)/nums.set(0, 1)验证随机访问与更新最后for i in range(10): nums.add(i)连续追加 10 个元素——源码注释明确写道在i 5时列表长度将超出列表容量此时触发扩容机制此前size已达 55 个初始元素经插入删除后仍为 5再追加到第 5 次时size capacity的判断实际此处容量为 10注释以逻辑说明触发点会命中extend_capacity()容量从 10 翻倍为 20最终打印扩容后的列表及其新容量与长度。Java、C、C 版本的 Driver Code分别在 my_list.java 第 109~146 行、my_list.cpp 第 120~170 行、my_list.c 第 116~162 行执行完全相同的步骤包括 C 与 C 版本在结尾显式释放内存delete nums;/delMyList(nums);。四、复杂度小结与使用建议综合原文档结论与源码实现列表动态数组的复杂度画像如下操作时间复杂度源码依据访问 / 更新元素$O(1)$get/set直接下标读写arr[index]尾部添加$O(1)$摊还add仅在size capacity时触发一次 $O(n)$ 扩容中间插入 / 按索引删除$O(n)$insert/remove需要整体移动后续元素遍历 / 排序遍历部分$O(n)$索引遍历与直接遍历均为线性拼接列表$O(m)$可能伴随 $O(nm)$ 扩容addAll/extend/等批量复制从何时用列表的视角看如果操作以尾部追加、随机访问、遍历为主如模拟栈、记录序列、缓存结果动态数组列表是理想选择如果频繁在头部或中间插入删除则可结合本章的 链表 一节选择链表实现。本书在 数组篇 中已论证了数组定长的限制本篇的MyList正是对这一限制的工程化补全。五、延伸阅读路径文档主体list.md本文骨架来源Python 完整驱动代码list.py演示了六类操作的连续执行效果手写实现对照my_list.py、my_list.java、my_list.cpp、my_list.c章节配套练习exercises.md。掌握以上内容后你应当能够熟练使用任意主流语言的内置列表完成初始化、随机访问、增删、遍历、拼接与排序读懂标准库动态数组初始容量 size 计数 倍数扩容三大核心参数并能在 C 等无内置动态数组的语言中参考仓库的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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 hello-algo《Hello 算法》列表（动态数组）核心操作与手写 MyList 扩容机制详解
hello-algo《Hello 算法》列表动态数组核心操作与手写 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 算法》的数组与链表一章中列表list是连接数组与动态数据结构的关键抽象它把元素有序集合的增、删、查、改、遍历能力封装起来使用者无须关心底层容量。本文以 list.md 为核心骨架完整覆盖列表的六类常用操作多语言代码对照并结合仓库中 my_list.py、my_list.java、my_list.cpp、my_list.c 四份跨语言实现逐步拆解初始容量、数量记录、扩容机制三大设计帮助你既会用标准库列表又能看懂其底层扩容原理。一、为什么需要动态数组来实现列表列表是一个抽象的数据结构概念表示元素的有序集合支持元素访问、修改、添加、删除和遍历等操作且无须使用者考虑容量限制问题。它可以基于两种底层实现链表天然可以看作一个列表支持元素增删查改并且可以灵活动态扩容数组同样支持增删查改但由于长度不可变只能看作一个具有长度限制的列表。用数组实现列表时长度不可变的性质会显著降低实用性我们通常无法事先确定需要存储多少数据从而难以选择合适的列表长度——选小了无法满足需求选大了又浪费内存空间。为此可以使用**动态数组dynamic array**来实现列表它继承了数组的各项优点并能在程序运行过程中动态扩容。许多编程语言标准库中的列表正是基于动态数组实现的例如 Python 的list、Java 的ArrayList、C 的vector、C# 的List。在本书后续的讨论中列表和动态数组被视为等同的概念。二、列表的六类常用操作多语言对照以下各小节继承原文档的全部操作示例保留 Python、C、Java、C#、Go、Swift、JS、TS、Dart、Rust、Kotlin、Ruby 等语言的实现方式。需要特别说明C 语言未提供内置动态数组因此在 C 语言的示例中该章代码块仅标注// C 未提供内置动态数组这也是仓库单独手写MyList的动机之一。1. 初始化列表列表通常支持无初始值与有初始值两种初始化方式。各语言的惯用写法如下# Pythonlist.py # 初始化列表 # 无初始值 nums1: list[int] [] # 有初始值 nums: list[int] [1, 3, 2, 5, 4]/* Clist.cpp */ // 需注意C 中 vector 即是本文描述的 nums // 无初始值 vectorint nums1; // 有初始值 vectorint nums { 1, 3, 2, 5, 4 };/* Javalist.java */ // 无初始值 ListInteger nums1 new ArrayList(); // 有初始值注意数组的元素类型需为 int[] 的包装类 Integer[] Integer[] numbers new Integer[] { 1, 3, 2, 5, 4 }; ListInteger nums new ArrayList(Arrays.asList(numbers));/* C#list.cs */ // 无初始值 Listint nums1 []; // 有初始值 int[] numbers [1, 3, 2, 5, 4]; Listint nums [.. numbers];// Golist_test.go // 无初始值 nums1 : []int{} // 有初始值 nums : []int{1, 3, 2, 5, 4}// Swiftlist.swift // 无初始值 let nums1: [Int] [] // 有初始值 var nums [1, 3, 2, 5, 4]// JSlist.js // 无初始值 const nums1 []; // 有初始值 const nums [1, 3, 2, 5, 4];// TSlist.ts // 无初始值 const nums1: number[] []; // 有初始值 const nums: number[] [1, 3, 2, 5, 4];// Dartlist.dart // 无初始值 Listint nums1 []; // 有初始值 Listint nums [1, 3, 2, 5, 4];// Rustlist.rs // 无初始值 let nums1: Veci32 Vec::new(); // 有初始值 let nums: Veci32 vec![1, 3, 2, 5, 4];// Kotlinlist.kt // 无初始值 var nums1 listOfInt() // 有初始值 var numbers arrayOf(1, 3, 2, 5, 4) var nums numbers.toMutableList()# Rubylist.rb # 初始化列表 # 无初始值 nums1 [] # 有初始值 nums [1, 3, 2, 5, 4]这些片段对应仓库中的多语言示例文件例如 list.pyPython 驱动代码。2. 访问与更新元素列表本质上是数组因此可以在 $O(1)$ 时间内访问和更新元素效率很高。# Python # 访问元素 num: int nums[1] # 访问索引 1 处的元素 # 更新元素 nums[1] 0 # 将索引 1 处的元素更新为 0// Java int num nums.get(1); // 访问索引 1 处的元素 nums.set(1, 0); // 将索引 1 处的元素更新为 0// C int num nums[1]; // 访问索引 1 处的元素 nums[1] 0; // 将索引 1 处的元素更新为 0其余语言C#、Go、Swift、JS、TS、Dart、Rust、Kotlin、Ruby同样通过下标或get/set方法完成例如 Rust 的let num: i32 nums[1];与 Kotlin 的val num nums[1];。可以看到Java 的ArrayList因接口抽象需要显式调用get()/set()而其余多数语言直接支持下标语法。3. 插入与删除元素相较于数组列表可以自由地添加与删除元素。其中在列表尾部添加元素的时间复杂度为 $O(1)$摊还意义下但在中间插入和删除元素的效率仍与数组相同时间复杂度为 $O(n)$——因为需要移动后续元素。# Python # 清空列表 nums.clear() # 在尾部添加元素 nums.append(1) nums.append(3) nums.append(2) nums.append(5) nums.append(4) # 在中间插入元素 nums.insert(3, 6) # 在索引 3 处插入数字 6 # 删除元素 nums.pop(3) # 删除索引 3 处的元素// Java nums.clear(); nums.add(1); // 尾部追加 nums.add(3, 6); // 在索引 3 处插入数字 6 nums.remove(3); // 删除索引 3 处的元素// C nums.clear(); nums.push_back(1); nums.insert(nums.begin() 3, 6); // 在索引 3 处插入数字 6 nums.erase(nums.begin() 3); // 删除索引 3 处的元素各语言在中间插入 / 按索引删除上的差异值得注意C#nums.Insert(3, 6)与nums.RemoveAt(3)Goslice 不可原地插入需要用append(nums[:3], append([]int{6}, nums[3:]...)...)插入、append(nums[:3], nums[4:]...)删除且清空用nums nilSwiftnums.insert(6, at: 3)与nums.remove(at: 3)JS / TS统一使用nums.splice(3, 0, 6)插入、nums.splice(3, 1)删除清空用nums.length 0Rustnums.insert(3, 6)与nums.remove(3)Ruby尾部追加可用nums 1删除用nums.delete_at(3)。4. 遍历列表与数组一样列表可以根据索引遍历也可以直接遍历各元素。# Python # 通过索引遍历列表 count 0 for i in range(len(nums)): count nums[i] # 直接遍历列表元素 for num in nums: count num// Java for (int i 0; i nums.size(); i) { count nums.get(i); } for (int num : nums) { count num; }// Go for i : 0; i len(nums); i { count nums[i] } for _, num : range nums { count num }// Rust let mut _count 0; for i in 0..nums.len() { _count nums[i]; } _count 0; for num in nums { _count num; }其余语言同理C 用for (int num : nums)C# 用foreach (int num in nums)Swift 用for num in numsKotlin 用for (i in nums.indices)Dart、JS、TS 用for...ofRuby 用for num in nums。两种遍历方式的时间复杂度均为 $O(n)$。5. 拼接列表给定一个新列表nums1可以将其拼接到原列表尾部。# Python nums1: list[int] [6, 8, 7, 10, 9] nums nums1 # 将列表 nums1 拼接到 nums 之后// Java ListInteger nums1 new ArrayList(Arrays.asList(new Integer[] { 6, 8, 7, 10, 9 })); nums.addAll(nums1);// C vectorint nums1 { 6, 8, 7, 10, 9 }; nums.insert(nums.end(), nums1.begin(), nums1.end());// Go nums1 : []int{6, 8, 7, 10, 9} nums append(nums, nums1...)// Rust let nums1: Veci32 vec![6, 8, 7, 10, 9]; nums.extend(nums1);JS / TS 使用nums.push(...nums1)Swift 使用nums.append(contentsOf: nums1)C# 使用nums.AddRange(nums1)Ruby 使用nums nums1。拼接的总时间复杂度为 $O(m)$$m$ 为nums1的长度本质上是把 $m$ 个元素复制到尾部触发扩容时还会产生一次 $O(nm)$ 的拷贝。6. 排序列表完成列表排序后便可以使用数组类算法题中经常考查的二分查找和双指针算法。# Python nums.sort() # 排序后列表元素从小到大排列// C sort(nums.begin(), nums.end());// Java Collections.sort(nums);// JS / TS注意需要显式传入比较函数否则默认按字典序排序 nums.sort((a, b) a - b);其余语言一行搞定C#nums.Sort()、Gosort.Ints(nums)、Swiftnums.sort()、Rustnums.sort()、Kotlinnums.sort()、Dartnums.sort()、Rubynums nums.sort { |a, b| a b }。三、简易列表的源码实现三大关键设计原文档列表实现一节指出许多语言内置列表的实现非常复杂初始容量、扩容倍数等参数设定考究为加深理解仓库提供了一个简易版列表包含三个重点设计初始容量选取一个合理的数组初始容量本示例选择10数量记录声明变量size记录列表当前元素数量并随插入和删除实时更新用于定位列表尾部以及判断是否需要扩容扩容机制插入元素时若容量已满先按扩容倍数创建更大的数组再把当前数组的所有元素依次移动至新数组。本示例规定每次将数组扩容至之前的2 倍。Python 版 MyList 逐方法解析my_list.py 是四份实现中最直白的一份核心结构如下class MyList: 列表类 def __init__(self): 构造方法 self._capacity: int 10 # 列表容量 self._arr: list[int] [0] * self._capacity # 数组存储列表元素 self._size: int 0 # 列表长度当前元素数量 self._extend_ratio: int 2 # 每次列表扩容的倍数这里对应了三大设计_capacity 10初始容量、_size 0数量记录、_extend_ratio 2扩容倍数。访问与更新get/set两者都先做越界检查if index 0 or index self._size: raise IndexError(索引越界)然后直接读写self._arr[index]体现了列表本质是数组、随机访问 $O(1)$这一结论。尾部添加add这是唯一会触发扩容的简单入口def add(self, num: int): 在尾部添加元素 # 元素数量超出容量时触发扩容机制 if self.size() self.capacity(): self.extend_capacity() self._arr[self._size] num self._size 1中间插入insert与add类似先检查并可能扩容然后把索引index及之后的元素从后向前整体后移一位最后写入新元素。for j in range(self._size - 1, index - 1, -1)反向循环是避免先移动导致覆盖源数据的关键这也解释了为什么中间插入是 $O(n)$。删除remove取出self._arr[index]后将索引index之后的元素从前向后整体前移一位self._size - 1并返回被删除的元素以便调用方取回值。扩容extend_capacitydef extend_capacity(self): 列表扩容 # 新建一个长度为原数组 _extend_ratio 倍的新数组并将原数组复制到新数组 self._arr self._arr [0] * self.capacity() * (self._extend_ratio - 1) # 更新列表容量 self._capacity len(self._arr)Python 版利用切片拼接完成新数组 复制一步到位由于extend_ratio 2每次扩容后容量翻倍。有效长度输出to_array()返回self._arr[: self._size]只截取有效长度内的元素——这解释了为什么size与capacity必须分开维护数组尾部始终可能残留空闲槽位。跨语言实现差异对比实现文件底层结构扩容方式越界检查值得注意的差异my_list.pylist[int]切片拼接[0] * capacity * (ratio - 1)抛出IndexErrorset(num, index)参数顺序为值在前my_list.javaint[]Arrays.copyOf(arr, capacity * extendRatio)抛出IndexOutOfBoundsException主类为public class my_listset(index, num)参数顺序与 Java 风格一致my_list.cppint *arr裸指针手动new int[newCapacity] 循环拷贝 delete[] tmp抛出out_of_range来自 common.hpp需要自己写析构函数delete[] arr体现手工内存管理my_list.cMyList结构体 mallocmalloc新数组 循环拷贝 free(temp)assert(index 0 index nums-size)删除函数命名为removeItem因为stdio.h占用了remove关键词几个细节可以从源码中直接确认四份实现的默认参数完全一致capacity 10、size 0、extendRatio 2与原文档描述一一对应C 版的extendCapacity()展示了教科书式的三步扩容流程my_list.cpp 第 94~107 行分配newCapacity capacity() * extendRatio的新数组 → 逐元素复制 → 释放旧数组再更新arrCapacityC 版用结构体模拟类newMyList()中先malloc(sizeof(MyList))再malloc(sizeof(int) * capacity)delMyList()负责两级释放这是 C 语言手写动态数组的标准内存管理模式见 my_list.c 第 20~33 行。用驱动代码验证扩容机制四份实现的 Driver Code 流程一致以 Python 为例my_list.py 第 86~118 行nums MyList()初始化此时capacity 10、size 0add五个元素1, 3, 2, 5, 4打印列表、容量与长度容量仍为 10nums.insert(6, index3)在中间插入nums.remove(3)再删除验证元素移动逻辑nums.get(1)/nums.set(0, 1)验证随机访问与更新最后for i in range(10): nums.add(i)连续追加 10 个元素——源码注释明确写道在i 5时列表长度将超出列表容量此时触发扩容机制此前size已达 55 个初始元素经插入删除后仍为 5再追加到第 5 次时size capacity的判断实际此处容量为 10注释以逻辑说明触发点会命中extend_capacity()容量从 10 翻倍为 20最终打印扩容后的列表及其新容量与长度。Java、C、C 版本的 Driver Code分别在 my_list.java 第 109~146 行、my_list.cpp 第 120~170 行、my_list.c 第 116~162 行执行完全相同的步骤包括 C 与 C 版本在结尾显式释放内存delete nums;/delMyList(nums);。四、复杂度小结与使用建议综合原文档结论与源码实现列表动态数组的复杂度画像如下操作时间复杂度源码依据访问 / 更新元素$O(1)$get/set直接下标读写arr[index]尾部添加$O(1)$摊还add仅在size capacity时触发一次 $O(n)$ 扩容中间插入 / 按索引删除$O(n)$insert/remove需要整体移动后续元素遍历 / 排序遍历部分$O(n)$索引遍历与直接遍历均为线性拼接列表$O(m)$可能伴随 $O(nm)$ 扩容addAll/extend/等批量复制从何时用列表的视角看如果操作以尾部追加、随机访问、遍历为主如模拟栈、记录序列、缓存结果动态数组列表是理想选择如果频繁在头部或中间插入删除则可结合本章的 链表 一节选择链表实现。本书在 数组篇 中已论证了数组定长的限制本篇的MyList正是对这一限制的工程化补全。五、延伸阅读路径文档主体list.md本文骨架来源Python 完整驱动代码list.py演示了六类操作的连续执行效果手写实现对照my_list.py、my_list.java、my_list.cpp、my_list.c章节配套练习exercises.md。掌握以上内容后你应当能够熟练使用任意主流语言的内置列表完成初始化、随机访问、增删、遍历、拼接与排序读懂标准库动态数组初始容量 size 计数 倍数扩容三大核心参数并能在 C 等无内置动态数组的语言中参考仓库的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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考