連結リスト

説明

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

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

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

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

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

C++トラックでのこの演習の構成

連結リストは、さまざまなデータ構造を土台にして、さまざまな方法で実装できますが、ここでは連結リストをオブジェクト指向のスタイルで実装していただきます。

linked_list_test.cppファイルを見ると、テンプレート化されたListクラスが呼び出されているのがわかります。 このクラスには、次のメンバー関数を書くことが求められます。

• pushは、リストの末尾に要素を追加します。
• popは、リストの最後の要素を取り除いて返します。
• shiftは、リストの最初の要素を取り除いて返します。
• unshiftは、リストの先頭に要素を追加します。
• countは、現在のリストにある要素の合計数を返します。

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

テストはされませんが、空のListに対してpopやshiftが呼ばれたときは、例外を投げるとよいかもしれません。