企业官网建设流程全解析

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) {} // 构造函数 };

/* C：typedef 结构体 + 手工构造函数 */ 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; }

/* Rust：Rc<RefCell<_>> 实现共享可变引用 */ use std::rc::Rc; use std::cell::RefCell; #[derive(Debug)] struct ListNode { val: i32, // 节点值 next: Option<Rc<RefCell<ListNode>>>, // 指向下一节点的指针 }

三、链表初始化：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 中初始化脚本的curInstr=3（第 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与n1（n1 = n0.next）之间插入新节点P，只需改写两个引用，时间复杂度 O(1)：

插入前：n0 ──next──> n1 插入后：n0 ──next──> P ──next──> n1

1. n1 = n0.next：暂存n0原本的后继，避免被覆盖丢失；
2. P.next = n1：新节点指向n0的原后继；
3. n0.next = P：n0改指新节点，插入完成。

教程正文特别指出的对比：向数组中插入元素的时间复杂度是 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 行）给出了完整的性能对照表：

由于两者存储策略相反，其性质与操作效率也大体相反：数组「访问快、增删慢」，链表「增删快、访问慢」。本文四个 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#code=<URL编码源码>&cumulative=false&curInstr=<指令编号>&heapPrimitives=nevernest&mode=display&py=311&rawInputLstJSON=[]&textReferences=false，其中py=311表示 Python 3.11 运行时，mode=display为显示模式，curInstr是定格到的指令序号（本文档中 insert 为 39，其余三个为 34）；页面内可按步进按钮逐帧执行，堆内存中的对象框与引用箭头会随之更新。

本地运行完整示例：仓库根目录下 Python 版示例可直接执行（依赖同目录modules包中的ListNode与print_linked_list，后者定义于 print_util.py）：

python 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 的Rc<RefCell<_>>、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