Python数据结构与算法分析：从数组链表到动态规划实战

简介《Python数据结构与算法分析.docx》系统讲解Python语言环境中数据结构与算法的核心知识适合正在学习Python编程、准备算法相关考试或希望夯实编程基础的程序员与初学者。文档先从数据结构和算法的定义入手讲解二者如何配合解决实际问题接着介绍数组、链表等基本数据结构再深入二叉树、二叉搜索树、图等高级结构覆盖创建、遍历、插入、删除、搜索等关键操作的实现方法并配有简洁示例便于对照练习。资源共包含1个docx文件压缩包大小仅为15KB体积轻量下载后可直接阅读可充当课堂笔记或快速复习手册。目前已有787人学习内容层次清晰、示例具体能帮助读者快速搭建知识框架并理解常用数据结构的应用场景是一份实用的Python算法入门资料。1. Python 数据结构与算法分析讲义内容地图与适用人群这份《Python 数据结构与算法分析》讲义把数据结构的组织形式和算法的设计思路直接用 Python 代码串成了可以照着敲、照着改的完整示例。内容从 list 和链表这类线性结构开始逐步走到二叉树、图再覆盖排序、搜索、动态规划和贪心算法基本就是 Python 算法入门和笔试面试的核心范围。适合正在准备校招笔试的应届生、想系统补数据结构基础的开发者以及被链表指针和递归绕晕的初学者。它不是一本必须从头啃到尾的教材按章节跳着看、配着 LeetCode 题练吸收效率会高很多。2. 数组与链表Python 线性结构的实现与选型逻辑2.1 list 索引、插入、删除时间成本怎么记Python 内置 list 是大多数人接触到的第一种“数组”。讲义用arr [1, 2, 3]一行代码说明数组的创建后续用 append、insert、del 和下标赋值演示基本操作。这里要提醒一个很多人忽略的事实list 底层是连续内存的动态数组按下标取元素是 O(1)但插入或删除元素时插入点之后的所有元素都要整体移位所以头部插入和删除都是 O(n)。数据量只有几千条时毫无察觉一旦上到几万条记录还频繁在头部操作性能就会急剧退化。arr [1, 2, 3] arr.append(4) # 尾部追加均摊 O(1) arr.insert(0, 0) # 头部插入O(n)所有元素后移一位 del arr[0] # 头部删除O(n)所有元素前移一位 arr[1] 9 # 下标修改O(1) print(arr) # 最终输出 [1, 9, 3, 4]这段代码覆盖了 list 最常用的四类操作。append 尾部追加在大多数情况下不会触发扩容均摊复杂度按 O(1) 理解insert 指定位置插入后该位置之后的元素要依次后移del 的删除逻辑同样涉及元素整体迁移只有下标赋值是真正意义上的 O(1)。另外list 的扩容机制值得注意当容量不足时Python 会分配更大的内存空间并把旧数据整体复制过去。虽然均摊开销不大但如果你事先知道数据规模直接用[None] * n预分配列表可以避免中途反复扩容造成的额外消耗这在处理大批量数据时体感差异很明显。2.2 手写 ListNode节点、指针和插入删除链表在 Python 里没有内置实现但面试笔试十有八九会考。讲义定义了一个最基础的单链表节点类这里建议把它当成模板背下来class ListNode: def __init__(self, val0, nextNone): self.val val # 数据域存当前节点值 self.next next # 指针域指向下一个节点有了节点类创建三个节点的链表只需要连续赋值head ListNode(1) head.next ListNode(2) head.next.next ListNode(3)head 指向第一个节点节点 1 的 next 指向节点 2节点 2 的 next 指向节点 3。链表的物理内存并不连续每个节点靠 next 指针串起来所以插入和删除不需要移动其他元素理论上时间复杂度是 O(1)——前提是你已经拿到要操作位置的前一个节点。这个前提条件很关键实际写代码时为了“找到前一个节点”往往需要先遍历 O(n) 一次整体代价并没有理论看起来那么美好。插入操作是我见过新手翻车最多的地方。比如在节点 2 之前插入新节点 4正确顺序是先让新节点 4 的 next 指向节点 2再让节点 1 的 next 指向新节点 4。顺序一旦反了链表后半段就再也找不回来。new_node ListNode(4) new_node.next head.next # 先接4 的 next 指向原来的节点 2 head.next new_node # 再断1 的 next 指向 4删除操作的核心思路同样围绕“前一个节点”展开把被删节点前一个节点的 next 直接跳过它指向被删节点的 next这个节点就被摘除了。链表指针操作的通用口诀只有一句话先接好新链条再断开旧链条。把这个顺序刻进肌肉记忆绝大多数指针 bug 都可以避免。2.3 数组 vs 链表选型要看真实读写模式学习数据结构时最容易被忽略的问题是“选型”。很多初学者背下了“数组查得快、链表改得快”但实际工程里选哪个要看你真实的读写模式。维度list动态数组单链表按下标访问O(1)list 底层连续内存O(n)要沿 next 逐个找尾部插入/删除O(1) 均摊需要先找到尾节点O(n)头部插入/删除O(n)整体移位O(1)改头指针即可中间插入O(n)移位可能扩容O(1)拿到前驱节点后额外内存预留容量可能浪费每个节点多存一个 next 指针缓存友好度高连续内存低节点分散真实项目里如果数据量不大且操作集中在尾部list 是无脑选择如果业务场景明确需要频繁在头部插入删除比如实现一个 LRU 缓存或者维护一个待办队列链表结构才真正发挥价值。还有一个常见误区Java 里 LinkedList 看着是链表但遍历性能通常比 ArrayList 差不少因为节点分散在内存各处缓存命中率低。这个现象在 Python 里同样存在只是内置没有 LinkedList需要自己实现。所以选型时不要只盯着大 O 复杂度要结合数据量和操作频率一起看。3. 二叉树与图遍历顺序与存储表示怎么选3.1 二叉树节点结构与三种遍历写法二叉树是递归结构的最佳载体。讲义给出的节点类非常干净每个节点包含数据域、左子指针和右子指针class Node: def __init__(self, data): self.data data # 节点值 self.left None # 左子节点指针 self.right None # 右子节点指针创建一棵简单的二叉树就是逐层设置子节点。比如根节点为 1左子为 2右子为 3那么代码为root Node(1) root.left Node(2) root.right Node(3)二叉树的遍历是面试的高频考点。前序、中序、后序三种遍历方式的差别只在访问根节点的时机理解这一点比死记代码更有用。以下代码把三种遍历写到一起对照def preorder(tree): if tree is not None: print(tree.data) # 前序先访问根 preorder(tree.left) preorder(tree.right) def inorder(tree): if tree is not None: inorder(tree.left) print(tree.data) # 中序左 - 根 - 右 inorder(tree.right) def postorder(tree): if tree is not None: postorder(tree.left) postorder(tree.right) print(tree.data) # 后序先访问左右再访问根三种遍历的递归结束条件都是if tree is not None递归深度取决于树的高度。对中序遍历来说一个关键性质是对二叉搜索树做中序遍历输出结果一定是递增序列。这个性质可以直接用来验证一棵树是不是合法的二叉搜索树比你自己手写判断逻辑要稳得多。3.2 二叉搜索树O(log n) 查找的前提条件二叉搜索树BST的每个节点都满足一个约束左子树所有节点的值都小于当前节点右子树所有节点的值都大于当前节点。有了这个约束查找时每次比较都可以放弃一侧子树把搜索范围缩小一半理想情况下查找、插入、删除都能达到 O(log n)。def search_bst(root, target): if root is None: return None if root.data target: return root if target root.data: return search_bst(root.left, target) # 小于当前值去左子树 return search_bst(root.right, target) # 大于当前值去右子树这个递归过程的终止条件有两个一是找到目标节点二是走到空节点。很多人容易忽略 BST 查找高效的真正前提——树必须保持平衡。如果插入顺序是 [1, 2, 3, 4, 5]生成的 BST 会退化成一条单链表查找复杂度直接变成 O(n)。所以实务中一般不会直接用裸 BST而是用 AVL 树或红黑树这类带自平衡机制的变体。Python 内置的 dict 底层虽然是对哈希表做冲突处理但它的效率和 BST 的平衡思想本质上都源于“减少无谓比较”这个核心目标。3.3 邻接矩阵还是邻接表看图密度说话图是二叉树之后最重要的非线性结构。讲义里提到了两种标准表示法邻接矩阵和邻接表。很多初学者在这两种表示之间反复纠结其实选型标准很直接——看图的稀疏程度。邻接矩阵用二维数组存边关系matrix[i][j]为 1 表示 i 到 j 有边。判断两个节点是否相邻是 O(1)非常快但空间是 O(V²)。如果图有 10000 个节点邻接矩阵就需要 1 亿个元素的存储太浪费。邻接表则为每个节点维护一个相邻节点列表总空间是 O(V E)。# 邻接表表示用字典存储key 是节点value 是相邻节点列表 graph { A: [B, C], B: [A, D], C: [A], D: [B] }实际操作中我一般这样判断如果图的边数量接近 V² 数量级稠密图用邻接矩阵因为判断任意两点连通性的场景多矩阵更直接如果边数量接近 V 数量级稀疏图用邻接表省空间且遍历邻居节点更快。另外带权图不要用 0/1 存矩阵直接把权重值放进矩阵元素即可邻接表则在每个邻居节点上追加权重字段。图相关的面试题里最常考的是 BFS 和 DFS两者的区别只在“用队列还是用栈”这一层而队列与栈正好对应前面章节的基本数据结构基础打不牢就会在这些地方卡壳。4. 排序搜索与动态规划四类算法的落地边界4.1 冒泡、选择、插入O(n²) 家族什么时候够用排序算法是数据结构必考内容但面试中真正手写冒泡的机会并不多。讲义里把冒泡、选择、插入三种算法归类到了 O(n²) 复杂度这几兄弟的适用场景高度集中在“数据规模小”和“实现简单优先”这两类场景。冒泡排序通过相邻元素反复交换把最大值“冒”到最后代码写起来直观但交换次数最多选择排序每轮找到剩余元素中的最小值交换次数比冒泡少插入排序则更像打牌时理牌的过程把新元素插到已排序序列的正确位置。def insertion_sort(arr): for i in range(1, len(arr)): key arr[i] # 当前要插入的元素 j i - 1 while j 0 and arr[j] key: arr[j 1] arr[j] # 比 key 大的元素往右挪 j - 1 arr[j 1] key # 找到插入位置插入排序在三种算法中有一个独特优势当数组近乎有序时它的实际执行次数接近 O(n)。这个特性让它成为很多混合排序算法的基础组件比如 Timsort——Python 内置 sort 的底层算法——就大量用到了插入排序的思路。所以在工程里如果数据量在百级左右插入排序完全可以无脑用没必要上复杂算法。真正的分水岭在数据量过万以后O(n²) 和 O(n log n) 的差距会被指数级放大。4.2 快速排序和二分搜索分治思想的两个代表快速排序是分治思想的经典落地。它的流程是选一个基准元素把数组分成小于基准和大于基准的两部分再对两部分递归排序。平均时间复杂度 O(n log n)常数因子很小所以工程上很流行。但新手实现时最容易踩的坑就是基准选择不当——如果每次基准都取到最大或最小值复杂度直接退化成 O(n²)。def quicksort(arr): if len(arr) 1: return arr pivot arr[len(arr) // 2] # 取中间位置元素作为基准 left [x for x in arr if x pivot] middle [x for x in arr if x pivot] right [x for x in arr if x pivot] return quicksort(left) middle quicksort(right)这个实现说明分治逻辑最直观的样子分解、递归、合并三步。代码可读性很好但空间开销大每层递归都新建列表。面试时如果要求原地排序需要用双指针交换的写法这也是考察点之一。二分搜索和快速排序共享分治思想每轮比较把范围砍半复杂度 O(log n)。它有一个硬性前提——数据必须有序这个前提初学者经常漏掉。def binary_search(arr, target): low, high 0, len(arr) - 1 while low high: mid (low high) // 2 if arr[mid] target: return mid # 找到目标返回下标 elif arr[mid] target: low mid 1 # 目标在右半区 else: high mid - 1 # 目标在左半区 return -1 # 没找到二分搜索的边界条件值得细抠while low high能不能用替代不能因为当 low high 时mid 可能恰好就是目标值。low mid 1和high mid - 1为什么要跳过一个位置因为 mid 已经比较过了不跳过会导致死循环。这两处细节就是二分搜索最常见的两个考点。4.3 背包动态规划与贪心状态转移怎么写、何时不能贪动态规划是很多人的老大难但讲义给出的背包问题版本很能说明问题。0-1 背包问题要求每个物品最多选一次目标是总重量不超过背包容量的前提下总价值最大。核心是定义 dp[i][j]前 i 个物品在容量为 j 时的最大价值。状态转移方程就一句话——放还是不放当前物品。def knapsack(weights, values, capacity): n len(weights) # dp[i][j] 表示前 i 个物品在容量 j 下的最大价值 dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): # 逐个考虑物品 for j in range(1, capacity 1): # 逐个容量 if weights[i - 1] j: dp[i][j] max( dp[i - 1][j], # 不放当前物品 dp[i - 1][j - weights[i - 1]] values[i - 1] # 放当前物品 ) else: dp[i][j] dp[i - 1][j] # 放不下只能不放 return dp[n][capacity]这个 dp 表是二维的行代表已经考虑过的物品数列代表背包容量。状态转移只依赖上一行所以很多优化版本会把二维表压成一维但这个优化必须从后往前遍历容量否则物品会被重复使用。讲义里的版本是最稳妥的先把二维结构弄清楚再看一维优化就不会乱。贪心算法和动态规划的关系很容易混淆。贪心的核心是每一步都取当前最优不做回退所以它必须满足“局部最优能推出全局最优”。典型的反例就是背包问题按单位价值从高到低贪心选择在 0-1 背包里很可能得不到最优解因为物品不可分割时贪心选择会留下不连续的剩余容量。但分数背包物品可以分割用贪心就是最优。判断策略时只有一个标准能否找到一个反例推翻贪心选择。找不到才可用找到就是动态规划的领域。5. 数据结构实操避坑四个翻车现场的复盘5.1 链表插入后新节点“消失”了现象按直觉写了 head.next 指向新节点结果链表后半段全丢了遍历只能输出前半截。原因插入顺序错了。先把 head.next 指向新节点原来的下一个节点就失去引用链表断链。链表插入的正确逻辑是先让新节点的 next 指向旧节点再修改前一个节点的 next 指向新节点。解决强制自己按“先接后断”的顺序写代码。如果没有把握画一张三个节点的指针图再动手。凡是涉及链表指针修改就先在心里过一遍哪个节点的 next 会被覆盖被覆盖前是否已经保存了后继节点这两问能挡住 90% 的链表 bug。5.2 二分搜索返回 -1但数据里明明有目标值现象对一组数据调用二分搜索目标值确实存在但函数返回 -1。原因最常见的原因是传入的数据没有排序。二分搜索的前提是数组有序它通过比较中间值和目标值来缩小范围如果数据无序中间值的大小关系无法代表左右两半的整体情况搜索就会漏掉目标。解决调用二分搜索前先确认数据有序。如果数据本身无序但需要反复搜索有两种思路先排序再搜索排序开销 O(n log n) 摊到多次搜索后被均摊或者改用哈希表存储直接用 set 或 dict 判断存在性O(1) 查找代价是占用额外内存。还有一个小坑是数据量极大时(low high) // 2存在整数溢出风险更稳的写法是low (high - low) // 2。Python 的 int 不会溢出但其他语言里这个坑真实存在。5.3 递归遍历二叉树时报 RecursionError现象二叉树深度只有几百层但前序递归遍历直接报 RecursionError程序崩溃。原因Python 默认的递归深度上限大约在 1000 层左右。二叉树的递归深度等于树的高度极端情况下比如退化成链表深度可以轻松超过这个上限。解决先在系统层面调高递归上限用sys.setrecursionlimit(10000)临时解决更根本的方法是改成迭代写法前序遍历用栈模拟递归中序和后序也可以显式维护遍历状态。import sys sys.setrecursionlimit(10000) def preorder_iter(root): if root is None: return stack [root] while stack: node stack.pop() # 弹出一个节点 print(node.data) # 访问节点 if node.right: stack.append(node.right) # 右子树先入栈 if node.left: stack.append(node.left) # 左子树后入栈先被弹出栈模拟的版本虽然代码看起来没有递归简洁但不会受递归深度限制而且这个写法还能延伸到树的层序遍历——把栈换成队列就是 BFS。递归有递归的美迭代有迭代的稳工程里两者互补。5.4 动态规划 dp 表边界条件漏写现象背包问题的结果总比预期小或者下标访问直接越界。原因二维 dp 表初始化时容量和物品索引的对应关系很容易错。比如把 dp 表建成了 (n) 行但循环里访问了 dp[n]或者容量循环从 0 开始但计算时使用了 j - 1 作为索引导致越界。解决初始化 dp 表时行数定为 n1列数定为 capacity1让 0 行和 0 列专门承担空状态。循环时第 i 个物品对应 weights[i-1]容量 j 从 1 遍历到 capacity。每次写完动态规划代码先跑两个边界用例容量为 0、物品数量为 0再跑一个只有一件物品的最小用例可以避免多数初始化错误。6. 验证掌握度三道练习题与一个复盘习惯光看不练数据结构永远学不扎实。如果想把这份讲义的内容真正变成自己的东西我一般会拿三个 LeetCode 题目来验证学习成果反转链表206 题验证链表指针操作二叉树的最大深度104 题验证递归和 DFS爬楼梯70 题验证基础动态规划。这三道题难度都不高但分别覆盖了线性结构、树形结构、动态规划三大核心模块做出来不等于掌握关键是做错之后能定位到具体章节去回看讲义。设计练习时注意——先把爬楼梯的状态转移方程写出来再看代码先自己实现链表插入再对照讲义的顺序。这种“先盲写、后对照”的方式比直接看代码有效得多因为面试考的就是你的第一反应而不是记忆能力。复盘习惯比做题数量更重要。我自己整理了一套简单的流程每道做错的题记录三件事——错在哪一步、知识点盲区是什么、对应的讲义章节在哪。比如链表插入顺序错了就在笔记里写“ListNode 插入先接后断对应讲义第 2 章”动态规划边界漏了就写“dp 表行数为 n1容量循环从 1 开始对应讲义第 5 章”。这样积累两周后薄弱环节会非常清楚。从那以后我每次刷完一个算法专题都会强制自己用“盲写一遍 对照讲义 记录盲区”这个流程走一遍效果比单纯刷题好很多。这份讲义的覆盖面足够广但再好的资料也需要你动手敲一遍才能真正印在脑子里。希望帮到你。本文还有配套的精品资源点击获取