Hello 算法仓库中的链表栈：用「头插法」实现 O(1) 入栈出栈的完整解析-育师

Hello 算法仓库中的链表栈：用「头插法」实现 O(1) 入栈出栈的完整解析

【免费下载链接】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-algo 仓库中「基于链表实现栈」这一主题：以 ru/codes/pythontutor/chapter_stack_and_queue/linkedlist_stack.md 中的可视化代码为核心，结合仓库各语言源码，完整讲解 LIFO 语义、头插法入栈与头部删除出栈的底层机制、LinkedListStack类的逐方法实现、驱动代码的运行结果，以及 Python / C++ / Rust 三种实现的源码级差异。读完本文后，你将能够独立用链表手写一个功能完整的栈，并理解它与数组栈在性能与内存上的取舍。

一、主题定位：这个文档在仓库中对应什么

linkedlist_stack.md 是俄语版代码教程pythontutor目录下的一个可视化代码文件，服务于文档章节 ru/docs/chapter_stack_and_queue/stack.md 中「基于链表实现栈」一节。

该文件本身结构极简，由两部分组成：

文件头注释：标注文件名、创建时间（2024-01-05）与作者；
一条 Python Tutor 渲染链接：链接的#code=参数是一段 URL 编码的完整 Python 源码，内容为ListNode与LinkedListStack两个类的定义加上驱动代码（Driver Code），可直接粘贴到 Python Tutor 中逐步可视化执行。

文档头部的标签行[file]{linkedlist_stack}-[class]{linked_list_stack}-[func]{}是 mkdocs 构建系统的取码标记：文档页面（ru/docs/chapter_stack_and_queue/stack.md 第 379–381 行）通过该标记从真实源码文件 ru/codes/python/chapter_stack_and_queue/linkedlist_stack.py 中自动抽取LinkedListStack类注入页面。也就是说，本文展开的所有代码，都可以在仓库源码中找到逐行对应的实现，而非仅存在于可视化链接中。

二、栈的基本语义与操作复杂度

栈（Stack）是一种遵循 LIFO（后进先出，Last In First Out）逻辑的线性数据结构：只能在一端（栈顶）插入和删除元素。仓库文档中将其类比为一摞盘子——想拿走底部的盘子，必须先依次移走上面所有盘子。

LinkedListStack支持的六个方法及其时间复杂度如下（与 ru/docs/chapter_stack_and_queue/stack.md 的操作表格一致）：

方法	功能	时间复杂度
`push(val)`	将元素入栈（置于栈顶）	$O(1)$
`pop()`	弹出栈顶元素并返回	$O(1)$
`peek()`	查看栈顶元素但不弹出	$O(1)$
`size()`	返回栈中元素个数	$O(1)$
`is_empty()`	判断栈是否为空	$O(1)$
`to_list()`	序列化为普通列表以便打印	$O(n)$

所有核心操作的 $O(1)$ 复杂度正是「头插法」设计带来的：入栈、出栈都只发生在链表头部，无需遍历。

三、核心数据结构：头节点即栈顶

链表栈的关键设计决策只有一条：把链表的头节点当作栈顶（peek），尾节点当作栈底。

push(val)：等价于链表的头插——新建节点，令其next指向当前头节点，再把头指针移到新节点上；
pop()：等价于链表的删头——取出头节点的值，把头指针前移到下一个节点。

由于不维护尾指针，push/pop均不需要遍历链表，这保证了严格意义上的常数时间操作。

四、Python 实现逐段解析

以下内容与 linkedlist_stack.md 中解码后的代码完全一致，同时对应源码 ru/codes/python/chapter_stack_and_queue/linkedlist_stack.py。

4.1 节点定义与导入

from modules import ListNode # 仓库中定义于 ru/codes/python/modules/list_node.py

仓库提供的 ListNode 只有两个字段：

class ListNode: """Класс узла связного списка""" def __init__(self, val: int): self.val: int = val # 节点值 self.next: ListNode | None = None # 指向后继节点的引用

ru/codes/python/modules/init.py 将ListNode统一导出，因此各章代码都以from modules import ListNode的方式复用同一套节点定义。

