大家好我是专注于技术分享的博主。最近在整理悉尼大学USYDCOMP2123这门“数据结构与算法”课程的学习笔记发现很多同学在入门阶段对核心概念和抽象思维感到困惑。本文将以第一周公开课内容为基础结合我个人的学习与实践经验系统性地梳理数据结构与算法的入门知识。无论你是正在学习这门课程的学生还是希望夯实计算机科学基础的开发者都能从本文中获得从概念理解到代码实践的完整指导。1. 数据结构与算法为什么是程序员的基石在开始学习具体的链表或排序之前我们必须先理解一个根本问题为什么数据结构与算法如此重要简单来说数据结构是数据的组织、管理和存储格式其目的是为了高效地访问和修改数据。你可以把它想象成一个工具箱不同的工具数据结构适合完成不同的任务。而算法则是解决特定问题的一系列清晰指令是操作这些“工具”的具体方法。两者相辅相成共同决定了程序的效率、可读性和可维护性。1.1 从现实问题到抽象模型所有复杂的软件系统其底层都在处理数据。例如社交网络的好友关系如何快速找到共同好友这背后是图Graph数据结构。浏览器的前进后退功能如何实现这依赖于栈Stack的“后进先出”特性。文本编辑器的撤销操作如何记录一系列操作并回退这同样可以用栈或者更复杂的命令模式配合数据结构来实现。数据库索引如何在海量数据中快速检索一条记录这离不开B树、B树、哈希表等高级数据结构。COMP2123这门课的目标就是教会我们如何为具体问题选择最合适的“工具箱”数据结构和“使用说明书”算法。1.2 核心衡量标准时间与空间复杂度评价一个算法好坏不能只看它是否能运行出正确结果。在资源有限的计算机世界里我们需要量化的标准这就是时间复杂度和空间复杂度通常用大O符号Big O notation表示。时间复杂度指算法执行所需的时间随着数据规模n增长而增长的趋势。它关注的是操作次数的增长率而非精确的秒数。空间复杂度指算法执行过程中临时占用的存储空间大小随数据规模增长的趋势。为什么大O表示法如此重要因为它让我们能脱离具体的机器性能在理论层面比较不同算法的效率。例如O(1)的算法效率远高于O(n²)的算法尤其是当n很大时。第一周课程通常会引入这个概念这是分析一切算法的起点。2. 环境准备工欲善其事必先利其器学习数据结构与算法理论理解是关键但动手实践同样不可或缺。一个合适的编程环境能让你更专注于逻辑本身。2.1 语言选择C, C, Java 还是 PythonCOMP2123课程可能使用多种语言教学核心思想是相通的。选择哪种语言实践可以参考以下建议C/C更接近底层能让你深刻理解内存管理指针、引用、数据在内存中的实际布局。这对于理解链表、树等指针密集型数据结构非常有帮助。缺点是语法相对繁琐。Java拥有丰富的内置集合框架如ArrayList, LinkedList, HashMap但同时也封装了底层细节。适合快速实现和验证算法思想并且强类型和面向对象的特性对工程化思维有益。Python语法简洁表达力强可以用更少的代码实现算法逻辑非常适合算法原型设计和面试刷题。但其动态类型和高级抽象可能会掩盖一些底层细节。建议初学者可以从Python或Java开始快速建立信心和理解流程。若想深入理解一定要用C/C重新实现一遍关键数据结构。2.2 开发环境搭建这里以Visual Studio Code (VSCode)配合Python环境为例因为它轻量、跨平台且插件丰富。安装Python访问 python.org 下载并安装最新稳定版。安装时务必勾选“Add Python to PATH”。安装VSCode从官网下载安装。配置VSCode安装官方Python扩展ms-python.python。打开一个空文件夹作为你的项目目录。创建一个新文件例如test.py。验证环境在test.py中输入以下代码并运行右键选择“在终端中运行Python文件”。print(Hello, Data Structures!) arr [3, 1, 4, 1, 5, 9] print(Original array:, arr) arr.sort() print(Sorted array:, arr)如果能看到排序后的数组输出说明环境配置成功。3. 核心数据结构初探数组、链表与抽象数据类型ADT第一周通常会从最基础也是最重要的两个线性数据结构开始数组Array和链表Linked List。理解它们的区别是理解后续所有数据结构的基础。3.1 数组连续空间的优与劣数组是一种在连续内存空间中存储相同类型数据的线性结构。特点与操作随机访问通过下标索引访问任意元素时间复杂度是O(1)。这是数组最大的优势。arr [10, 20, 30, 40, 50] print(arr[2]) # 输出 30直接计算内存地址偏移即可得到。插入/删除低效在数组中间插入或删除元素需要移动后续所有元素以保持连续性平均时间复杂度为O(n)。# 在索引2处插入元素99 arr.insert(2, 99) # 需要将30,40,50依次后移 print(arr) # [10, 20, 99, 30, 40, 50]适用场景需要频繁按索引查询而插入删除操作较少的场景。3.2 链表非连续空间的灵活之道链表中的元素节点在内存中不是连续存储的每个节点除了存储数据还存储指向下一个节点地址的指针或引用。特点与操作顺序访问要访问第i个元素必须从头节点开始逐个遍历时间复杂度为O(n)。插入/删除高效只要修改相关节点的指针即可完成插入或删除时间复杂度为O(1)前提是已知要操作节点的前驱节点。# 单向链表的节点定义 class ListNode: def __init__(self, val0, nextNone): self.val val self.next next # 在节点prev之后插入新节点new_node def insert_after(prev_node, new_node): new_node.next prev_node.next prev_node.next new_node适用场景需要频繁在任意位置插入或删除而对随机访问需求不高的场景。3.3 抽象数据类型接口与实现的分离在讨论数据结构时我们常常提到抽象数据类型Abstract Data Type, ADT。ADT定义了一个数据模型以及在该模型上的一系列操作但它不关心这些操作在计算机内部如何实现。例如“栈”Stack作为一个ADT定义了数据对象集一个有0个或多个元素的线性序列。操作集push(x)将元素x压入栈顶。pop()弹出并返回栈顶元素。top()返回栈顶元素但不弹出。isEmpty()判断栈是否为空。至于这个栈是用数组实现顺序栈还是用链表实现链式栈ADT并不关心。这种“接口与实现分离”的思想是软件工程的核心也是COMP2123课程中反复强调的重点。4. 实战用Python实现一个链表理解了概念我们动手实现一个简单的单向链表并完成其基本操作。4.1 定义链表节点class ListNode: 链表节点类 def __init__(self, val0, nextNone): 初始化节点 :param val: 节点值 :param next: 指向下一个节点的引用 self.val val self.next next4.2 实现链表类及其基本操作class SinglyLinkedList: 单向链表类 def __init__(self): 初始化一个空链表头节点为None self.head None def is_empty(self): 判断链表是否为空 return self.head is None def insert_at_head(self, val): 在链表头部插入节点 - O(1) new_node ListNode(val) new_node.next self.head self.head new_node def insert_after_node(self, prev_node, val): 在给定节点之后插入新节点 - O(1) if prev_node is None: print(给定的前一个节点不能为空) return new_node ListNode(val) new_node.next prev_node.next prev_node.next new_node def search(self, key): 在链表中搜索值为key的节点 - O(n) current self.head while current: if current.val key: return current current current.next return None def delete_node(self, key): 删除第一个值为key的节点 - O(n) # 处理头节点就是要删除的节点的情况 if self.head and self.head.val key: self.head self.head.next return # 遍历查找要删除的节点及其前驱 prev None curr self.head while curr and curr.val ! key: prev curr curr curr.next # 如果找到则删除 if curr: prev.next curr.next # 如果没找到curr为None什么也不做 def print_list(self): 打印整个链表 nodes [] current self.head while current: nodes.append(str(current.val)) current current.next print( - .join(nodes) if nodes else 空链表)4.3 运行与测试# 测试代码 if __name__ __main__: # 1. 创建链表 llist SinglyLinkedList() print(初始链表:) llist.print_list() # 空链表 # 2. 在头部插入 llist.insert_at_head(3) llist.insert_at_head(2) llist.insert_at_head(1) print(头部插入1,2,3后:) llist.print_list() # 1 - 2 - 3 # 3. 在指定节点后插入 node_2 llist.search(2) # 找到值为2的节点 if node_2: llist.insert_after_node(node_2, 99) print(在节点2后插入99:) llist.print_list() # 1 - 2 - 99 - 3 # 4. 搜索 found llist.search(99) print(f搜索99: {找到 if found else 未找到}) # 找到 # 5. 删除节点 llist.delete_node(2) print(删除节点2后:) llist.print_list() # 1 - 99 - 3 # 6. 删除不存在的节点 llist.delete_node(100) print(尝试删除100后:) llist.print_list() # 1 - 99 - 3通过这个完整的例子你可以清晰地看到链表在内存中是如何通过指针连接以及插入、删除操作是如何通过修改指针来实现的。这正是链表相比数组的优势所在。5. 常见问题与排查思路在学习数据结构实现时新手常会遇到一些典型问题。问题现象可能原因解决思路访问空指针Null Pointer在链表操作中试图访问None或null的next属性。例如在空链表上执行delete或遍历时未检查当前节点是否为None。1.防御性编程在执行任何节点操作前先判断节点是否为None。2.画图辅助在纸上画出链表状态和指针变化理清逻辑。3.使用哨兵节点在链表头部添加一个不存储实际数据的哑节点可以简化边界条件处理。内存泄漏C/C中在动态分配内存的语言中删除节点后只修改了指针没有释放该节点占用的内存。1.成对管理记住malloc/new必须对应free/delete。2.在删除节点函数中先保存下一个节点的地址再释放当前节点内存。无限循环链表出现环状结构本不应有环导致遍历函数无法终止。常见于指针操作错误。1.检查指针赋值确保next指针指向正确的节点尤其是在插入和反转操作中。2.使用“快慢指针”法检测环一个经典算法面试题也是有效的调试手段。逻辑错误导致数据丢失例如在删除节点时先断开了前驱节点与当前节点的连接却丢失了当前节点与后继节点的连接信息。1.顺序很重要在修改指针前先用临时变量保存必要的信息。2.单元测试为你的链表类编写小型测试覆盖空链表、单节点、头节点操作、尾节点操作等边界情况。6. 最佳实践与工程建议将数据结构的知识应用到实际项目中需要遵循一些工程原则。6.1 理解标准库而非重复造轮子在实际开发中除非有极特殊的性能或功能需求否则应优先使用编程语言提供的标准库数据结构。Pythonlist动态数组、collections.deque双端队列、dict哈希表。JavaArrayList,LinkedList,HashMap,HashSet。Cstd::vector,std::list,std::unordered_map。学习实现的意义在于当你知道它们的底层原理后你就能更明智地选择和使用它们。例如你知道ArrayList在中间插入慢就会避免在循环中频繁使用add(index, element)。6.2 复杂度分析先行在设计函数或模块前先思考其时间和空间复杂度。问自己几个问题这个函数会被频繁调用吗处理的数据规模n大概有多大最耗时的操作在哪里有优化的可能吗 养成这种思维习惯是写出高效代码的第一步。6.3 为数据结构编写清晰的API和文档即使是练习也请像编写库代码一样对待你的实现。class MyVector: 一个简化的动态数组实现 def __init__(self, capacity10): 初始化动态数组 :param capacity: 初始容量 (默认10) self._capacity capacity self._size 0 self._data [None] * self._capacity def push_back(self, value): 在数组末尾添加元素若空间不足则自动扩容 - 摊还时间复杂度 O(1) if self._size self._capacity: self._resize(2 * self._capacity) # 扩容 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清晰的注释和规范的命名如_开头的私有方法能极大提升代码的可读性和可维护性。6.4 重视测试与边界条件“我的代码在正常情况下运行良好”是远远不够的。必须测试边界条件数据结构为空时的操作插入、删除、查找。只有一个元素时的操作。重复元素的处理。操作导致容量变化时如数组扩容、缩容。7. 学习路线与资源推荐第一周的内容是打开数据结构与算法大门的钥匙。为了后续更深入地学习你可以按照以下路径规划巩固基础彻底理解数组、链表、复杂度分析。完成课后所有关于链表操作的编程练习。深入线性结构学习栈Stack和队列Queue理解它们作为受限线性表的特性和应用场景如函数调用栈、BFS/DFS。掌握高级数据结构随后课程会逐步展开树Tree特别是二叉树、二叉搜索树、图Graph、哈希表Hash Table等。每学习一种都尝试自己实现基本操作。攻克经典算法排序冒泡、选择、插入、归并、快排、搜索二分查找、递归、动态规划、贪心算法等。理解其思想并分析不同数据规模下的优劣。理论联系实际刷题平台在LeetCode、HackerRank等平台上从“Easy”难度开始练习应用所学知识。阅读源码尝试阅读你所用语言标准库中简单数据结构如Pythoncollections模块的源码或官方文档看专业实现与你自己的有何不同。项目应用在小型个人项目中刻意使用不同的数据结构体会其差异。学习资源方面除了COMP2123的官方课件经典的《算法导论》、《数据结构与算法分析》等书籍永远是可靠的参考。网络上像GeeksforGeeks、Stack Overflow等社区有大量针对具体问题的讨论。数据结构与算法的学习是一场马拉松而非短跑。第一周建立正确的认知和兴趣比快速啃下所有知识点更重要。多动手写代码多画图理解指针的指向多思考“为什么用这个而不用那个”你会在后续的学习中越来越得心应手。如果在实现过程中遇到任何问题欢迎在评论区交流讨论。
大家好我是专注于技术分享的博主。最近在整理悉尼大学USYDCOMP2123这门“数据结构与算法”课程的学习笔记发现很多同学在入门阶段对核心概念和抽象思维感到困惑。本文将以第一周公开课内容为基础结合我个人的学习与实践经验系统性地梳理数据结构与算法的入门知识。无论你是正在学习这门课程的学生还是希望夯实计算机科学基础的开发者都能从本文中获得从概念理解到代码实践的完整指导。1. 数据结构与算法为什么是程序员的基石在开始学习具体的链表或排序之前我们必须先理解一个根本问题为什么数据结构与算法如此重要简单来说数据结构是数据的组织、管理和存储格式其目的是为了高效地访问和修改数据。你可以把它想象成一个工具箱不同的工具数据结构适合完成不同的任务。而算法则是解决特定问题的一系列清晰指令是操作这些“工具”的具体方法。两者相辅相成共同决定了程序的效率、可读性和可维护性。1.1 从现实问题到抽象模型所有复杂的软件系统其底层都在处理数据。例如社交网络的好友关系如何快速找到共同好友这背后是图Graph数据结构。浏览器的前进后退功能如何实现这依赖于栈Stack的“后进先出”特性。文本编辑器的撤销操作如何记录一系列操作并回退这同样可以用栈或者更复杂的命令模式配合数据结构来实现。数据库索引如何在海量数据中快速检索一条记录这离不开B树、B树、哈希表等高级数据结构。COMP2123这门课的目标就是教会我们如何为具体问题选择最合适的“工具箱”数据结构和“使用说明书”算法。1.2 核心衡量标准时间与空间复杂度评价一个算法好坏不能只看它是否能运行出正确结果。在资源有限的计算机世界里我们需要量化的标准这就是时间复杂度和空间复杂度通常用大O符号Big O notation表示。时间复杂度指算法执行所需的时间随着数据规模n增长而增长的趋势。它关注的是操作次数的增长率而非精确的秒数。空间复杂度指算法执行过程中临时占用的存储空间大小随数据规模增长的趋势。为什么大O表示法如此重要因为它让我们能脱离具体的机器性能在理论层面比较不同算法的效率。例如O(1)的算法效率远高于O(n²)的算法尤其是当n很大时。第一周课程通常会引入这个概念这是分析一切算法的起点。2. 环境准备工欲善其事必先利其器学习数据结构与算法理论理解是关键但动手实践同样不可或缺。一个合适的编程环境能让你更专注于逻辑本身。2.1 语言选择C, C, Java 还是 PythonCOMP2123课程可能使用多种语言教学核心思想是相通的。选择哪种语言实践可以参考以下建议C/C更接近底层能让你深刻理解内存管理指针、引用、数据在内存中的实际布局。这对于理解链表、树等指针密集型数据结构非常有帮助。缺点是语法相对繁琐。Java拥有丰富的内置集合框架如ArrayList, LinkedList, HashMap但同时也封装了底层细节。适合快速实现和验证算法思想并且强类型和面向对象的特性对工程化思维有益。Python语法简洁表达力强可以用更少的代码实现算法逻辑非常适合算法原型设计和面试刷题。但其动态类型和高级抽象可能会掩盖一些底层细节。建议初学者可以从Python或Java开始快速建立信心和理解流程。若想深入理解一定要用C/C重新实现一遍关键数据结构。2.2 开发环境搭建这里以Visual Studio Code (VSCode)配合Python环境为例因为它轻量、跨平台且插件丰富。安装Python访问 python.org 下载并安装最新稳定版。安装时务必勾选“Add Python to PATH”。安装VSCode从官网下载安装。配置VSCode安装官方Python扩展ms-python.python。打开一个空文件夹作为你的项目目录。创建一个新文件例如test.py。验证环境在test.py中输入以下代码并运行右键选择“在终端中运行Python文件”。print(Hello, Data Structures!) arr [3, 1, 4, 1, 5, 9] print(Original array:, arr) arr.sort() print(Sorted array:, arr)如果能看到排序后的数组输出说明环境配置成功。3. 核心数据结构初探数组、链表与抽象数据类型ADT第一周通常会从最基础也是最重要的两个线性数据结构开始数组Array和链表Linked List。理解它们的区别是理解后续所有数据结构的基础。3.1 数组连续空间的优与劣数组是一种在连续内存空间中存储相同类型数据的线性结构。特点与操作随机访问通过下标索引访问任意元素时间复杂度是O(1)。这是数组最大的优势。arr [10, 20, 30, 40, 50] print(arr[2]) # 输出 30直接计算内存地址偏移即可得到。插入/删除低效在数组中间插入或删除元素需要移动后续所有元素以保持连续性平均时间复杂度为O(n)。# 在索引2处插入元素99 arr.insert(2, 99) # 需要将30,40,50依次后移 print(arr) # [10, 20, 99, 30, 40, 50]适用场景需要频繁按索引查询而插入删除操作较少的场景。3.2 链表非连续空间的灵活之道链表中的元素节点在内存中不是连续存储的每个节点除了存储数据还存储指向下一个节点地址的指针或引用。特点与操作顺序访问要访问第i个元素必须从头节点开始逐个遍历时间复杂度为O(n)。插入/删除高效只要修改相关节点的指针即可完成插入或删除时间复杂度为O(1)前提是已知要操作节点的前驱节点。# 单向链表的节点定义 class ListNode: def __init__(self, val0, nextNone): self.val val self.next next # 在节点prev之后插入新节点new_node def insert_after(prev_node, new_node): new_node.next prev_node.next prev_node.next new_node适用场景需要频繁在任意位置插入或删除而对随机访问需求不高的场景。3.3 抽象数据类型接口与实现的分离在讨论数据结构时我们常常提到抽象数据类型Abstract Data Type, ADT。ADT定义了一个数据模型以及在该模型上的一系列操作但它不关心这些操作在计算机内部如何实现。例如“栈”Stack作为一个ADT定义了数据对象集一个有0个或多个元素的线性序列。操作集push(x)将元素x压入栈顶。pop()弹出并返回栈顶元素。top()返回栈顶元素但不弹出。isEmpty()判断栈是否为空。至于这个栈是用数组实现顺序栈还是用链表实现链式栈ADT并不关心。这种“接口与实现分离”的思想是软件工程的核心也是COMP2123课程中反复强调的重点。4. 实战用Python实现一个链表理解了概念我们动手实现一个简单的单向链表并完成其基本操作。4.1 定义链表节点class ListNode: 链表节点类 def __init__(self, val0, nextNone): 初始化节点 :param val: 节点值 :param next: 指向下一个节点的引用 self.val val self.next next4.2 实现链表类及其基本操作class SinglyLinkedList: 单向链表类 def __init__(self): 初始化一个空链表头节点为None self.head None def is_empty(self): 判断链表是否为空 return self.head is None def insert_at_head(self, val): 在链表头部插入节点 - O(1) new_node ListNode(val) new_node.next self.head self.head new_node def insert_after_node(self, prev_node, val): 在给定节点之后插入新节点 - O(1) if prev_node is None: print(给定的前一个节点不能为空) return new_node ListNode(val) new_node.next prev_node.next prev_node.next new_node def search(self, key): 在链表中搜索值为key的节点 - O(n) current self.head while current: if current.val key: return current current current.next return None def delete_node(self, key): 删除第一个值为key的节点 - O(n) # 处理头节点就是要删除的节点的情况 if self.head and self.head.val key: self.head self.head.next return # 遍历查找要删除的节点及其前驱 prev None curr self.head while curr and curr.val ! key: prev curr curr curr.next # 如果找到则删除 if curr: prev.next curr.next # 如果没找到curr为None什么也不做 def print_list(self): 打印整个链表 nodes [] current self.head while current: nodes.append(str(current.val)) current current.next print( - .join(nodes) if nodes else 空链表)4.3 运行与测试# 测试代码 if __name__ __main__: # 1. 创建链表 llist SinglyLinkedList() print(初始链表:) llist.print_list() # 空链表 # 2. 在头部插入 llist.insert_at_head(3) llist.insert_at_head(2) llist.insert_at_head(1) print(头部插入1,2,3后:) llist.print_list() # 1 - 2 - 3 # 3. 在指定节点后插入 node_2 llist.search(2) # 找到值为2的节点 if node_2: llist.insert_after_node(node_2, 99) print(在节点2后插入99:) llist.print_list() # 1 - 2 - 99 - 3 # 4. 搜索 found llist.search(99) print(f搜索99: {找到 if found else 未找到}) # 找到 # 5. 删除节点 llist.delete_node(2) print(删除节点2后:) llist.print_list() # 1 - 99 - 3 # 6. 删除不存在的节点 llist.delete_node(100) print(尝试删除100后:) llist.print_list() # 1 - 99 - 3通过这个完整的例子你可以清晰地看到链表在内存中是如何通过指针连接以及插入、删除操作是如何通过修改指针来实现的。这正是链表相比数组的优势所在。5. 常见问题与排查思路在学习数据结构实现时新手常会遇到一些典型问题。问题现象可能原因解决思路访问空指针Null Pointer在链表操作中试图访问None或null的next属性。例如在空链表上执行delete或遍历时未检查当前节点是否为None。1.防御性编程在执行任何节点操作前先判断节点是否为None。2.画图辅助在纸上画出链表状态和指针变化理清逻辑。3.使用哨兵节点在链表头部添加一个不存储实际数据的哑节点可以简化边界条件处理。内存泄漏C/C中在动态分配内存的语言中删除节点后只修改了指针没有释放该节点占用的内存。1.成对管理记住malloc/new必须对应free/delete。2.在删除节点函数中先保存下一个节点的地址再释放当前节点内存。无限循环链表出现环状结构本不应有环导致遍历函数无法终止。常见于指针操作错误。1.检查指针赋值确保next指针指向正确的节点尤其是在插入和反转操作中。2.使用“快慢指针”法检测环一个经典算法面试题也是有效的调试手段。逻辑错误导致数据丢失例如在删除节点时先断开了前驱节点与当前节点的连接却丢失了当前节点与后继节点的连接信息。1.顺序很重要在修改指针前先用临时变量保存必要的信息。2.单元测试为你的链表类编写小型测试覆盖空链表、单节点、头节点操作、尾节点操作等边界情况。6. 最佳实践与工程建议将数据结构的知识应用到实际项目中需要遵循一些工程原则。6.1 理解标准库而非重复造轮子在实际开发中除非有极特殊的性能或功能需求否则应优先使用编程语言提供的标准库数据结构。Pythonlist动态数组、collections.deque双端队列、dict哈希表。JavaArrayList,LinkedList,HashMap,HashSet。Cstd::vector,std::list,std::unordered_map。学习实现的意义在于当你知道它们的底层原理后你就能更明智地选择和使用它们。例如你知道ArrayList在中间插入慢就会避免在循环中频繁使用add(index, element)。6.2 复杂度分析先行在设计函数或模块前先思考其时间和空间复杂度。问自己几个问题这个函数会被频繁调用吗处理的数据规模n大概有多大最耗时的操作在哪里有优化的可能吗 养成这种思维习惯是写出高效代码的第一步。6.3 为数据结构编写清晰的API和文档即使是练习也请像编写库代码一样对待你的实现。class MyVector: 一个简化的动态数组实现 def __init__(self, capacity10): 初始化动态数组 :param capacity: 初始容量 (默认10) self._capacity capacity self._size 0 self._data [None] * self._capacity def push_back(self, value): 在数组末尾添加元素若空间不足则自动扩容 - 摊还时间复杂度 O(1) if self._size self._capacity: self._resize(2 * self._capacity) # 扩容 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清晰的注释和规范的命名如_开头的私有方法能极大提升代码的可读性和可维护性。6.4 重视测试与边界条件“我的代码在正常情况下运行良好”是远远不够的。必须测试边界条件数据结构为空时的操作插入、删除、查找。只有一个元素时的操作。重复元素的处理。操作导致容量变化时如数组扩容、缩容。7. 学习路线与资源推荐第一周的内容是打开数据结构与算法大门的钥匙。为了后续更深入地学习你可以按照以下路径规划巩固基础彻底理解数组、链表、复杂度分析。完成课后所有关于链表操作的编程练习。深入线性结构学习栈Stack和队列Queue理解它们作为受限线性表的特性和应用场景如函数调用栈、BFS/DFS。掌握高级数据结构随后课程会逐步展开树Tree特别是二叉树、二叉搜索树、图Graph、哈希表Hash Table等。每学习一种都尝试自己实现基本操作。攻克经典算法排序冒泡、选择、插入、归并、快排、搜索二分查找、递归、动态规划、贪心算法等。理解其思想并分析不同数据规模下的优劣。理论联系实际刷题平台在LeetCode、HackerRank等平台上从“Easy”难度开始练习应用所学知识。阅读源码尝试阅读你所用语言标准库中简单数据结构如Pythoncollections模块的源码或官方文档看专业实现与你自己的有何不同。项目应用在小型个人项目中刻意使用不同的数据结构体会其差异。学习资源方面除了COMP2123的官方课件经典的《算法导论》、《数据结构与算法分析》等书籍永远是可靠的参考。网络上像GeeksforGeeks、Stack Overflow等社区有大量针对具体问题的讨论。数据结构与算法的学习是一场马拉松而非短跑。第一周建立正确的认知和兴趣比快速啃下所有知识点更重要。多动手写代码多画图理解指针的指向多思考“为什么用这个而不用那个”你会在后续的学习中越来越得心应手。如果在实现过程中遇到任何问题欢迎在评论区交流讨论。
