My開発メモ

大阪環状線のような円環リストをつくる(Java)

大阪環状線のような終わりのない円環状リストをつくってみた。

まず、構成要素となる駅クラスを以下のように作成した。

package railway;

import java.util.Objects;

public class Eki {
	String name;
	Eki next = null;
	Eki prev = null;

	public Eki(String name) {
		this.name = name;
	}

	@Override
	public int hashCode() {
		return Objects.hash(name);
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Eki other = (Eki) obj;
		return Objects.equals(name, other.name);
	}

	@Override
	public String toString() {
		return name;
	}
}

nextフィールド と prevフィールド を用意しておいた。
これは、たとえば「大阪」なら、nextが「天満」になり、
prevが「福島」になる。

次は、これを円環状にする EkiListクラスである。

package railway;

public class EkiList {
	// 最初 EkiList のインスタンスを生成したときは、
	// この head には、next も prev も null である
	// Eki インスタンスが代入されている。
	// しかし、EkiListがadd()コマンドにより生成されてのちは
	// この head には、next には歳1番目の Eki インスタンスが
	// 代入されている。
	private Eki head = new Eki(null);
	private int length = 0;
	
	public Eki get(String name) {
		Eki eki = head;
		while (eki.next != null) {
			eki = eki.next;
			if (eki.name.equals(name)) {
				return eki;
			}
		}
		return null;
	}

	public void add(int num, String name) {
		int i = 0;
		Eki eki = head;
		while (i < num) {
			eki = eki.next;
			i++;
		}
		// System.out.println(eki.next.name);
		Eki nextEki = eki.next;
		eki.next = new Eki(name);
		eki.next.next = nextEki;
		this.length++;
	}
	
	public void add(String name) {
		Eki eki = head;
		while (eki.next != null) {
			eki = eki.next;
		}
		Eki newEki = new Eki(name);
		eki.next = newEki;
		newEki.prev = eki;
		this.length++;
	}
	
	public int size() {
		return this.length;
	}
	
	/**
	 * ekilist.add(福島) のあとで、ekilist.close("大阪") とすれば、
	 * ekilistは閉じられる。
	 * @param name
	 */
	public void close(String name) {
		Eki eki = head;
		while (eki.next != null) {
			eki = eki.next;
		}
		Eki end = get(name);
		eki.next = end;
		end.prev = eki;
		
	}
	
	public void remove(String name) {
		Eki eki = head;
		while (!eki.next.name.equals(name)) {
			eki = eki.next;
		}
		// System.out.println(eki.name);
		Eki nextEki = eki.next.next;
		eki.next = nextEki;
		this.length--;
	}
	
	public String toString() {
		StringBuilder sb = new StringBuilder();
		Eki eki = head;
		String headNextName = eki.next.name;
		while(eki.next != null) {
			eki = eki.next;
			sb.append(eki.name + " ");
			if (eki.next.name.equals(headNextName)) break;
		}
		return sb.toString();
	}
}

EkiListクラスのインスタンスを作成したときに、
まず Eki型の head を宣言し、nameがnull、
nextもprevもnull というインスタンスを代入しておく。

private Eki head = new Eki(null);

ポイントとなるのは、add()メソッドである。
このメソッドは引数に String型の name をとる。

public void add(String name) {
	Eki eki = head;
	while (eki.next != null) {
		eki = eki.next;
	}
	Eki newEki = new Eki(name);
	eki.next = newEki;
	newEki.prev = eki;
	this.length++;
}

まず、Eki型のフィールドeki に headを代入している。

この head は name もnull であり、nextもprevも null である。

(1) EkiList作成の最初の駅「大阪」を add()した場合

headが代入された eki の eki.next は、当然nullなので、while(){} は実行
されない。

そして、新しいEkiインスタンス newEki を作成する。

Eki newEki = new Eki(name); // nameは"大阪"である

headが代入されている ekiのnextフィールドに このnewEkiを代入する。
また、大阪がセットされている newEkiのprevフィールドに
headが代入されいる eki を代入する。

head.name = null
head.next = newEki(大阪)
head.prev = null

newEki.name = "大阪"
newEki.next = null
newEki.prev = head

現時点では newEkiのprevには “head” がセットされているが、
将来 Eki「福島」が作成されれば、このprevにはEki「福島」が
セットされることになる。

(2) EkiListで駅「京橋」を add()した場合

「京橋」をadd()できる場所(Eki)まで移動する必要がある。

Eki eki に head を代入すると、そこが起点になる。

このheadは EkiListのクラス変数なので、EkiListを作成した
ときのheadになっている。
すなわち、headのnextフィールドには「大阪」がセットされている。
また、Eki「大阪」のnextフィールドには「天満」がセットされている。
そして、Eki「天満」のnextフィールドには「桜宮」がセットされている。

だから、while()文で、eki.nextがnullになるところ、すなわち「桜宮」
まで Eki をすすめているのである。

while (eki.next != null) {
    eki = eki.next;
}

そして、「京橋」のEkiインスタンスを作成し、それを「桜宮」Ekiインスタンス
のnextフィールドにセットしている。

また、「京橋」のprevフィールドに「桜宮」をセットしている。

Eki newEki = new Eki(name);
eki.next = newEki;
newEki.prev = eki;

ほかにもいろいろとあるが、骨格となるのは、以上。

main()メソッドの例

public class Main {
  static EkiList ekiList;

  public static void main(String[] args) {
    ekiList = new EkiList();
    ekiList.add("大阪");
    ekiList.add("天満");
    ekiList.add("桜ノ宮");
    ekiList.add("京橋");
    ...
    ekiList.add("福島");
    ekiList.close("大阪");
  }
}

close()メソッドで、Eki「福島」のnextフィールドにEki「大阪」を、
Eki「大阪」のprevフィールドにEki「福島」をセットしている。