お知らせ

ただいま、シンタックスハイライターの設定を見直しております。
プログラムが見にくくなっているページがありますが、ご容赦ください。

さまざまなデータ構造(1)片方向リスト用のノード

データ構造

こんにちは。今回からデータ構造について数回書いていきたいと思います。(データ活用やデータサイエンスは、プログラムもデータも両方それなりに用意しないと書けないので、まとまった時間が取れるときに書くことにします。)今までPythonのプログラムが多かったのですが、久しぶりにJavaを書きたくなったのでJavaです。単に気分がJavaなだけです。

ということで、さまざまなデータ構造を扱っていくための準備として、今回はノードを作ります。ノードを作った後に、次回以降で連結リストやスタック、キューなどに発展させていこうと思います。

ノードを作る

ノードの説明はここでは割愛しますが、データがつながっているうちの1個分のデータと考えてもらって大丈夫です。

今回作るノードを図にすると上図のようになります。elementというデータを扱う部分と、nextという次のノードを指し示す部分によって構成します。次、次の次と後ろの方向にはたどっていくことができますが、前に戻ることは残念ながらできません。次回、連結リストを作りますが、このノードにより作られるリストは片方向リストといいます。最初なので、シンプルな片方向リストを扱うことにします。(補足ですが、アイキャッチ画像のUSBハブはnextが4個あるノードですね。)

なお、次につながるものがない場合には、nextはnullにしておきます。

ノードのプログラム

早速、プログラムです。

package data_structure;

public class MyNode<E> {

	private E element;
	private MyNode<E> next;

	public MyNode() {
		element = null;
		next = null;
	}

	public E getElement() {
		return element;
	}

	public void setElement(E element) {
		this.element = element;
	}

	public MyNode<E> getNext() {
		return next;
	}

	public void setNext(MyNode<E> next) {
		this.next = next;
	}

	public String toString() {
		String result = "[" + element + "]";
		if (next != null) {
			result += "→";
		}
		return result;
	}
}

3行目に謎の<E>とありますが、ジェネリクスといって整数だろうが文字列だろうがクラスだろうが特定の型なくても扱えるもので、総称型ともいわれています。実際に使う場合には変数宣言時に

MyNode<String> node = new MyNode<String>();

というように書けば、elementはStringになります。

長そうなプログラムに見えますが、メソッドはコンストラクタとgetter・setterとtoStringだけです。

5~6行目のインスタンス変数は、elementとnextで上の図のとおりです。

8~10行目のコンストラクタです。elementもnextもnullで空っぽのノードを作っているだけです。

13~27行目はgetter・setterです。インスタンス変数をprivateで宣言して、外部から直接操作できないようにしているので、値を取り出したり、値を変更したりといった操作は、ここで宣言されたメソッドを介して行います。インスタンス変数の値に制約がある場合には、setterで値を代入する前にチェックする必要があるのですが、今回はノーチェックです。

29~35行目のtoStringは、文字列での表現を返すメソッドです。次のノードにつながっている場合には『[element]→』、次のノードがnullの場合には『[element]』としています。

ノード1個分では大したことはできないので、今回はこれでおしまいにします。それではまた。

この記事を書いた人
春日井 優

高校で情報科という教科を担当しています。以前は数学科も担当していました。(今でも数学科の教員免許状は有効です。)プログラムを覚えたのは、「ゲームセンターあらし」という漫画のキャラクターがBASICを解説する「こんにちはマイコン」を読んだことがきっかけでした。

Posted by kasugai