質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

Q&A

解決済

2回答

6289閲覧

単方向連結リストの実装例

退会済みユーザー

退会済みユーザー

総合スコア0

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

0グッド

0クリップ

投稿2016/08/24 10:05

以下に示すコードは単方向リストの非常に簡単な実装例です。
しかし、これでいいのだろうかと思う点がありますので、皆さんにそれをお聞きしたいです。

Java

1class Node { 2 Node next = null; 3 int data; 4 5 public Node(int d) { 6 this.data = d; 7 } 8 9 void appendToTail(int d) { 10 Node end = new Node(d); 11 Node n = this; 12 while (n.next != null) { 13 n = n.next; 14 } 15 n.next = end; 16 } 17 18 Node deleteNode(Node head, int d) { 19 Node n = head; 20 21 if(n.data == d) { 22 return head.next; /*ノードの先頭を移動*/ 23 } 24 25 while (n.next != null) { 26 if(n.next.data == d) { 27 n.next = n.next.next; 28 return head; /*ノードの先頭は変化しない*/ 29 } 30 n = n.next; 31 } 32 return head; 33 } 34}

deleteNodeメソッドがよくわかりません。
単方向連結リストからノードを削除する方法というのは、例えばノードnが与えられたとして、一つ前のノードprevを探し、prev.nextをn.nextに置き換えるというものだと思います。
このメソッドではそれが実現されていますが、引数でNode型の参照を取るのは、渡したノードから数えられるようにということでいいのでしょうか?
つまり、削除のたびに最初から調べ上げていくのではなく、途中からでもその検索を始められるようにこのような形にしていると思ったのですが、どうでしょうか?
それともう一点あるのですが、戻り値がheadになっています。
ということは連結リスト内の要素(headの次の要素ではない)を二つ削除した時に返ってくるNodeは同一ということですよね?(もちろん連結リストは変わりますが)
このような戻り値にする意味はあるのでしょうか?
今まで見たものだと削除した時に戻ってくるのはその削除した要素もしくはvoidだったので、少し戸惑っております。
わかる方、回答お願いします。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

本来このような連結リストのノードを使う場合、ノードとは別に最初のノードを参照するオブジェクトが存在するのが通常です。そのオブジェクトをリストとして扱うことで、リストの最初から捜査して全要素にアクセスできるようにしているのが連結リストの実装です。おっしゃるような

それともう一点あるのですが、戻り値がheadになっています。

ということは連結リスト内の要素(headの次の要素ではない)を二つ削除した時に返ってくるNodeは同一ということですよね?(もちろん連結リストは変わりますが)
このような戻り値にする意味はあるのでしょうか?
今まで見たものだと削除した時に戻ってくるのはその削除した要素もしくはvoidだったので、少し戸惑っております。

という不具合、と言うか不都合が起きているのは、最初のノードを参照するオブジェクトが存在しない制です。

投稿2016/08/25 15:36

swordone

総合スコア20649

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

ベストアンサー

このクラスを使う側では、先頭のNode インスタンスだけを使うようにできてそうです。

static void main() { Node list = new Node(0); list.append(1); list.append(10); ... list = list.deleteNode(10); list.deleteNode(0); // list はそのままなので削除したことにならない list = list.deleteNode(0); // list が変わる (list.data==1) }

しかしながら、こういう使う側が注意しなければならないクラスは良い実装とは思えません。

投稿2016/08/24 11:57

yskz44

総合スコア100

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2016/08/24 13:59

戻り値をheadにする意味はあるのでしょうか? 普通はデータ(この場合int型の整数)を返すと思うのですが。
yskz44

2016/08/24 14:20

私もそうだと思いますよ。 でも、このクラスだと、 headもNodeクラスのインスタンスなので、先頭のNodeのデータを削除するこうするしかないのでしょう。
退会済みユーザー

退会済みユーザー

2016/08/25 01:01

回答ありがとうございました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問