程序设计导论：Python语言实践

4.3.3　基于链表实现栈

接下来，我们讨论一种实现栈的完全不同的方法，即使用一种称为链表（linked list）的基本数据结构。这里再使用“列表（list）”这个词会造成一定的困惑，但我们别无选择，因为链表（链接列表）的历史要远远比Python悠久。

链表是一个递归数据结构，其定义如下：链表要么是空（null），要么是一个指向节点（node）的引用，而节点包含指向链表的引用。这种定义中的节点是可以包含任意数据的抽象实体，节点引用则描述了构建链表角色的特性。如递归程序一样，刚开始接触递归数据结构的概念时可能会有点费解，但正因为其简洁性而具有重要价值。

基于面向对象的程序设计，实现链表并不困难。我们从定义节点抽象的类开始：

类型Node的一个对象包含两个实例变量：item（指向一个项目的引用）和next（指向另外一个Node对象的引用）。next实例变量描述了数据结构的链接本质。为了强调我们如何使用Node类来组织数据，Node类中除了构造函数以外没有定义任何其他方法。实例变量名称的前面省略了前缀下划线，意味着数据类型的外部代码（但仍然还是Stack实现中的代码）允许访问这些实例变量。

现在，根据递归定义，我们可以将一个链表表示为对一个Node对象的引用，Node对象包含对项目和另一个Node对象的引用，以此类推。链表中的最后一个Node对象必须清楚地表明其为最终节点。在Python中，通过把最后一个Node对象的next实例变量赋值为None，将其标识为最终节点。注意，None是一个Python关键字，赋值为None的变量不引用任何对象。 ...