java教えてください。

質問

双方向リストをjavaで書きたいんですけどここまで書いて双方向リストになってるか不安になってきました。
これは双方向リストになっていますか？

class MyListw{
int data;
MyListw next = null; //次のノードへのポインタ
MyListw prev = null; //前のノードへのポインタ
MyListw(int data){
this.data = data;
}
void insertTail(MyListw node){ //リストの最後へ追加
MyListw tmp = this;
while(tmp.next != null){
tmp = tmp.next;
}
tmp.next = node;
node.prev = tmp.next;
}

void insertHead(MyListw node){ //リストの先頭へ追加

node.next = this.next;

this.next = node;
node.prev = this.next;
}

void insert(int head, MyListw node){ //リストの途中へ新規データを挿入
MyListw tmp = this;

while(tmp != null){
if(tmp.data == head){
break;
}
tmp = tmp.next;
}
node.next = tmp.next;
tmp.next = node;
node.prev = tmp.next;

}

void delete(int here, MyListw node){ //リストからデータを1つ削除
MyListw tmp = this;

while(tmp != null){
if(tmp.data == here){
break;
}
tmp = tmp.next;
}
node = tmp.next;
tmp.next.prev = node;
tmp.next = node.next;
node.next.prev = tmp.next;
node.next = null;
node.prev = null;

}

void deleteHead(){ //先頭のノードを削除
MyListw tmp = next;
this.next = tmp.next;
tmp.next.prev = this.next;
tmp.next = null;
tmp.prev = null;
}

void deleteTail(){ //最後のノードを削除
MyListw tmp = this;
MyListw lastList = null;

while(tmp.next != null){
lastList = tmp;
tmp = tmp.next;
}

lastList.next = null;
lastList.prev = null;
}

void show(){
MyListw tmp = next;
while(true){
System.out.print(tmp.data);
if(tmp.next == null)
break;
tmp = tmp.next;
}
System.out.println("");
}

void showTail(){

}
}

class MyListwApp{
public static void main(String[] args){
MyListw list = new MyListw(0); //初期ダミー

System.out.println("最後に追加");

list.insertTail(new MyListw(1));
list.show();
System.out.println("逆順に表示");
list.showTail();

System.out.println("\n");

list.insertTail(new MyListw(5));
list.show();
System.out.println("逆順に表示");
list.showTail();

System.out.println("先頭に追加");

list.insertHead(new MyListw(8));
list.show();
System.out.println("逆順に表示");
list.showTail();

System.out.println("\n");

list.insertHead(new MyListw(9));
list.show();
System.out.println("逆順に表示");
list.showTail();

System.out.println("途中からデータを追加");

list.insert(1, new MyListw(2));
list.show();
System.out.println("逆順に表示");
list.showTail();

System.out.println("\n");

list.insert(2, new MyListw(3));
list.show();
System.out.println("逆順に表示");
list.showTail();

System.out.println("リストからデータを削除");

list.delete(8, new　MyListw(1));
list.show();
System.out.println("逆順に表示");
list.showTail();

System.out.println("先頭のノードを削除");

list.deleteHead(); //先頭のノードを削除
list.show();
System.out.println("逆順に表示");
list.showTail();

System.out.println("\n");

list.deleteHead();
list.show();
System.out.println("逆順に表示");
list.showTail();

System.out.println("最後のノードを削除");

list.deleteTail(); //最後のノードを削除
list.show();
System.out.println("逆順に表示");
list.showTail();

System.out.println("\n");

list.deleteTail();
list.show();
System.out.println("逆順に表示");
list.showTail();
}
}

回答No.2

Lchan0211 · ベストアンサー

双方向リストのメリットは、データの追加/削除操作を高速にできる
(リンク操作のためにループをする必要がない)点にあります。

このソースでは、せっかくのprevがあまり有効に活用されておらず、
片方向リストと処理性能が変わりません。
実質的に、双方向リストの処理になってないです。

まず、insertTail()やdeleteTail()の処理は、whileを使わないで
実現すべきです。
この処理をするには、リストの最終ノードを求める必要がありますが、
循環双方向リストの形にしておけば、リスト開始ノードのprevが
最終ノードということなります。
(循環双方向リストでなく、リストの先頭ノードと最終ノードを保持した、
リストオブジェクトを別に作る方法もあります。)

次に、insert(),delete()について、
このメソッドは、指定値と同じ値を持つノード位置に
新しいノードを挿入(またはそのノードを削除)という機能
なのだと思いますが、ノードの検索機能とノードの挿入/削除機能が
一緒になっているため、双方向リストのメリットを享受できません。

(1)指定値を持つノードを検索し、そのノードオブジェクトを返却するメソッド(find)
(2)ノードオブジェクトを指定し、そのノードの位置に新しいノードを
挿入する(またはそのノードを削除する)メソッド
の2つに分ければ、それぞれのメソッドの用途が広がり、
(2)のメソッドは双方向リストのメリットを活かした処理になります。

(参考)
http://akademeia.info/index.php?%C1%D0%CA%FD%B8%FE%A5%EA%A5%B9%A5%C8
http://ja.wikipedia.org/wiki/%E9%80%A3%E7%B5%90%E3%83%AA%E3%82%B9%E3%83%88

お礼

回答ありがとうございます。

書き直してみます。

回答No.1

Tacosan

実行してみればわかるけど insert系は全滅です. 最後の文が間違っているだけだけど.
deleteHead もあやしいなぁ.
操作前と操作後の状況を図に描いて, 「それぞれのメンバの値がどうなればいいのか」を考えてみてください.