簡易鏈結串列

說明

寫一個音樂播放器應用程式的原型。

在這個原型中，每首歌只用一個數字來代表。 給定一段數字範圍（也就是歌曲 ID），請建立一個單向鏈結串列。

給定一個單向鏈結串列，你應該要能反轉這個串列，讓歌曲以相反的順序播放。

這個練習在 Python 中的結構

雖然stacks和queues可以用lists、collections.deque、queue.LifoQueue和multiprocessing.Queue來實作，但這個練習預期的是以 自製的 單向鏈結串列實作的「後進先出」（LIFO）堆疊：

這不應該與使用動態陣列的LIFO堆疊混為一談，後者底層可能使用list、queue或array。 以動態陣列為基礎的stacks有不同的head位置，以及不同的時間複雜度（Big-O）與記憶體佔用量。

有幾個考量點可以參考這兩篇 Stack Overflow 問答：以陣列為基礎與以鏈結串列為基礎的堆疊與佇列，以及陣列堆疊、鏈結堆疊與堆疊之間的差異。 關於鏈結串列、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。 引發錯誤時，你還是應該附上有意義的訊息。

這個練習要求你建立一個_自訂例外_，在鏈結串列為空時引發／「拋出」它。 只有當你自訂適當的例外、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》的單向鏈結串列。