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, val=0, next=None): 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 是无脑选择；如果业务场景明确需要频繁在头部插入删除，比如实现一个 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 表时，行数定为 n+1，列数定为 capacity+1，让 0 行和 0 列专门承担空状态。循环时第 i 个物品对应 weights[i-1]，容量 j 从 1 遍历到 capacity。每次写完动态规划代码，先跑两个边界用例：容量为 0、物品数量为 0，再跑一个只有一件物品的最小用例，可以避免多数初始化错误。

6. 验证掌握度：三道练习题与一个复盘习惯

光看不练，数据结构永远学不扎实。如果想把这份讲义的内容真正变成自己的东西，我一般会拿三个 LeetCode 题目来验证学习成果：反转链表（206 题）验证链表指针操作，二叉树的最大深度（104 题）验证递归和 DFS，爬楼梯（70 题）验证基础动态规划。这三道题难度都不高，但分别覆盖了线性结构、树形结构、动态规划三大核心模块，做出来不等于掌握，关键是做错之后能定位到具体章节去回看讲义。

设计练习时注意——先把爬楼梯的状态转移方程写出来，再看代码；先自己实现链表插入，再对照讲义的顺序。这种“先盲写、后对照”的方式比直接看代码有效得多，因为面试考的就是你的第一反应而不是记忆能力。

复盘习惯比做题数量更重要。我自己整理了一套简单的流程：每道做错的题记录三件事——错在哪一步、知识点盲区是什么、对应的讲义章节在哪。比如链表插入顺序错了，就在笔记里写“ListNode 插入：先接后断，对应讲义第 2 章”；动态规划边界漏了，就写“dp 表行数为 n+1，容量循环从 1 开始，对应讲义第 5 章”。这样积累两周后，薄弱环节会非常清楚。

从那以后，我每次刷完一个算法专题，都会强制自己用“盲写一遍 + 对照讲义 + 记录盲区”这个流程走一遍，效果比单纯刷题好很多。这份讲义的覆盖面足够广，但再好的资料也需要你动手敲一遍才能真正印在脑子里。希望帮到你。

本文还有配套的精品资源，点击获取