双方向線形リストの挿入

Question

前提・実現したいこと

javaで双方向線形リストの勉強をしていて、
新しいノードを先頭に挿入にしていくプログラムを作りたいのですが、
NullPointterExceptionが出てしまいます。
insertAメソッドの2,3行目が間違っている気はするのですが…

実行結果が
空行
Taro
Jiro<->Taro
Sabu<->Jiro<->Taro
となるようにしたいのです。

発生している問題・エラーメッセージ

Exception in thread "main" java.lang.NullPointerException
        at exer3.link.DoublyLinkedList.toString(DoublyLinkedList.java:21)
        at java.base/java.lang.String.valueOf(String.java:3388)
        at java.base/java.io.PrintStream.println(PrintStream.java:1047)
        at exer3.link.tester.TesterD01.main(TesterD01.java:7)

該当のソースコード

import java.util.StringJoiner;

public class DoublyLinkedList<V> {
	public class Node {
		private V value;
 	   private Node prev = this;
		private Node next = this;
		private Node(V v) { value = v; }
		public Node getPrev() { return prev; }
		public Node getNext() { return next; }
		public V getValue() { return value; }	
	}

	private Node terminal;

	public DoublyLinkedList() { terminal = null; }

	public String toString() {
		StringJoiner j = new StringJoiner("<->");
		Node p = terminal.next;
		while (p != terminal) {
			j.add(p.value.toString());
			p = p.next;
		}
		return j.toString();
	}

	public DoublyLinkedList<V> insertA(V v){
		Node x = new Node(v);
		x.next = terminal.next;
		x.prev = terminal;
		terminal.next.prev = x;
		terminal.next = x;
		return this;
	}

}
________________________________________________________________________________________
テスター

public class Tester {
	public static void main(String[] args) {
		DoublyLinkedList<String> l = new DoublyLinkedList<>();
		System.out.println(l);
		l.insertA("Taro");System.out.println(l);
		l.insertA("Jiro");System.out.println(l);
		l.insertA("Sabu");System.out.println(l);
	}
}

Answer 1

このコードは双方向リストというよりは双方向の参照を持つ循環リストではないかと思います。線形リストではありません。
循環するのが前提で書かれている処理があります。
terminalはリストの先頭？終端？どちらでしょう。先頭であり終端である前提で書かれている節があります。

とりあえず決定的にいけないのは、terminal のnull考慮がないことです。

terminalはnullで初期化されていますが、初回insertAする際にterminal.next等を参照します。
terminalはnullなので当然NullPointerExceptionです。
また、toStringでもterminalのnullチェックがありません。
提示のスタックトレースはtoStringで発生しています。読めばわかりますよね？

あとは、insertする処理も整理がついていません。図を書きながらどのように参照を代入すれば良いかイメージを描いてください。こういう処理はまず図を書いて整理することが肝要です。

どのように学習されているかが分かりませんが、双方向線形リストを実装するには必要な知識がかなり不足しています。ジェネリクスの実装方法も間違っています。ジェネリクスを使わない単方向線形リストの実装から学習をやり直したほうが賢明と思います。

Comments

[mazeneko]

補足すると、terminalのnull考慮がないだけでなくterminalにnull以外が入るロジックがないですね。