はじめに
行き交う列車の多い鉄道網のために、列車のスケジュール管理システムを開発するプロジェクトに取り組んでいます。
そのスケジュール管理システムで使う列車の路線のプロトタイプを作るように頼まれました。それぞれの路線は、ある列車が停車する駅を順番に並べたものです。
説明
チームは、スケジュールにある各列車の路線を双方向連結リストで表すことに決めました。
列車の路線上にある各駅は、連結リストのノードで表します。
駅の到着時刻や出発時刻を気にする必要はありません。
各駅は、単に数値で表します。
路線は延長できます。路線の先頭または末尾に駅を追加します。
また、路線の先頭または末尾から駅を削除して短くすることもできます。
駅が廃止されることがあり、その場合は路線の先頭や末尾でなくても、その駅を路線から削除する必要があります。
路線の大きさは、列車が走る距離ではなく、停車する駅の数で測ります。
連結リストは、コンピューターサイエンスにおける基本的なデータ構造で、ほかのデータ構造の実装によく使われます。
名前のとおり、つながり合ったノードのリストです。
「ノード」のリストで、それぞれのノードが隣のノード（複数の場合もあります）とつながっています。
単方向連結リストでは、各ノードは後ろのノードだけとつながります。
双方向連結リストでは、各ノードは前のノードと後ろのノードの両方とつながります。
連結リストについてもっと深く知りたい場合は、わかりやすい図で解説しているこちらの記事を見てみましょう。
実装
この演習では、ジェネリクスを紹介します。
テストに合格するには、IntegerやStringなど、どんな型の入力でも受け付けるようにクラスを作る必要があります。
ジェネリクスを使うと、より汎用的で再利用しやすいコードを書けるようになるので便利です。
JavaのListとMapの実装は、どちらもジェネリクスを使ったクラスの例です。
これらを使えば、Integersを格納したListや、Strings、その他の型を格納した配列を作ることができます。
ジェネリクスで使う型には、いくつかの制約があります。
その1つは、Integersを格納したListを一度作ったら、そこにStringsを入れることはできないというものです。
クラスを作るときに、どの型を入れるかを指定する必要があり、そのインスタンスは指定した型でしか使えません。
たとえば、次のようにIntegersの配列を作ることができます。
List<Integer> someList = new LinkedList<>();
これで、someListにはIntegersしか入れられません。次のようにすることもできます。
List<String> someOtherList = new LinkedList<>()
これで、someOtherListにはStringsしか入れられません。
もう1つの制約は、ジェネリクスで使う型はintやlongのようなプリミティブ型にはできないというものです。
ただし、すべてのプリミティブ型には対応する参照型があるので、intの代わりにInteger、longの代わりにLongを使えます。
とっかかりをつかむために、ジェネリクスの使用例を見てみるとよいでしょう。
出典
コンピューターサイエンスの定番のテーマ
