さまざまなデータ構造（１）片方向リスト用のノード

データ構造

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

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

ノードを作る

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

今回作るノードを図にすると上図のようになります。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;
	}
}
Java

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

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

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

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

５～６行目のインスタンス変数は、elementとnextで上の図のとおりです。

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

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

２９～３５行目のtoStringは、文字列での表現を返すメソッドです。次のノードにつながっている場合には『［element］→』、次のノードがnullの場合には『［element］』としています。

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

Posted by 春日井 優