単純な連結リスト

説明

音楽プレイヤーアプリケーションのプロトタイプを書いてみましょう。

プロトタイプでは、それぞれの曲を単純に数値で表します。数値の範囲（曲のID）が与えられたら、単方向連結リストを作成しましょう。

単方向連結リストが与えられたら、そのリストを逆順にして、曲を反対の順番で再生できるようにしましょう。

Pythonでのこの演習の構成

stacksやqueuesはlists、collections.deque、queue.LifoQueue、multiprocessing.Queueを使って実装できますが、この演習では、自作の単方向連結リストを使った「後入れ先出し」（LIFO）スタックを想定しています。

これは、内部でlistやqueue、arrayを使うかもしれない動的配列やリストを使ったLIFOスタックと混同しないでください。動的配列ベースのstacksは、headの位置が異なり、時間計算量（Big-O）やメモリ使用量も異なります。

これらの考慮点については、Stack Overflowの次の2つの質問を参照してください：配列ベースとリストベースのスタックとキューと、配列スタック、連結スタック、スタックの違い。 Pythonにおける連結リスト、LIFOスタック、その他の抽象データ型（ADT）の詳細については、次の資料をご覧ください：

• Baeldung: 連結リストのデータ構造（複数の実装を扱っています）
• Geeks for Geeks: 連結リストを使ったスタック
• Moshによる抽象データ構造の解説（連結リストだけでなく、多くのADTを扱っています）

Pythonのクラス

Pythonで連結リストを「標準的」に実装するには、通常1つ以上の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のいずれかを継承するという選択肢があります。 エラーを送出するときも、意味のあるメッセージを含めるようにしてください。

この演習では、連結リストが空のときに送出される（"thrown"）_カスタム例外_を作成する必要があります。 テストに合格するには、適切な例外をカスタマイズし、その例外を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』の単方向連結リストから着想を得ています。