連結リスト

説明

チームは、スケジュールにある各列車の路線を双方向連結リストで表すことに決めました。 列車の路線上にある各駅は、連結リストのノードで表します。

駅の到着時刻や出発時刻を気にする必要はありません。 各駅は、単に数値で表します。

路線は延長できます。路線の先頭または末尾に駅を追加します。 また、路線の先頭または末尾から駅を削除して短くすることもできます。

駅が廃止されることがあり、その場合は路線の先頭や末尾でなくても、その駅を路線から削除する必要があります。

路線の大きさは、列車が走る距離ではなく、停車する駅の数で測ります。

この演習のPythonでの構成

連結リストは、基盤となるデータ構造をいろいろ変えて、さまざまな方法で実装できますが、ここでは連結リストをオブジェクト指向のスタイルで実装してください。

スタブファイルには、Nodeクラスの冒頭とLinkedListクラスがあります。 Nodeクラスでは、自身の値と、前後につながるノードを管理します。 push、pop、shift、unshift、そしてlen用の特殊メソッドは、LinkedListクラスに実装してください。 また、繰り返しのための特殊メソッドiterを実装すると便利かもしれません。

コアの演習とは異なり、ここでは空のLinkedListに対してpopやshiftを呼び出して、エラーになる条件をテストします。ですから、適切にエラーをraiseする必要があります。

最後に、ここまでに挙げたメソッドに加えてdeleteも実装してください。 deleteは引数を1つ取り、それは連結リストから削除する値です。 同じ値が複数回現れる場合は、最初に現れた1つだけを削除します。

例外メッセージ

例外を発生させる必要があることもあります。その際は、エラーの原因が何かを示す意味のあるエラーメッセージを必ず含めましょう。 そうすることで、コードが読みやすくなり、デバッグもしやすくなります。 エラーの原因が特定の種類だとわかっている場合は、組み込みのエラーの種類から1つ選んで発生させてもかまいませんが、その場合も意味のあるメッセージを含めましょう。

この演習では、delete()で削除しようとしているノードの値が連結リストに見つからないときに、raise文を使ってValueErrorを「投げる」必要があります。 また、pop()するノードが残っていない場合は、IndexErrorを投げる必要があります。 これらのexceptionsをraiseし、なおかつメッセージを添えたときにだけ、テストは通ります。

メッセージ付きでValueErrorを発生させるには、メッセージをexception型の引数として書きます。

# When the value passed to `delete()` is not found.
if not found:
    raise ValueError("Value not found")

メッセージ付きでIndexErrorを発生させるには、メッセージをexception型の引数として書きます。

# When pop() is called and there are no nodes left in the linked list
if self.length == 0:
    raise IndexError("List is empty")

Pythonの特殊メソッド

この演習のテストでは、LinkedListsに対してlen()も呼び出します。 len()を動かすには、特殊メソッド__len__を作成する必要があります。 Pythonで特殊メソッド、または「ダンダー」メソッドを実装する方法の詳細は、Pythonドキュメント：基本的なオブジェクトのカスタマイズとPythonドキュメント：object.len(self)を参照してください。

また、連結リストを繰り返し処理するのに役立つ、特殊メソッド__iter__を作ることもおすすめします。