Q&A
何と比較しての話なのかを明確にされると良いかと存じます
双方向リストにおいて、利点は末尾への参照がO(1)になるなどありますが、
一般的な片方向連結リストに比べて
欠点は全くないのでしょうか？
ご教示願います。
メンテがめんどいのは欠点じゃないのかなあ。
「順序列」としての利点/欠点というのなら、配列との比較かもしれませんしね。
すみません、配列ではなく片方向連結リストとの比較です。
片方向でも末尾の参照は O(1) にできますし、双方向でも O(n) にできます。これはヘッダの仕様に依存するもので、本質的に片方向・双方向とは無関係です。
本来ヘッダは先頭リストを指しており、最後尾を探すために先頭から辿る必要があるので単一方向リストはO(n)だと思ったのですが、
そのヘッダに最後尾へのポインタを追加すれば O(1) になります。最後尾にノードを追加していくことの多いリストの場合、いちいち最初からたどるのではパフォーマンスが悪いので、そのような実装にすることも多いです。
すみません、双方向リストは先頭と末尾が繋がっているものと誤認していました。
その場合は、単一方向リストではなく、循環リストの場合であっていますよね。
つまり、最初のノードをそのままヘッダとして使うのではなく、最初のノードの前にヘッダ専用の型のオブジェクトがあるリストですね。
すみません、その場合は双方向リストと循環リストの合体のような場合でした。
循環はしていません。最後尾のノードは何も指さなくて良いので。
循環と方向は別の次元の話になります。
回答4件
0
単方向リストに較べると、戻り分、余分なポインタが増える。
逆方向に辿るのは容易ですが、挿入時に、一手間(逆方向ポインタ)増える。
他にもあるかも知れませんが、万能でしたら、全てこれになってしまう。
まあ、適材適所。
投稿2019/08/12 01:39
総合スコア6385
ベストアンサー0
こんにちは。
双方向リストにおいて、利点は末尾への参照がO(1)になるなどありますが、
欠点は全くないのでしょうか？
利点／欠点は何かと比較してより優れている／より劣っているですから、比較対象が必要です。
単なる連結リストではなく、双方向リストということなら比較対象は単方向リストでしょう。
この場合、管理領域（オーバーヘッド）が大きい分、メモリをより多く消費します。
投稿2019/08/12 02:04
総合スコア23274
> 比較対象が必要です
それを明確にしろという修正依頼を出しているのだが，その返事すら待ちきれない人が多くて草です
私の回答のリンク先には、単方向および配列との比較が載っています。返事を待つまでもなく、それで十分と判断しましたが、それ以上のものが必要でしょうか？ それ以上に範囲を広げると違いがありすぎて書ききれなくなるのではないかと思います。
「双方向」とわざわざ書いてある時には、その比較対象は明示されない限り単方向ではないかとは思いますが、「末尾への参照が……」との言及から、質問者さんが連結リストのつもりで書いている可能性も排除しきれないので、このあたりが比較対象として適当かなと思いました。
適当だと思いますが，微妙にあやふやさがある範囲に関して誰かが問うている途中状態があるなら，それを利用すれば（そこが明確になってから回答を書けば）
> 双方向リストということなら
みたいなアバウトさを含むような前置き等も要らなくなるのになぁ，とか．それだけです．
fanaさん
この件はここで議論するような内容ではないと思います。
teratailタグにて別途質問を立てて頂けるとありがたいです。
確かにきっちりしておきたいですが、それをすると例の質問のように「お前は知識がないから無駄なことを聞くんだ」と突然怒りだす人がいるのでなかなかバランスが難しいところです。
「データ構造の種類」的な括りの話における課題だったりすると，比較範囲は単方向だけでは不足かも？とか想像して問うておいたのですが，まぁ割とどうでもいいです．失礼しました．
すみません、比較対象を明示せず混乱させてしまい申し訳ございませんでした。また、提示してないにも関わらず、単一方向リストと汲み取っていただき感謝いたします。これからは曖昧な質問がないよう努力します。
0
双方向リストは片方向連結リストに比べて:
- 実装がちょびっと(?)ややこしい
- 各要素がポインタをふたつ持つのでその分メモリ食う
投稿2019/08/13 02:27
総合スコア16612
ありがとうございます。メモリとオーダーはトレードオフということですね！
要素サイズが十分大きければポインタいっこくらい誤差かもですが
ありがとうございます。末尾に追加していくものや、消去したいノードがわかっているときみたいな目的が明確であるときに双方向リストを採択する意味があるとわかりました。
> 要素サイズが十分大きければポインタいっこ
要素数が多い、と無視できなかったり、、。
今、自分で書く程度のプログラムでは誤差ですが。
わざわざありがとうございます。
あなたの回答
tips
プレビュー