4.2 类成员与构造（L14-L20）

class LinkedListStack: """Стек на основе связного списка""" def __init__(self): self._peek: ListNode | None = None # 头指针：指向栈顶节点，空栈为 None self._size: int = 0 # 栈内元素个数

两个私有成员即可覆盖全部状态：

_peek：链表头指针。之所以命名为_peek而非_head，是因为它同时兼任「栈顶」角色，直接读它的.val就是peek()的返回值；
_size：独立计数器。维护它可以让size()和is_empty()都不必遍历链表，保持 $O(1)$。

4.3 入栈：三步头插（L30-L35）

def push(self, val: int): """Поместить в стек""" node = ListNode(val) # ① 创建新节点 node.next = self._peek # ② 新节点指向当前栈顶 self._peek = node # ③ 头指针移到新节点 self._size += 1

这三行是链表头插的标准写法。顺序上第 ②、③ 步不可颠倒：若先执行self._peek = node，就会丢失对原栈顶的引用。

4.4 出栈与查看栈顶（L37-L48）

def pop(self) -> int: """Извлечь из стека""" num = self.peek() # 先取栈顶值（空栈时 peek 会抛 IndexError） self._peek = self._peek.next # 头指针前移，完成删头 self._size -= 1 return num def peek(self) -> int: """Доступ к верхнему элементу стека""" if self.is_empty(): raise IndexError("стек пуст") return self._peek.val

值得注意的设计点：

pop()通过先调用peek()实现空栈保护——对空栈执行pop()会抛出IndexError("стек пуст")，而不是让self._peek.next在None上触发属性错误；
Python 由垃圾回收器处理被摘除节点，因此pop()中没有显式的释放代码；这一点与 C++ 版本形成对照（见第六节）。

4.5 长度、判空与序列化（L22-L28, L50-L58）

def size(self) -> int: return self._size def is_empty(self) -> bool: return self._size == 0 def to_list(self) -> list[int]: """Преобразовать в список для вывода""" arr = [] node = self._peek while node: arr.append(node.val) node = node.next arr.reverse() # 链表顺序为 栈顶 -> 栈底，翻转后为 栈底 -> 栈顶 return arr

to_list()沿next指针从头走到尾，天然得到「栈顶在前」的顺序，所以最后需要arr.reverse()，让打印结果[1, 3, 2, 5, 4]以栈底元素 1 排在最左，符合人们看「一摞盘子」的直觉。

五、驱动代码与运行结果

驱动部分位于 linkedlist_stack.py，与可视化文档中的代码一致：

if __name__ == "__main__": stack = LinkedListStack() stack.push(1) stack.push(3) stack.push(2) stack.push(5) stack.push(4) print("Стек stack =", stack.to_list()) peek: int = stack.peek() print("Верхний элемент peek =", peek) pop: int = stack.pop() print("Извлеченный элемент pop =", pop) print("stack после извлечения =", stack.to_list()) size: int = stack.size() print("Длина стека size =", size) is_empty: bool = stack.is_empty() print("Пуст ли стек =", is_empty)

按 LIFO 语义逐步推演其运行结果：

步骤	操作	栈内状态（左=栈底，右=栈顶）	输出
1	`push(1) push(3) push(2) push(5) push(4)`	`[1, 3, 2, 5, 4]`	`Стек stack = [1, 3, 2, 5, 4]`
2	`peek()`	`[1, 3, 2, 5, 4]`	`Верхний элемент peek = 4`
3	`pop()`	`[1, 3, 2, 5]`	`Извлеченный элемент pop = 4`
4	`size()`	`[1, 3, 2, 5]`	`Длина стека size = 4`
5	`is_empty()`	`[1, 3, 2, 5]`	`Пуст ли стек = False`

最后弹出的 4 恰好是最后压入的元素，直观验证了「后进先出」：栈顶指针始终指向最后入栈者。

六、跨语言实现的源码对照

仓库为同一算法提供了 14 种语言实现（ru/codes/<lang>/chapter_stack_and_queue/linkedlist_stack.*），其中 Python 与可视化文档逐行对应。以 C++ 和 Rust 为例，可以看到同一个头插法设计在不同内存模型下的落地差异。

