今回は、リストの演習として「辞書」を作ってみます。これは、キーと値が対になった項目が並んでいて、キーを指定すると項目の中から指定したキーに対応する値を返したり指定したキーを持つ項目を削除したり、という操作が行えるものです（いわゆる連想配列）。Mapみたいなものですね。今回は、キーと値を保持するクラスDItemのインスタンスをリスト化したDListオブジェクトを作って単方向リストへの追加や削除、検索を行ってみましょう。
単方向リストのデータ構造とアルゴリズム
単方向リストは、ある構造をもった項目が線形に並んだデータ構造です。各項目は「次の項目への参照」を保持しており、最初から順に「次の項目」を辿っていく事でリスト内の任意の項目にアクセスできます。基本的には「最初から順に」辿っていく事しか出来ないので、任意の場所へ頻繁にアクセスする場合は不利ですが、「順番の付け替え」だけで項目の追加や削除が可能なので頻繁に項目を追加・削除する場合は検討してみる価値があるかもしれません（まあ、実際は双方向リストの方が良い事が多いけど）。
今回作る辞書は「キーと値」のセットなので、キーと値それに次の項目への参照を持つ項目クラスDItemを定義しましょう。このクラスには、「キーと値から項目インスタンスを作るコンストラクタ」「キー・値の取得」「次の項目へのアクセス」といったインターフェースメソッドを定義しておきます。
class DItem { // 項目クラス
DItem(String st1,String st2)
String getKey()
String getValue()
DItem getNext()
void setNext(DItem di1)
}
内部の実装は、String型のキーと値、DItem型の次の項目といった内部メンバ変数を定義し、その取得・設定を行えば良いでしょう。
class DItem { // 項目クラス
String stKey,stValue;
DItem diNext;
DItem(String st1,String st2) {
stKey=st1;
stValue=st2;
}
String getKey() { return stKey; }
String getValue() { return stValue; }
DItem getNext() { return diNext; }
void setNext(DItem di1) { diNext=di1; }
}
これで「キーと値、次の項目」を保持するためのクラスが出来たので、次はこのクラスのインスタンスをまとめるリストクラスDListを定義します。機能としては、項目の追加・削除、検索、といったあたりですかね。あと、リスト内の項目にアクセスできるように「最初の項目」の参照を取得するメソッドも用意しておきましょう。
class DList { // 項目リストクラス
boolean add(String st1,String st2)
String search(String stKey)
boolean delete(String stKey)
DItem getFirst()
}
クラスDListの内部には、最初の項目を保持するdiFirstと最後の項目を保持するdiLastという２つのDItem型変数を用意しましょう。メソッド内では、項目を変更するたびに最初と最後の項目を更新しておくようにします。まず、項目の追加を行うaddは、
boolean add(String st1,String st2) {
if (st1.length()<1)
return false;
if (diFirst==null) {
diFirst=new DItem(st1,st2);
diLast=diFirst;
} else {
DItem diWrk=new DItem(st1,st2);
diLast.setNext(diWrk);
diLast=diWrk;
}
return true;
}
という感じにしてみました。リスト内に項目がなければ、新しい項目を作成してそれをdiFirst/diLastにする、すでに項目があれば新しく作成した項目を現在の最後の項目の後に繋げ、diLastを更新するわけですね。
次に検索。これは、diFirstから順に項目のキーを見ていって指定されたキーと一致すれば、その項目の値を返す、というアルゴリズムになります。
String search(String stKey) {
String stWrk=new String();
DItem diWrk=diFirst;
while(diWrk!=null) {
if (stKey.equals(diWrk.getKey())) {
stWrk=diWrk.getValue();
return stWrk;
}
// 次の項目へ
diWrk=diWrk.getNext();
}
return stWrk;
}
最後に削除は、「削除する項目の前の項目と後ろの項目を繋ぐ（削除対象の項目を飛ばす）」処理ですが、削除対象がリストの最初の項目だった場合はその次の項目を最初の項目に設定します。「削除する項目の前の項目」が必要なのがちょっと厄介ですね。双方向リストなら問題ないのですが、単方向リストでは次の項目に移る時に現在参照している項目を「前の項目」として保存しておく必要があります。
boolean delete(String stKey) {
if (diFirst==null)
return false;
DItem diWrk=diFirst,diPrev=diFirst;
if (stKey.equals(diWrk.getKey())) { // 削除対象は最初の項目
if (diLast==diWrk) {
diFirst=null;
diLast=null;
return true;
}
diFirst=diWrk.getNext();
return true;
}
diWrk=diWrk.getNext();
while(diWrk!=null) {
if (stKey.equals(diWrk.getKey())) {
if (diWrk==diLast)
diLast=diPrev;
// 削除対象の前の項目に削除対象の次の項目を繋ぐ
diPrev.setNext(diWrk.getNext());
return true;
}
diPrev=diWrk; // 削除対象の前の項目を保存
diWrk=diWrk.getNext();
}
return false;
}
*リスト内の最後の項目のdiNextはnullになっています。
辞書の操作
今回のアプレットでは、辞書リストに登録や削除・検索を行うためキーと値を指定するテキストフィールドとボタン類を配置します。
DList dlData;
TextField tfKey,tfValue,tfSearch,tfRes;
Button btAdd,btSearch,btDelete;
TextArea taView;
Panel pnAdd,pnSearch,pnView;
public void init() {
tfKey=new TextField(8); // 追加項目のキー
tfValue=new TextField(8); // 追加項目の値
tfSearch=new TextField(8); // 検索・削除キー
tfRes=new TextField(8); // 検索結果の値
btAdd=new Button("A d d");
btAdd.addActionListener(this);
btSearch=new Button("S e a r c h");
btSearch.addActionListener(this);
btDelete=new Button("D e l e t e");
btDelete.addActionListener(this);
taView=new TextArea(24,48);
pnAdd=new Panel();
pnAdd.add(new Label("Key"));
pnAdd.add(tfKey);
pnAdd.add(new Label("Value"));
pnAdd.add(tfValue);
pnAdd.add(btAdd);
pnSearch=new Panel();
pnSearch.add(new Label("Key"));
pnSearch.add(tfSearch);
pnSearch.add(btSearch);
pnSearch.add(btDelete);
pnSearch.add(tfRes);
pnView=new Panel();
pnView.add(taView);
add(pnAdd);
add(pnSearch);
add(pnView);
dlData=new DList();
}
また、アプレットクラスには現在のリスト内の項目を表示するdrawData()を定義し、ここでテキストエリアtaViewにリスト内の項目のキー・値を表示するようにします。これは、リストの最初の項目を取得して順次項目を辿りながらキー・値を表示していくだけですね。このdrawData()は、最初と追加・削除などでリストが更新された時に呼び出すようにしましょう。
void drawData() {
String stWrk=new String();
DItem diWrk=dlData.getFirst();
while(diWrk!=null) {
stWrk+=diWrk.getKey()+" - "+diWrk.getValue()+"\n";
diWrk=diWrk.getNext();
}
taView.setText(stWrk);
}
ボタンがクリックされた時に追加・削除・検索を行う処理は、以下のようにリストのメソッドを呼び出すだけです。
public void actionPerformed(ActionEvent e) {
if (e.getSource()==btAdd) { // Addボタンクリックイベント
dlData.add(tfKey.getText(),tfValue.getText());
drawData();
}
if (e.getSource()==btSearch) { // Searchボタンクリックイベント
tfRes.setText(dlData.search(tfSearch.getText()));
}
if (e.getSource()==btDelete) { // Deleteボタンクリックイベント
dlData.delete(tfSearch.getText());
drawData();
}
}
プログラム
まず、KeyとValueを指定していくつか項目を作ってください。その後、下の段にあるKeyにキーを指定して検索や削除を試してみましょう。なお、今回はキーの重複チェックなどは行っていません。