Java Node作成について

Question

ダブルリンクドリストで最後に新しいノードを追加したいのですが、Nodeクラスのコンストラクターは一つしかありません。
Nodeクラスのコンストラクターを使ってどのように新しいノードを追加すればいいのでしょうか。

Node.java

public class Node {

	public Node next;
	public Node prev;
	
	private String t;

	public Node(Node next, Node prev, String token) {
		this.next = next;
		this.prev = prev;
		this.t = token;
	}

Comments

[TakaiY]

Node.jsは関係ないので、消しておきましょう。

Answer 1

末尾のノードのnextに何が設定されているのかわかりませんが、nullとしておきましょう。

• 末尾のノードをつかまえる。Tとする。
• 新規のノードを作成する。Nとする。
  nextはnull, prevにはTを指定する。
• TのnextにNを設定する。

これでよいかと。

---

こんな感じ？ 上に書いた通りですが。

t = // リストの末尾

Node n = new Node(null, t, "hoge")
t.next = n

もとのリストがどのように表現されているかわからないので、とりあえず、末尾がわかっているとしときました。

---

質問でもらったソースをできるだけ生かせばこんな感じでしょうか。

public boolean add(String obj) throws NullPointerException{ //boolean -> void
    if(obj == null) {
        throw new NullPointerException("obj cannot store a null reference!");
    }
    else {
        // currentの設定はここにあってはだめ。
        Node newNode = new Node(null, null, obj);  //このタイミングではではprevを決められないのでnullとしておく。
        if(head == null) {
            head = newNode;
            tail = newNode;  // tailの更新を追加。 空だったときはどちらも同じノードを指す。
            // 単一ノードなので、newNodenのnextもprevもnullの儘
        }
        else {
            Node current = head;     //currentの設定はここに移動。       
            while(current.next != null) {
                current = current.next;
            }
            current.next = newNode;
            newNode.prev = current   //ここでnewNodeのprevが設定できる。
            tail = newNode;   // tailは、最後のノードそのものを指している。 newNode.next ではrnullになっちゃう。
        }
    }
    return true;
}

さて、そもそもtailで末尾を持っているのだから、末尾を捜す処理は不要なので、こんな感じ。

public boolean add(String obj) throws NullPointerException{ //boolean -> void
    if(obj == null) {
        throw new NullPointerException("obj cannot store a null reference!");
    }
    else {

        Node newNode = new Node(null, null, obj);

        if(head == null) {
            head = newNode;
            tail = newNode;
        }
        else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }
    return true;
}

Comments

[coala]

早々にご回答ありがとうございます。
ダブルリンクドリストの初心者で申し訳ないのですが、コードで説明いただけると大変助かります。
よろしくお願い致します。

[coala]

早々に追記ありがとうございます。
他のクラスでリストの末尾はNode tail;で定義してあります。
その場合、TakaiYさんのを参考にさせていただくと
Node n = new Node(null, tail, "hoge");
tail.next =n;
ありがとうございます。nextをnullで定義する発想がありませんでした。大変助かりました、ありがとうございます。

[TakaiY]

よかったです。

tailが保持されているのであればさらに
tail = n
というふうにtailも更新しておく必要がありますね。

[coala]

tailに対して新しいNodeを作成する必要があるということでしょうか。
tail.next = n;として上でその後
tail = n;が必要という理解でよかったでしょうか。
headも定義されているので私の中で以下のコードでダブルリンクドリストの最後に新しいノードが追加できると考えました。
どうでしょうか。もしよければコード見ていただけないでしょうか。
public void add(String obj){
Node current = head;
Node newNode = new Node(null, current, obj);
if(head == null){
head = newNode;
}
else{
while(current.next != null){
current = current.next;
}
current.next = newNode;
}
}

[dodox86]

横からすみません。混乱させるつもりはありませんが、双方向リストでかつ明示的なheadがあるのであれば、headのprevで末尾のNodeを指すようにしておくことで、一発で最後のNodeに辿り着くことができます。

[coala]

補足ありがとうございます。
tailのnextではなく、headのprev、確かにそうですね。
tail.nextとするとheadに戻ってしまうという理解でよかったですか。
dodox86さんのおっしゃられるようにコードを変更すると以下の理解であっていますか。
public void add(String obj){
Node current = head;
Node newNode = new Node(null, current, obj);
if(head.prev == null){
current = newNode;
}

}

[TakaiY]

まず、ノードを循環させる(headとtailをつなぐ)話は置いておきましょう。
3つ前のコードは前提が崩れています。 どこかでtailを保持しているのであれば、前に示したとおり、最後にNodeを追加したのであれば、そのtailが指しているものを更新する必要があるということです。

3つまえのコードは、taliは保持しておらず、currentが末尾になるまで回しています。 毎回そのように末尾を捜すのであれば、そもそも末尾は保持していないので、更新もいらなくなります。

前提が崩れればコードは変ります。

3番目のコードはいくつか問題があります。たとえば、
Node current = head;
としていますが、headがnullだった場合、currentが更新されない場合があるので、後で例外が発生する可能性があります。ここを変えようとすると他も変えなければなりません。

headにリストの先頭を持っていて、リストが未生成の場合(head=null)のことも考えるのであれば、もっとロジックを検討する必要があります。
- headがnullなら、新規のノードを生成してそれをheadに入れて返す
- headがnullでないなら、nextがnullになるまで辿って(=末尾を探して)新規ノードを先述のようにくっつける。
という処理になるでしょう。

dodox86さんの指摘のようにリストを循環させる方法もありますが、末尾の検出の方法がまったく異なり、また、ノードを追加するには、一度切り離して間に嵌め込む必要があるので、かなり複雑になります。
この場合もロジックはきちんと検討しなければうまく動きません。

[dodox86]

そうですね。TakaiYさんのコメントのように、まずはもとの考えのまま、一貫して完成させた方が良いと思います。（混乱させるかと思いましたが、大分惑わせてしまったようです。失礼しました）明示的にheadがある場合、headと言う特別なNodeがあるかたちでも、headは循環したリスト中のNodeのいずれかへの参照として別にとっておくかたちでも、様々な方法が考えられます。前提が崩れるのは確かなので、私の案は脇へおいてください。

[coala]

詳細なアドバイスありがとうございます。
ご指摘いただいたようにコードを作成しました。
参照いただけないでしょうか。
public boolean add(String obj) throws NullPointerException{ //boolean -> void
if(obj == null) {
throw new NullPointerException("obj cannot store a null reference!");
}
else {
Node current = head;
Node newNode = new Node(null, current, obj);
if(head == null) {
head = newNode;//headがnullなら、新規のノードを生成してそれをheadに入れて返す
}
else {
while(current.next != null) {
current = current.next;
}
current.next = newNode;//headがnullでないなら、nextがnullになるまで辿って(=末尾を探して)新規ノードを先述のようにくっつける。
tail = newNode.next;//どこかでtailを保持しているのであれば、前に示したとおり、最後にNodeを追加したのであれば、そのtailが指しているものを更新する
}
}
return true;

最後のtailの部分ですが、
public Node head;
private Node tail;
public int data;
として定義しています。

[TakaiY]

- headがnullだったときにcurrent.nextにアクセスしたところで落ちます。
前にも指摘しています。currentは末尾を捜すために必要なだけなので、elseに入れればよい。
- tailの更新が漏れているし、間違えています。

そもそも、tailがあるのであれば、currentのループは不要です。どこかから流用したコードと思いますけど。

コードの修正版を回答に入れました。 動かしていないので、バグってるかもしれませんが。

[coala]

TakaiYさんコードの修正版まで作成していただきわかりやすい説明ありがとうございました。ご指摘いただきました内容完全に理解できました。
お時間を作っていただきありがとうございました。