6.1 C++：显式内存管理

ru/codes/cpp/chapter_stack_and_queue/linkedlist_stack.cpp 中成员为ListNode *stackTop，push同样是三步头插：

void push(int num) { ListNode *node = new ListNode(num); node->next = stackTop; stackTop = node; stkSize++; } int pop() { int num = top(); ListNode *tmp = stackTop; stackTop = stackTop->next; delete tmp; // 手动释放被摘除节点 stkSize--; return num; }

与 Python 版的差异集中在三处：pop()中必须delete被摘除的节点；析构函数里遍历链表逐个释放（L21-L24）；top()对空栈抛出的异常类型是std::out_of_range而非 Python 的IndexError。此外，C++ 的toVector()利用已知长度做逆序回填，省去了 Python 版to_list()里的reverse()调用。

6.2 Rust：借用检查下的`Rc<RefCell>`写法

ru/codes/rust/chapter_stack_and_queue/linkedlist_stack.rs 中头指针类型为Option<Rc<RefCell<ListNode<T>>>>：

pub fn push(&mut self, num: T) { let node = ListNode::new(num); node.borrow_mut().next = self.stack_peek.take(); // take() 临时取出旧头 self.stack_peek = Some(node); self.stk_size += 1; } pub fn pop(&mut self) -> Option<T> { self.stack_peek.take().map(|old_head| { self.stack_peek = old_head.borrow_mut().next.take(); self.stk_size -= 1; old_head.borrow().val }) }

从源码结构看，这里用take()先移走Option里的旧头节点，再赋值新头，是为了在借用检查器（borrow checker）面前构造出合法的独占可变借用；pop()返回Option<T>而非抛异常，是 Rust 处理「空栈」这一不可预期状态惯用手法。

6.3 小结：三种实现的共同骨架

维度	Python	C++	Rust
头指针类型	`ListNode \\| None`	`ListNode *`	`Option<Rc<RefCell<ListNode<T>>>>`
空栈弹出行为	抛`IndexError`	抛`out_of_range`	返回`None`
节点释放	GC 自动回收	`delete`+ 析构遍历	`Rc`引用计数
`to_list`策略	正向收集后`reverse()`	逆序回填	递归拼接

三种实现的状态都只有「头指针 + 计数器」两个变量，进一步说明链表栈的实现骨架极其紧凑，语言差异全部落在内存管理层面。

七、链表栈的适用场景与性能特征

结合仓库文档 ru/docs/chapter_stack_and_queue/stack.md 中「两种实现比较」一节的结论：

扩容：数组栈在容量耗尽时扩容，单次push退化为 $O(n)$，属于「平时快、偶尔慢」；链表栈每次push都新分配一个节点，没有整体搬迁，各次操作耗时稳定；
内存：链表节点要为next指针额外付出空间，而数组可能预留超出实际需要的容量，两者各有所失，需按场景权衡；
天然适配：如果入栈的元素本身已经是节点对象（例如遍历树时压入TreeNode），链表栈可以直接压入节点而不需要额外包装，这正是文档中提到的「跳过节点初始化步骤」的情形；
典型应用：浏览器前进/后退历史（两个栈配合实现 undo/redo）、函数调用的栈帧管理（递归深入即连续push，回溯即连续pop）。

八、总结

本文围绕 ru/codes/pythontutor/chapter_stack_and_queue/linkedlist_stack.md 的可视化代码展开：先确认了该文档与 mkdocs 构建标记、真实源码文件之间的对应关系；再逐一拆解了 LinkedListStack 的头插式push、带空栈保护的pop/peek、常数时间的size/is_empty与需要翻转的to_list；随后通过驱动代码的运行推演验证了 LIFO 语义，并用 C++、Rust 源码对照说明了同一算法在不同内存模型下的实现差异。掌握这一实现后，读者可以将其作为理解数组栈（ru/codes/python/chapter_stack_and_queue/array_stack.py）、双端队列（deque）等后续数据结构的基础。

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

Hello 算法仓库中的链表栈：用「头插法」实现 O(1) 入栈出栈的完整解析