Hello 算法单链表四大核心操作的 PythonTutor 逐帧可视化解析insert/remove/access/find【免费下载链接】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 算法仓库中俄语版 PythonTutor 可视化脚本ru/codes/pythontutor/chapter_array_and_linkedlist/linked_list.md展开。该文件将单链表的四大核心操作——节点插入insert、节点删除remove、按索引访问access、按值查找find——编码为四个可在 PythonTutor 中逐帧step-by-step播放的可视化链接。读完后你将掌握单链表的节点内存结构与引用改写规则、四个操作的 O(1)/O(n) 时间复杂度来源、如何解码并运行仓库中的 PythonTutor 可视化脚本以及链表相对数组在存储与操作上的本质差异。一、文件定位PythonTutor 可视化目录的角色在 Hello 算法仓库中教程正文位于ru/docs/chapter_array_and_linkedlist/linked_list.md俄语版《Связный список》章节其中通过形如[file]{linked_list}-[func]{insert}的占位标记引用可视化脚本而真正的可视化载体就是本文档ru/codes/pythontutor/chapter_array_and_linkedlist/linked_list.md。仓库按「章节 → 文件-类-函数」的三级命名组织了codes/pythontutor/下的全部脚本例如回溯章节的ru/codes/pythontutor/chapter_backtracking/下有 10 个对应的.md脚本文件。该文件共包含 4 段内容每段由两部分组成一行注释标记!-- [file]{linked_list}-[class]{}-[func]{函数名} --标识对应linked_list文件、insert/remove/access/find四个函数一行https://pythontutor.com/render.html#code...链接URL 编码后的code参数即为完整的可执行 Python 脚本curInstr参数则定位到某条指令的逐帧播放位置。这四个脚本与仓库可运行实现 linked_list.py 中的函数逐行对应仅注释语言不同insert对应第 14–18 行、remove对应第 21–28 行、access对应第 31–37 行、find对应第 40–48 行。因此可以把该 PythonTutor 文件理解为把linked_list.py的四个函数拆成四段独立、自带驱动代码Driver Code的最小可视化程序。二、单链表的数据结构与内存特性在展开四个操作之前先回顾节点定义——这也是四个 PythonTutor 脚本共同的前置代码。解码 URL 中的code参数后每个脚本都以同一个节点类开头class ListNode: Класс узла связанного списка # 链表节点类 def __init__(self, val: int): self.val: int val # 节点值 self.next: ListNode | None None # 指向后继节点的引用其结构与 linked_list.py 引用的公共模块 list_node.py 中的ListNode完全一致val存值、next存后继引用。根据 linked_list.md 正文的论述内存是所有程序的共享资源复杂运行环境中的空闲内存块往往散布在地址空间各处数组要求整块连续内存大数组可能根本分不出连续空间这正是链表灵活性的价值所在。链表的基本单位是节点node每个节点含两部分节点值val与指向下一个节点的引用next引用存储的是下一节点的内存地址由它可以跳到下一个节点。链表的节点可以散布在内存各处地址不必连续。第一个节点称头节点head最后一个称尾节点tail尾节点指向空值——Java 中为null、C 中为nullptr、Python 中为None在 C、C、Go、Rust 等指针语言中引用需替换为指针pointer。由于每个节点都额外携带一个引用同等数据量下链表比数组占用更多内存。多语言节点定义的对照摘自上述俄语教程正文可跨文件比对实现细节/* C结构体节点 */ struct ListNode { int val; // 节点值 ListNode *next; // 指向下一节点的指针 ListNode(int x) : val(x), next(nullptr) {} // 构造函数 };/* Ctypedef 结构体 手工构造函数 */ typedef struct ListNode { int val; // 节点值 struct ListNode *next; // 指向下一节点的指针 } ListNode; ListNode *newListNode(int val) { ListNode *node; node (ListNode *) malloc(sizeof(ListNode)); node-val val; node-next NULL; return node; }/* RustRcRefCell_ 实现共享可变引用 */ use std::rc::Rc; use std::cell::RefCell; #[derive(Debug)] struct ListNode { val: i32, // 节点值 next: OptionRcRefCellListNode, // 指向下一节点的指针 }三、链表初始化1 → 3 → 2 → 5 → 4四个操作的演示都基于同一条样例链表1 - 3 - 2 - 5 - 4。初始化分两步先创建 5 个独立节点再逐一改写next引用把它们串起来# 初始化链表 1 - 3 - 2 - 5 - 4 # 初始化各个节点 n0 ListNode(1) n1 ListNode(3) n2 ListNode(2) n3 ListNode(5) n4 ListNode(4) # 构建节点之间的引用 n0.next n1 n1.next n2 n2.next n3 n3.next n4与 linked_list.py 的驱动代码第 52–64 行一致其中n4.next保持None即尾节点指向空。需要强调的一个概念通常用头节点来代表整条链表。例如上面的链表就可以整体记作n0——这与数组不同数组是一条整体变量而链表是众多独立节点对象靠引用串成的集合。初始状态在 PythonTutor 中对应的逐帧快照可参见 linked_list.md 中初始化脚本的curInstr3第 3 条指令处定格画面。在 PythonTutor 中每个节点的val、next以及各局部变量n0…n4都会以独立对象框的形式画在堆内存区引用箭头直接可见——这正是「节点散布在内存中、靠引用连接」这一抽象概念最直观的呈现方式。四、操作一insert 插入节点O(1)4.1 可视化脚本解码ru/codes/pythontutor/chapter_array_and_linkedlist/linked_list.md第 7–8 行的注释标记为[file]{linked_list}-[class]{}-[func]{insert}其 URL 解码后的完整脚本为class ListNode: Класс узла связанного списка # 链表节点类 def __init__(self, val: int): self.val: int val # 节点值 self.next: ListNode | None None # 指向后继节点的引用 def insert(n0: ListNode, P: ListNode): Вставить узел P после узла n0 в связанном списке # 在链表节点 n0 之后插入节点 P n1 n0.next P.next n1 n0.next P Driver Code if __name__ __main__: # 初始化链表 / 初始化各个节点 n0 ListNode(1) n1 ListNode(3) n2 ListNode(2) n3 ListNode(5) n4 ListNode(4) # 构建节点之间的引用 n0.next n1 n1.next n2 n2.next n3 n3.next n4 # 插入节点 p ListNode(0) insert(n0, p)该函数与 linked_list.py 的insert实现完全相同。4.2 引用改写的三步曲在相邻两节点n0与n1n1 n0.next之间插入新节点P只需改写两个引用时间复杂度 O(1)插入前n0 ──next── n1 插入后n0 ──next── P ──next── n1n1 n0.next暂存n0原本的后继避免被覆盖丢失P.next n1新节点指向n0的原后继n0.next Pn0改指新节点插入完成。教程正文特别指出的对比向数组中插入元素的时间复杂度是 O(n)需要整体搬移元素数据量大时链表明显更优。在 PythonTutor 中逐帧播放这三条赋值语句可以清楚看到n0.next的箭头先「断开」再「重新指向」P对象框的全过程。五、操作二remove 删除节点O(1)5.1 可视化脚本解码第 10–11 行标记[func]{remove}URL 解码后def remove(n0: ListNode): Удалить первый узел после узла n0 в связанном списке # 删除链表节点 n0 之后的首个节点 if not n0.next: return # n0 - P - n1 P n0.next n1 P.next n0.next n1 Driver Code if __name__ __main__: n0 ListNode(1) n1 ListNode(3) n2 ListNode(2) n3 ListNode(5) n4 ListNode(4) n0.next n1 n1.next n2 n2.next n3 n3.next n4 # 删除节点 remove(n0)注意接口语义删除的不是n0本身而是n0之后的首个节点即P——这与 LeetCode「删除链表中节点」的常见约束一致没有前驱引用时无法真正删除自己只能操作后继。该定义与 linked_list.py 第 21–28 行一致。5.2 只需要改写一个引用删除前n0 ──next── P ──next── n1 删除后n0 ──────────────────── n1 P 被摘除前置判断if not n0.next: return保证n0有后继避免对None取.next报错P n0.next定位待删节点n1 P.next记下其后继n0.next n1一跳越过P完成删除仅一次引用赋值O(1)。教程正文补充了一个容易被误解的细节删除完成后P对象本身仍指向n1但从链表头部出发已无法遍历到P即P事实上已不属于这条链表在 GC 语言中等待回收。对比 C 语言实现可以看到手动内存管理的差异linked_list.c 中同逻辑的函数因stdio.h已占用remove一词而命名为removeItem并在改写引用后显式free(P)释放内存——Python 版则交给垃圾回收器无需也无法手动释放。六、操作三access 按索引访问O(n)6.1 可视化脚本解码第 13–14 行标记[func]{access}URL 解码后def access(head: ListNode, index: int) - ListNode | None: Доступ к узлу связанного списка по индексу index # 访问链表中索引为 index 的节点 for _ in range(index): if not head: return None head head.next return head Driver Code if __name__ __main__: # 同前初始化 1 - 3 - 2 - 5 - 4 n0 ListNode(1); n1 ListNode(3); n2 ListNode(2) n3 ListNode(5); n4 ListNode(4) n0.next n1; n1.next n2; n2.next n3; n3.next n4 # 访问节点 node access(n0, 3) print(Значение узла по индексу 3 в связанном списке {}.format(node.val))与 linked_list.py 第 31–37 行一致。6.2 为什么是 O(n)数组下标访问是 O(1)——地址可以直接由「基址 下标 × 元素大小」算出而链表没有这种寻址能力access必须从头节点出发逐步遍历访问第i个节点要做i - 1次head head.next迭代故时间复杂度为 O(n)。驱动代码取index 3对链表1 - 3 - 2 - 5 - 4走 3 步后命中值为5的n3节点。边界处理也值得注意for循环内部每次前进前检查if not head: return None当index越界走过头时head已为None时安全返回None而不是抛异常。在 PythonTutor 中逐帧观察可以数出指针恰好移动了 3 次——这是把 O(n) 这个抽象复杂度变成「看得见的步数」的最佳方式。七、操作四find 按值查找O(n)7.1 可视化脚本解码第 16–17 行标记[func]{find}URL 解码后def find(head: ListNode, target: int) - int: Найти первый узел со значением target в связанном списке # 在链表中查找值为 target 的首个节点 index 0 while head: if head.val target: return index head head.next index 1 return -1 Driver Code if __name__ __main__: # 同前初始化 1 - 3 - 2 - 5 - 4 n0 ListNode(1); n1 ListNode(3); n2 ListNode(2) n3 ListNode(5); n4 ListNode(4) n0.next n1; n1.next n2; n2.next n3; n3.next n4 # 查找节点 index find(n0, 2) print(Индекс узла со значением 2 в связанном списке {}.format(index))与 linked_list.py 第 40–48 行一致。7.2 线性查找的完整闭环find是典型线性查找从头到尾顺序扫描返回第一个等于target的节点索引扫描完仍无匹配则返回-1未找到的约定值。驱动代码查找target 2扫描1 → 3 → 2后在第 2 个位置命中返回2。与access的结构对比有助于理解两种遍历范式access用for _ in range(index)固定步数走位、越界判空find用while head:以「是否到达尾部」为循环条件、以「是否命中目标」为提前退出条件——两者都是 O(n) 线性遍历但退出逻辑不同。C 语言版 linked_list.c 的find与 Python 版逐行同构可作跨语言对照。八、数组 vs 链表效率对照综合四个操作教程正文linked_list.md 第 462–475 行给出了完整的性能对照表数组链表存储方式连续内存区域分散内存区域容量扩展长度不可变灵活扩展内存效率元素占内存少但可能有空间浪费元素占内存更多访问元素O(1)O(n)添加元素O(n)O(1)删除元素O(n)O(1)由于两者存储策略相反其性质与操作效率也大体相反数组「访问快、增删慢」链表「增删快、访问慢」。本文四个 PythonTutor 脚本恰好把这张表的每一格都变成了可逐帧验证的动画insert/remove定格在两三次引用赋值上O(1)access/find则是指针沿引用链一格一格移动O(n)。九、三种常见链表类型教程正文还归纳了三种常见链表形态对应图linkedlist_common_types.png单链表本文四个脚本所演示的形态。节点含值与后继引用头节点为起点尾节点指向None。循环链表让单链表尾节点指回头节点首尾相接此时任意节点都可视为头节点。双链表节点额外保存指向前驱节点的引用可双向遍历代价是更多内存。Python 版节点定义为class ListNode: Класс узла двусвязного списка # 双链表节点类 def __init__(self, val: int): self.val: int val # 节点值 self.next: ListNode | None None # 指向下一节点的引用 self.prev: ListNode | None None # 指向前驱节点的引用十、链表与 PythonTutor 脚本的典型应用单链表常用作栈、队列、哈希表、图的底层结构栈和队列增删只发生在链表同一端时表现为 LIFO栈一端插入另一端删除时表现为 FIFO队列。仓库中codes/python/chapter_stack_and_queue/下的linkedlist_stack.py、linkedlist_queue.py等文件正是基于链表的实现。哈希表拉链法chaining是哈希冲突处理的主要手段之一冲突元素被放入同一条链表中。图邻接表表示法中每个顶点对应一条链表链表元素即其邻接顶点。仓库codes/python/chapter_graph/提供了对应实现。双链表则适用于需要快速访问前驱与后继的场景红黑树/B 树中对父节点的访问、浏览器的前进/后退历史、LRU 缓存算法需快速定位最久未使用节点并快速增删。循环链表常用于需要循环操作的场景如操作系统的轮转调度Round-Robin与音视频播放器的环形缓冲。十一、如何运行与复现运行 PythonTutor 可视化直接在浏览器中打开 linked_list.md 中的四个链接即可。链接格式固定为https://pythontutor.com/render.html#codeURL编码源码cumulativefalsecurInstr指令编号heapPrimitivesnevernestmodedisplaypy311rawInputLstJSON[]textReferencesfalse其中py311表示 Python 3.11 运行时modedisplay为显示模式curInstr是定格到的指令序号本文档中 insert 为 39其余三个为 34页面内可按步进按钮逐帧执行堆内存中的对象框与引用箭头会随之更新。本地运行完整示例仓库根目录下 Python 版示例可直接执行依赖同目录modules包中的ListNode与print_linked_list后者定义于 print_util.pypython codes/python/chapter_array_and_linkedlist/linked_list.py驱动代码linked_list.py 第 52–85 行依次演示了初始化打印、insert(n0, p)插入值为 0 的节点、remove(n0)删除n0后继、access(n0, 3)访问索引 3、find(n0, 2)查找值 2输出与四个可视化脚本的终态一一对应。C 语言版 linked_list.c 通过各章节 CMakeLists 参与构建codes/c/CMakeLists.txt其输出行为与 Python 版相同且演示了free(P)手动释放与freeMemoryLinkedList(n0)整链释放的内存管理。同主题的多语言对照仓库为同一算法提供了 14 种语言的实现PythonTutor 脚本对应的四个函数在 linked_list.cpp、linked_list.java、linked_list.go、linked_list.ts 等文件中均有一一对应版本可作为跨语言引用/指针语义差异如 Rust 的RcRefCell_、C 的free的对照阅读材料。俄语版教程正文与图片位于 ru/docs/chapter_array_and_linkedlist/linked_list.md中文简繁体与英文版对应路径分别为docs/chapter_array_and_linkedlist/、en/docs/chapter_array_and_linkedlist/、zh-hant/docs/chapter_array_and_linkedlist/。小结ru/codes/pythontutor/chapter_array_and_linkedlist/linked_list.md以 4 段 PythonTutor 脚本承载了单链表的全部核心操作演示insert两次引用赋值完成 O(1) 插入remove一次引用赋值完成 O(1) 删除access与find则以线性遍历揭示了 O(n) 访问的本质。配合仓库中 linked_list.py 的可运行实现、list_node.py 的节点定义、C 语言的内存管理对照以及教程正文的复杂度对照表这份文件构成了一条从「内存模型 → 引用改写 → 复杂度结论」的完整学习链路。【免费下载链接】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），仅供参考