简单链表

说明

为音乐播放器应用写一个原型。

在原型中，每首歌就简单地用一个数字表示。 给定一个数字范围（也就是歌曲 ID），创建一个单向链表。

给定一个单向链表，你应该能够反转这个链表，从而按相反的顺序播放歌曲。

这个练习在 Python 中的结构

虽然stacks和queues可以用lists、collections.deque、queue.LifoQueue和multiprocessing.Queue来实现，但这个练习要求的是用_自制_的单链表实现的“后进先出”（LIFO）栈：

不要把它和用动态数组或列表实现的LIFO栈搞混，后者底层可能用的是list、queue或array。 基于动态数组的stacks，head位置不同，时间复杂度（Big-O）和内存占用也不同。

关于一些需要考虑的地方，可以参考这两个 Stack Overflow 问题：基于数组 vs 基于列表的栈和队列 和 数组栈、链式栈和栈之间的区别。 想进一步了解链表、LIFO栈以及 Python 中其他抽象数据类型（ADT）：

• Baeldung：链表数据结构（涵盖多种实现）
• Geeks for Geeks：用链表实现栈
• Mosh 谈抽象数据结构（涵盖许多ADT，不只是链表）

Python 中的类

在 Python 中，链表的“经典”实现通常需要一个或多个classes。 想好好入门classes，可以看classes和配套练习ellens-alien-game，或者官方 Python 教程的类部分。

Python 中的特殊方法

这个练习的测试会对你的LinkedList调用len()。 为了让len()正常工作，你需要创建一个__len__特殊方法。 关于在 Python 中实现特殊方法或“dunder”方法的细节，请参阅Python 文档：对象的基本定制和Python 文档：object.len(self)。

构建迭代器

想支持对LinkedList进行循环遍历或反转，你需要实现__iter__特殊方法。 关于实现细节，请参阅为类实现迭代器。

自定义异常和抛出异常

有时候，在你的代码里既需要自定义异常，也需要用raise来抛出异常。 这样做时，一定要附上有意义的错误信息，说明错误的来源是什么。 这能让你的代码更易读，对调试也有很大帮助。

自定义异常可以通过新的异常类来创建（详见classes），它们通常是Exception的子类。

如果你知道错误来源会是某种异常_类型_的派生，可以选择继承 Exception 类下的某个built in error types。 抛出错误时，仍然应该附上有意义的信息。

这个练习要求你创建一个_自定义异常_，当链表为空时将它抛出／“throw”。 只有自定义了合适的异常、用raise抛出这些异常，并附上合适的错误信息，测试才会通过。

要自定义一个通用的_异常_，可以创建一个继承自Exception的class。 抛出带信息的自定义异常时，把这条信息作为参数传给exception类型：

# subclassing Exception to create EmptyListException
class EmptyListException(Exception):
    """Exception raised when the linked list is empty.

    message: explanation of the error.

    """
    def __init__(self, message):
        self.message = message

# raising an EmptyListException
raise EmptyListException("The list is empty.")

---

来源

灵感来自《Data Structures and Algorithms with Object-Oriented Design Patterns in Ruby》中的单链表。