简介数据结构与算法是编程的核心基础在Python中经典结构如链表、二叉树、哈希表都有对应的实现方式与性能特征。理解时间复杂度与空间换时间的本质是写出高效代码的前提。无论是准备408考研、应对期末考试还是日常处理爬虫与数据分析任务掌握复杂度分析并亲手实现常见结构都至关重要。本文从Python内置类型与手写实现的差异出发梳理单链表、递归遍历、排序算法等关键知识点并结合timeit实测、常见翻车现场与复习路径帮助学习者将抽象理论转化为可运行的代码能力。1. 一份名为“Python数据结构与算法分析”的文档到底值不值得照着学电脑里躺着一份“Python数据结构与算法分析.docx”你可能是为期末复习下载的也可能是准备 408 考研时顺手存的还可能刚装好 Python、想系统补一遍“数据结构与算法分析”的底子。先说结论这类文档最大的价值不是让你背定义而是把抽象概念翻译成能在 Python 里跑、能画出复杂度曲线的代码。只要你会写 Python 基础语法照着文档里的思路自己实现一遍链表、二叉树、排序再跑几个实验比看十遍 PPT 管用。这份文档适合三类人准备 408 或期末考、需要手写代码的学生刷题刷到瓶颈、想回头补结构的自学者以及用 Python 做爬虫或数据分析、发现数据一多就卡顿的从业者。它的最终目标是让你看完敢动手而不是收藏完继续吃灰。2. 把 docx 里的抽象结构变成 Python 对象内置类型与手写实现很多初学者拿到一份“Python 数据结构与算法分析”文档第一反应是翻到树和图就开始背遍历顺序。这个顺序是反的。数据结构课程里的“逻辑结构”和 Python 这门语言提供的“内置结构”之间有一层很关键的翻译工作要做。翻译得好后面的算法分析才有意义。2.1 先分清内置类型能做什么list、dict、set 与经典结构的关系Python 的 list 不是传统教科书里的“链表”它是一个动态数组。它能在尾部快速 append也能按下标 O(1) 访问但如果你在头部 insert(0, x)底层要搬运整段数据复杂度是 O(n)。很多刚看完数据结构文档的人直接拿 list 当链表用写出来的代码功能对、性能完全不是一回事。常见做法是先建立一个映射表栈可以用 list 模拟队列入门阶段也可以用 list 和索引指针实现但讲究效率时换成 collections.dequedict 本质是哈希表天然适合做映射、计数器、图的邻接表set 做去重和集合运算tuple 做不可变记录。文档里讲的“哈希表”“树”“图”在 Python 里最朴素的落地方案分别是 dict、自定义 TreeNode 类和 dict list 组合。这里要特别提醒一个容易混淆的点pandas 里的 DataFrame 在 Python 语境里也叫“数据结构”但那是数据分析的二维表格是另一个维度的事。数据结构与算法分析这门课里的“线性表”“树”“图”讲的是数据之间的逻辑关系和组织方式。如果你搜“Python 数据结构”搜到一堆 pandas 教程先把它们放一边别让 DataFrame 干扰你对经典数据结构的学习。文档里的结构都要能用纯 Python 对象实现不依赖任何第三方库。在动手写代码之前建议你把文档里每一章的数据结构列成一张表逻辑结构是什么、对应 Python 内置类型是什么、必须手写实现的是什么。像链表、二叉树、图这种内置类型替代不了的结构才是你真正要花时间的重点也是 408 和期末考里最常要求“代码必背”的部分。2.2 手写单链表Node 与 LinkedList 的四个必要方法严蔚敏那本 C 语言版数据结构教材里链表章节的代码全是指针操作。换到 Python指针变成了对象引用NULL 变成了 None。这个转换看起来简单但几乎每个初学都会在 next 被置为 None 之后继续调用 next然后撞上 AttributeError。class Node: def __init__(self, data): self.data data self.next None # Python没有指针用对象引用串起下一个节点 class LinkedList: def __init__(self): self.head None self.size 0 def get(self, index): # 按索引取值链表只能从头遍历O(n) if index 0 or index self.size: raise IndexError(index out of range) cur self.head for _ in range(index): cur cur.next return cur.data def insert(self, index, data): # 插入三步造新节点、先接后继、再接前驱 if index 0 or index self.size: raise IndexError(index out of range) new_node Node(data) if index 0: new_node.next self.head self.head new_node else: prev self.head for _ in range(index - 1): prev prev.next new_node.next prev.next prev.next new_node self.size 1 def delete(self, index): # 删除头节点和删除中间节点处理逻辑不同 if index 0 or index self.size: raise IndexError(index out of range) if index 0: self.head self.head.next else: prev self.head for _ in range(index - 1): prev prev.next prev.next prev.next.next self.size - 1这段代码有四个需要说明的关键点。第一Node 里的 next 保存的是对下一个 Node 对象的引用不是复制对象当你写 new_node.next prev.next 时new_node 和 prev.next 指向同一个节点这是链式操作的基础。第二insert 的顺序必须先让新节点接上后继再让前驱接上新节点顺序反了会丢失整个链表的后半段。第三delete 头节点时直接移动 headdelete 尾节点时 prev.next 会被置为 None这符合单链表的定义不需要额外处理。第四维护 size 字段可以避免每次调用 get 或 insert 都遍历统计长度这是一种典型的“用空间换时间”。写完后建议你至少跑三个用例空链表里 insert 头节点、删除唯一节点、在尾部插入后再遍历打印。这些用例能同时暴露 None 引用、边界索引和遍历终止条件的问题是数据结构链表入门阶段最值得做的调试训练。2.3 树与递归先写终止条件再写递推关系二叉树章节是“Python 数据结构与算法分析”文档里最容易让人卡住的部分。它的难点不在树本身而在递归。很多人写递归函数时习惯先想递推式忽略了终止条件结果递归一层层往下掉最后要么报错要么返回一堆空值。class TreeNode: def __init__(self, val): self.val val self.left None self.right None def inorder(root): # 中序遍历左-根-右 if root is None: return [] return inorder(root.left) [root.val] inorder(root.right) def preorder(root): # 前序遍历根-左-右 if root is None: return [] return [root.val] preorder(root.left) preorder(root.right) def postorder(root): # 后序遍历左-右-根 if root is None: return [] return postorder(root.left) postorder(root.right) [root.val]这段代码把递归三件事拆得很清楚终止条件是“节点为空则返回空列表”递推关系按遍历顺序决定返回值是“以当前节点为根的子树遍历结果列表”。每次递归调用都在做同一件事——处理一棵子树然后把结果拼接给上一层。这是理解递归的关键不要试图跟踪每一层调用只需确认当前层返回什么、上层怎么用它。代码里用拼接列表写法简洁但会产生中间新列表数据量小的时候没问题刷算法题时如果内存限制严格可以改成传入 result 列表的写法用 append 累积结果。三种遍历顺序分别对应表达式求值、拷贝二叉树和删除节点等不同场景文档里每个场景背后都有对应考点。复习 408 时你会发现二叉树遍历不是背下来的而是靠亲手画一棵三层小树把三种遍历结果写出来再和代码输出对照。3. 算法分析大 O 不是背出来的是算出来再测出来的数据结构文档的后半部分通常叫“算法分析”。这个部分最容易变成纸上谈兵书里写出冒泡排序是 O(n²)读者记住了但换一道题、换一段自己的代码就不知道复杂度是多少了。算法分析要落地得学会用三段式判断法再用实验验证判断。3.1 三段式复杂度判断循环、递归、隐藏操作判断一段代码的时间复杂度我一般按三个步骤走。第一步看循环结构有几层嵌套循环每层循环的上限和 n 什么关系外层循环乘内层循环的时间基本就是这段代码的量级。第二步看每次循环内部做了什么是 O(1) 的普通赋值还是调用了另一个会遍历的函数。第三步看调用的容器方法有没有隐藏复杂度这一步最容易被忽略。举个例子for x in list本身是 O(n)如果在这个循环内部又写了if x in another_list那内外相乘就变成了 O(n²)。同理dict 的查找平均是 O(1)set 的成员判断平均也是 O(1)但 list 的 index 和in操作是 O(n)。数据结构期末复习和 408 里大量复杂度选择题考的就是你能否识别这些隐藏操作。文档里如果有“最好情况、最坏情况、平均情况”这一节建议你用三个阶段去理解先看最坏情况这是算法不会超出预期的底线再看平均情况这是实际使用中最常碰到的最后看最好情况它通常只在数据恰好有序时出现工程上很少作为优化依据。排序算法里快排最坏 O(n²)、平均 O(n log n) 这个差异就是典型例子。3.2 用 timeit 实测append 和 insert(0) 的真实差距光会估算还是不够你需要在本地把复杂度“测”出来。Python 自带 timeit 模块它能把一段代码反复执行多次、统计总耗时比手动time.time()掐表准确得多。这个实验建议每个人都亲手跑一次因为只有看到数据你才会真正记住为什么列表头部插入要避免。import timeit setup data list(range(10000)) append_time timeit.timeit(data.append(1), setupsetup, number100000) print(append 耗时:, append_time) insert_time timeit.timeit(data.insert(0, 1), setupsetup, number100000) print(insert(0) 耗时:, insert_time)这段代码的 setup 参数先创建了一个长度为 10000 的列表这样每次计时只统计操作本身不会把建列表的时间算进去。timeit 的第一个参数是要测试的语句第二个参数是环境变量number 表示执行次数。执行 10 万次 append耗时通常只有几十毫秒而同等次数的 insert(0, 1)因为每次都要把 10000 个元素往后挪耗时会高出一两个数量级这在你的机器上会看得非常直观。这个实验的价值不只是验证一句话而是帮你建立“复杂度分析决定代码性能”的直觉。用同样的方法你还可以测 dict 按 key 取值和 list 按 value 查找的差距、deque 和 list 做队列的差距。每次测完都在文档对应章节旁边写上一行笔记这份“Python 数据结构与算法分析”docx 就从复习资料变成了你自己的实验记录。3.3 排序算法一页纸哪些该手写哪些直接用 sorted排序是数据结构文档里篇幅最重、也最容易让人迷失的章节。冒泡、选择、插入、希尔、归并、快排、堆排再加上计数排序和基数排序一口气学下来很少有人能全部记住。先给你一张对照表把最关键的三个指标横着比一遍。排序算法平均时间复杂度最坏时间复杂度稳定性是否原地排序冒泡排序O(n²)O(n²)稳定是选择排序O(n²)O(n²)不稳定是插入排序O(n²)O(n²)稳定是希尔排序O(n log n) ~ O(n²)O(n²)不稳定是归并排序O(n log n)O(n log n)稳定否快速排序O(n log n)O(n²)不稳定是堆排序O(n log n)O(n log n)不稳定是计数排序O(n k)O(n k)稳定否表格里的稳定性和是否原地排序是 408 和期末考最爱出的两个判断题。稳定性指值相等的元素排序后相对顺序是否保持不变原地排序指是否只借助常数级别的额外空间。归并排序是稳定但非原地快排是原地但不稳定这两条几乎是必考。你不需要把每一种排序的实现都背下来但快排和归并的手写版本必须过关因为它们同时也是递归和分治思想的载体。工程实践中Python 内置的 sorted 和 list.sort 基于 Timsort 实现综合表现稳定日常写代码直接用就行没必要自己造轮子。这里有个新手常踩的坑list.sort() 是原地修改、返回 Nonesorted(list) 是返回新列表。很多人写完data data.sort()后发现 data 变成了 None这就是没分清“原地方法”和“返回新对象的内置函数”的后果。4. 数据结构和算法分析避坑实录5 个最常见的翻车现场4.1 照抄 C 语言版代码报 AttributeError: NoneType object has no attribute next现象你把严蔚敏或王道书上的链表代码改成 Python插入、删除一跑就报 TypeError。原因C 语言里指针指向空地址是 NULL写p-next不会报错只是访问无效内存。Python 里没有指针空引用是 None对 None 取 next 属性会直接抛 AttributeError。很多人在遍历链表时没有判空或者删除节点后没有更新前驱的 next。解决所有对 next 的访问前面都要确认当前节点不是 None。更简单的办法是给链表加一个虚拟头节点 dummy让 head 永远不会是 None这样统一了“插入头部”和“插入中间”两段逻辑。数据结构链表章节用这个技巧能少写一半特判。4.2 递归深度刚过一千就 RecursionError现象二叉树深度稍微大一点比如一千多层递归遍历直接报 RecursionError: maximum recursion depth exceeded。原因Python 默认递归深度限制约 1000这不是你代码写错了而是解释器为了防止栈溢出故意设的阈值。在 C/C 里递归深度可以开得很大很多教材不会提这个差异。解决复杂度过深时把递归改成迭代用显式栈模拟系统调用栈。比如前序遍历可以把递归函数改成stack [root]然后 while 循环弹栈、压栈。也可以临时用sys.setrecursionlimit(10000)提高上限但这不是后悔药递归层数上万后解释器照样扛不住显式栈才是可控方案。4.3 data data.sort() 之后 data 变成 None现象对列表排序后打印发现是 None代码还看不出哪里错了。原因list.sort() 是原地排序方法返回值是 Nonesorted() 是内置函数返回新列表。很多从 Java 或 C 转 Python 的人会把两者混用因为那些语言里的 sort 方法通常有返回值。解决要原地排序就只写data.sort()然后继续用 data要保留原列表就写new_data sorted(data)。这条规则同时适用于 list.append、list.reverse、dict.update 等所有原地修改方法。写完代码后可以加一行注释说明意图防止自己过两天再犯。4.4 代码功能全对但 LeetCode 超时没看出复杂度是 O(n²)现象小数据量测试都通过一提交就 Time Limit Exceeded。原因代码里有隐藏的高成本操作。最常见的三类是用list.insert(0, x)反复在头部插入、用if x in list在循环内部做成员判断、用字符串拼长文本。每一行单独看都正常但放到循环里就凭空多出 O(n) 或 O(n²) 的开销。解决回到 3.1 的三段式判断法逐行标出每句话的时间复杂度尤其注意循环体内部的容器操作。头部插入改成 append 最后再反转成员判断改成 set 或 dict字符串拼接改用列表 join。刷题卡超时的时候第一反应不是换算法而是先查隐藏操作。4.5 遍历字典时删除元素报 RuntimeError: dictionary changed size during iteration现象for k in d:循环里执行del d[k]程序中断并提示字典在迭代期间大小发生了变化。原因Python 的 dict 底层是哈希表迭代器基于哈希表当前状态。如果循环体内增删 key哈希表结构调整迭代器就失去合法性。这一点和 list 在遍历时改元素不同list 只是可能漏值dict 是直接抛异常。解决需要遍历时过滤改成for k in list(d.keys())先取出所有 key 的快照再遍历删除。或者用字典推导式重建新字典属于另一种“不改原表”的思路。图算法里用 dict 做邻接表时最容易踩这个坑写完 BFS 或 DFS 后记得检查循环里有没有删 key 的操作。5. 从 docx 到能跑的项目一份可复现的复习与动手路径把文档从头读一遍只是第一步真正掌握的标准是合上文档能把代码写出来。下面这套路径我实践过也推荐过很多人先把文档拆成脚本再做题检验最后用一个小项目把知识串起来。5.1 把文档章节映射成脚本文件目录与命名规范常见做法是按照“编号 主题”的规范把“Python 数据结构与算法分析”docx 里的每一章对应成一个可独立运行的 py 文件。这么做的好处是每次想复习哪个结构直接运行对应脚本就能看到输出不需要翻文档。algo_playground/ ├── 01_builtin_types.py ├── 02_linked_list.py ├── 03_stack_queue.py ├── 04_binary_tree.py ├── 05_sorting.py ├── 06_graph_bfs_dfs.py ├── data/ │ └── words.txt └── tests/ └── test_linked_list.py每个文件的头部把对应文档章节的核心结论写成注释比如 05_sorting.py 的注释里把前面那张排序对比表抄上去。data 目录放实验用的文本文件tests 目录用 unittest 写链表和树的最小测试保证每次改造后不把旧功能弄坏。这样整份文档就不是躺在桌面上的一个 docx 文件而是变成了一棵可以反复运行的代码树。如果你已经装了 PyCharm 并配好了 Python 环境可以直接用 IDE 建项目如果只用命令行mkdir 建目录后把每个 py 文件用编辑器写好即可。这个阶段不需要任何第三方库纯标准库就能跑通全部代码。5.2 用小题检验掌握度数据结构常见题与知识点映射表文档复习完立刻做题效果最好。注意不是直接刷难题而是用能覆盖“数据结构与算法知识点归纳”的基础题来验证。下面这张表列了 10 道经典题目和它们对应的考察点每道题做完后回文档看对应章节把错因和复杂度写在旁边。题目类型核心考察点涉及结构反转链表指针操作与遍历单链表有效的括号匹配逻辑与栈顶操作栈二叉树层序遍历队列 BFS队列、二叉树数组去重哈希判断字典、集合合并两个有序数组双指针与边界处理列表斐波那契数列递归与缓存递归、字典单词频率统计哈希计数与排序字典、列表最小栈辅助栈设计栈环形链表快慢指针链表全排列回溯与递归展开递归、数组这 10 道题覆盖面广且难度递进。做题时要注意先自己写写不出来再翻文档对应章节禁止一边看代码一边抄。每道题跑通后把时间复杂度和空间复杂度写在文件顶部注释里这一步是在训练你没动手先分析的习惯。不需要为了刷数量而刷这 10 道吃透比机械刷 50 道效果更好。5.3 串一个小项目单词频率与 Top N 统计做完小题后做一个能串起多个知识点的短项目。统计文件里出现次数最多的单词这个需求至少要经过文件读取、正则清洗、哈希计数、排序输出四个环节正好覆盖文档里的多个章节。from collections import Counter import re def word_frequency(filepath, top_n10): # 读文件、清洗文本、统计词频、输出前N个 with open(filepath, encodingutf-8) as f: text f.read() words re.findall(r[a-zA-Z], text.lower()) counter Counter(words) return counter.most_common(top_n) if __name__ __main__: result word_frequency(data/words.txt, top_n10) for word, count in result: print(f{word}: {count})Counter 是 dict 的子类构造时自动完成“键存在则加一、不存在则初始化”的逻辑这正是哈希表的典型用法。most_common 内部按出现次数降序排序相当于一个以计数为 key 的排序流程。正则表达式[a-zA-Z]只提取英文字母组成的单词text.lower() 做归一化这两行解决文本清洗问题。整个脚本没有一行超过 20 个字符的复杂逻辑但却把文件 IO、正则、哈希计数、排序四个点全部覆盖。如果想往图的方向延伸可以把“相邻出现的单词”构造成邻接表统计共现关系这就自然过渡到了图结构。很多 Python 爬虫和数据分析场景里数据处理的核心逻辑和这个项目是同构的你以后写爬虫清洗文本、做统计时都会用到这套思路。6. 写算法前先画三张图一个让我少踩一半坑的习惯最后分享一个我用了很久的习惯动手写代码之前先在草稿纸上画三张图。第一张是数据结构形态图链表就画方块和箭头树就画父子节点连线。第二张是递归调用栈图从第一次调用开始画压栈和弹栈直到遇到终止条件再一层层返回。第三张是复杂度增长图横轴是输入规模 n纵轴是操作次数把不同算法的曲线画在同一张图上。这三张图里最有用的是第二张。拿最基础的斐波那契数列来说普通递归写法里 fib(5) 需要重复计算 fib(3)、fib(2) 多次调用栈图画出来以后你会清楚看到重复的子问题像一棵膨胀的树。解决办法是用缓存记录已算过的结果。def fib(n, memoNone): # memo是一个字典缓存已经算过的斐波那契值 if memo is None: memo {} if n in memo: return memo[n] if n 1: return n memo[n] fib(n - 1, memo) fib(n - 2, memo) return memo[n]memo 参数默认取 None是为了避免多个调用之间共享同一个可变默认值这是 Python 函数定义里一个经典陷阱。if n in memo利用 dict 的 O(1) 查找判断是否已计算命中缓存就直接返回不再递归展开。这个小小的改动把时间复杂度从 O(2^n) 降到 O(n)代价是额外的 O(n) 空间这就是典型的空间换时间。我现在的习惯是排序算法画复杂度增长图递归函数画调用栈图树和图相关的问题先画出结构形态再写代码。每次画完图边界条件、终止条件、返回值基本都清楚了写代码时很少需要回头调试。如果你刚接触这份“Python 数据结构与算法分析”文档建议从第二张调用栈图开始练它能让你的递归水平在两周内看到明显变化希望帮到你。本文还有配套的精品资源点击获取