Singly linked listで最後から二番目に挿入

質問

先週、テストがありました。
結構自信があったんですが、教授によるとすごく悪かったそうです…(結果はまだもらっていません)。
それで「問題全部、もう一度家でやり直してこい」と言われました。
下がその問題の一つです。

Write a method to insert a new node into a singly linked list before the tail node. If the list is empty, then the new node will be both the head and the tail node. This method will be a member of IntSLList class given on page 74.

public void addBeforeTail(int el) {
// ブランク

そのIntSLList.javaはIntNode.javaとセットで使われます(でもどちらもmainがないんです)。
そしてここ↓にあります。

http://www.mathcs.duq.edu/drozdek/DSinJava/.

(きっと)基となるメソッド(IntSLList.java内)
public void addToTail(int el) {
if (!isEmpty()) {
tail.next = new IntNode(el);
tail = tail.next;
}
else head = tail = new IntNode(el);
}

私自作のメソッド

public void addBeforeTail(int el) {
if (!isEmpty()) {
tail = new IntNode(el);
tail.next = tail;
}
else head = tail = new IntNode(el);
}

リストの最後の一つ手前に挿入するんでしょうが
Double linked listならnextとpreviousがあって
tail.previous = new IntNode(el);
tail = tail.previous;
にすれば解決だと思うのですが、
Singlyだとnextしかないのでどうすればいいのかはっきり分かりません。
勘で基となるだろうメソッドを逆にしてみました。
上の私自作のメソッドであってますでしょうか?
Javaの神様、どうかお助け下さい。m(__)m

回答No.4

takaP- · ベストアンサー

public void addBeforeTail(int el) {
　if (isEmpty()) {
　　addToHead(el);
　}
　else if (head==tail) {
　　head=new IntNode(el,tail);
　}
　else {
　　IntNode tmp;
　　for (tmp=head; tmp.next!=tail; tmp=tmp.next);
　　tmp.next=new IntNode(el,tail);
　}
}

↑の訂正です↓

public void addBeforeTail(int el) {
　if (isEmpty() || head==tail) {
　　addToHead(el);
　}
　else {
　　IntNode tmp;
　　for (tmp=head; tmp.next!=tail; tmp=tmp.next);
　　tmp.next=new IntNode(el,tail);
　}
}

空でも１つでも addToHead() でいけますね。
失礼。

お礼

ありがとうございます。

間違いには気付きましたがもうだめぽいです。
忙しすぎて咀嚼せずに飲み込むような勉強しかできないんですよね、明日もまた授業が…。
もういっそ回線切って首[以下略]

回答No.3

takaP-

>public int addBeforeTail() {
>int el = tail.info;
>if (head == tail) // if only one node in the >list;
>head = tail = null;
>else { // if more than one node in the list,
>IntNode tmp; // find the predecessor of tail;
>for (tmp = head; tmp.next != tail; tmp = >tmp.next);
>tail = new IntNode(el);
>tail.next = tail;
>}
>return el;
>}

ん？？

public void addBeforeTail(int el) {
　if (isEmpty()) {
　　addToHead(el);
　}
　else if (head==tail) {
　　head=new IntNode(el,tail);
　}
　else {
　　IntNode tmp;
　　for (tmp=head; tmp.next!=tail; tmp=tmp.next);
　　tmp.next=new IntNode(el,tail);
　}
}

こんな感じじゃないでしょうか（もっと綺麗に書けるかもしれないけど・汗）
そもそも、引数無しではどうにもやり様がないはずですよ。
他にも。。。

public void addBeforeTail(int el) {
　if (isEmpty()) {
　　addToHead(el);
　}
　else {
　　int i=deleteFromTail();
　　addToTail(el);
　　addToTail(i);
　}
}

という手もありますが、厳密な意味での連結リストの挿入法からは外れるでしょうから、やはり最初のような処理が良さそうな気がしますね（継承を使うならこれになるでしょうけど）

間に合えば良いのですが。。。

お礼

あーっ、tail.nextではなくて、tmp.nextだっとわぁーっ!!
せっかく最後から二番目の位置見つけたのに使ってない…。
小さい勘違い、大きな減点…ああ、激しく鬱です。
もう提出したので逆立ちしても間に合いません(泣)。
崖っぷちはもう通り越して落っこちたようです。
はぁー…鬱です、鬱です、欝です。
ありがとうございました。

回答No.2

noname#30871

図でも描いて落ち着いて考えれば簡単です。

　単方向連結リストの先頭要素をＨ、末尾要素をＴとすれば

Ｈ→…→Ｔ　　　　...(a)

と表現できます。これは大丈夫でしょうか。

また、「末尾の一つ前の要素」をＰとすれば、(a)は

Ｈ→…→Ｐ→Ｔ　　　　　...(b)

と描くことができます。

　さて、上記の連結リストに新たな要素Ｎを挿入します。Ｎはどこに入るでしょうか。答は

Ｈ→…→Ｐ→Ｎ→Ｔ　　　　　...(c)

となりますね。つまり、今回のメソッドでは(c)を作ればよいのです。もう少し噛み砕いて言えば、メソッドの中では

(1) Ｐを求める。
(2) Ｎをnewする。
(3) ＰとＮを連結する。
(4) ＮとＴを連結する。

という手順になります。Ｐの求め方は、#1のご回答のとおり。

　ところで、そんなに回答を求めているのであれば、せめて問題文の和訳を付けるべきです。Javaができる人が英語を読めるとは限りません。

お礼

>問題文の和訳

すみませんでした。
以前「みんな英語が読めるはずだから和訳なんかつけるな」ってクレームがついたんで(しかもその人、回答もせずにクレームだけでした)、書かないことにしたんです。
でも、プログラムのが得意な人がみんな英語が出来るとは限りませんよね。
次回は付けます。

私の成果のほどはどうでしょうか?
正直、まだ慣れてないのでコピーして修正するのが精一杯です。
間違っていたらご指摘下さい。
ありがとうございました。

補足

只今、奮戦中です。しばらくお待ち下さい。m(__)m

回答No.1

m_hagizo

>上の私自作のメソッドであってますでしょうか?
はっきり言ってしまうと、間違っています。

考え方としては、どうにかしてtailの１個前のノードのnextを書き換えてあげなければいけません。
では、previousが無いのにどうやってtailの１個前のノードを知るのか、というと、そのヒントはIntSLListのdeleteFromTailというメソッドにあります。

deleteFromTailでは、tailの１個前のノードを発見し、そのノード自体をtailにセットすると共に、nextにnullをセットすることで、「次のノードはなくなっている」ということを認識させています。

これを応用すれば、tailの１個前のノードに新しいノードを追加することは容易でしょう。

敢えてズバリな回答は控えておきます。

ちなみに、このクラスにmainメソッドがないのは、様々なプログラムで利用されることを前提にしているためです。自分で、以下のような感じに、このクラスをテストするクラスを作って試してみるとよいでしょう。
public class RunTest {
public static void main(String[] args) {
IntSLList list = new IntSLList();
list.addToTail(30);
list.addToTail(50);
list.addToTail(100);

list.printAll();
System.out.println();

list.addToHead(10);

list.printAll();
System.out.println();

list.addBeforeTail(80);

list.printAll();
System.out.println();
}
}

お礼

出来ましたーっ(多分)。

では成果のほどを。
public int addBeforeTail() {
int el = tail.info;
if (head == tail) // if only one node in the list;
head = tail = null;
else { // if more than one node in the list,
IntNode tmp; // find the predecessor of tail;
for (tmp = head; tmp.next != tail; tmp = tmp.next);
tail = new IntNode(el);
tail.next = tail;
}
return el;
}
最後から二番目を見つけるまではdeleteFromTailとまったく同じです。
それからは普通に現在のtailに新しいノードを追加してtail.nextをtailにしました。
これでいいんですよね?

実はもう提出しました。
時間がなかったので焦って
最後のreturn el;と}、忘れちゃいました…
教授、そんな細かいことで点ばっさり引かないでね(と祈る私)。

もう一日だけ締め切らずにおきます。
あっているようであれば返事はいりませんが、
間違っているようであれば指摘してやって下さい。
ありがとうございました。

補足

基にすべきだったのはdeleteFromTailだったんですね!
只今、奮戦中です。しばらくお待ちください。m(__)m