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

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

ただいまの
回答率

90.48%

  • C

    3810questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

ある本で「削除が高速にできる双方向連結リスト」とあったのですが何故か?

解決済

回答 6

投稿

  • 評価
  • クリップ 0
  • VIEW 1,393
退会済みユーザー

退会済みユーザー

双方向リストは一方向より早いのでしょうか?
それは何故でしょうか?

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 6

+7

双方向という事は前後へのリンク情報も保持しているという事なので削除対象が特定されている時点で削除物の前にあるデータと削除物の後にあるデータを連結して削除対象物をリストから除外するという整理操作がその場ですぐに解決できますが、例えば片方向(後方)の場合だと、削除対象が特定されていても削除物の前にあるデータは検索しないと特定できないので双方向の時に比べると検索コストが余計にかかってしまう理屈になります。

[例]
A→B→C から B を削除したい場合に
1.「Aの次がBである」を「Aの次はCである」に変更
2.「Cの前がBである」を「Cの前はAである」に変更(双方向の場合)
をしなくてはなりませんが、
・双方向ならBがAとCへのリンク情報を持っているのでBだけですぐにAとCを特定できる
・片方向ならBはCへのリンク情報しかもっていないのでAの特定には検索が必要
という違いがあります。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

checkベストアンサー

+2

prev -> here -> next で現在hereをポイントしてて、hereを削除となると
削除要素のひとつ前:prevをポイントせにゃならんので速くはなさそう。

が、ゴマカシが許されるなら nextのナカミをhereにコピーしたのちnextを削除することで hereが削除されたようにみせかけることができます。
ただし、
1.コピーのコストが大きいと速くない(ポインタ張替えの方が速いなら、双方向の方が速いことになる)
2.末尾要素が削除できない

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/06/01 20:35 編集

    おお!
    その削除の方法は気付かなかったのでベストアンサーにしようかと思ったのですがプログラムの他のところにhere,nextをポイントして使ってる部分があったらバグになっちゃうのかと思ったのですがどうでしょうか。

    キャンセル

  • 2018/06/01 21:55

    ですね、どっかヨソでnextをポイントしてる誰かさんに迷惑をかけることになります。
    とはいえ、双方向でも here をポイントしてる誰かさんに迷惑をかけるわけだし。

    キャンセル

  • 2018/06/02 01:42

    いや、消す要素が全体に比べて少ないものの膨大な場合は削除処理を非同期化できるというメリットが・・・

    キャンセル

  • 2018/06/02 19:58

    あーいや、なんでもない、間違って読んでいた

    キャンセル

+1

多分に推測になりますが、双方向連結リストで「削除が高速にできる」の比較対象は一方向リストではなく、配列などリストでないデータ構造なのではないかと思います。

配列であれば途中の削除は「残りを全部ずらす」しかないのでリスト構造のほうが有利ですが、一方向リストに対しては優位になりません。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/06/01 10:25

    ただ、ポインタで指したような「この要素」を削除したいとなった場合は、双方向リストであればそこから両方向のポインタをたどって削除すればいいのに対して、一方向リストの場合は「前」がわからないので、リストを改めてたどる必要が出てきます。

    キャンセル

+1

単方向リストで、「ポインタが指している要素を削除する」という関数を実装することを考えてみると分かるかと。根本から、その要素までず~~~と辿らないといけない。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

解決済みですが。

皆様おっしゃられる通り、以下のようなリストを考えます。
head->p1->・・・->p11->p12->p13->・・・
ここでp12を削除する場合を考えると、p11のポインタを書き換える必要があります。しかし、フォーカス(巡回用ポインタ)がp12を指示しているならば、先頭から辿らないとp11のポインタを変更できないので手間がかかります。

 ただし、これはフォーカスの運用次第です。

フォーカスを二つ使うとか、先読運用(例えばp11を指しているときにp12に対する処理を行う。)とか、解決する方法がないわけではありません。

 蛇足

非常に変則な形ですが、フォーカスだけ双方向ポインタをもち、これを中心にリストの向きを変更していくといったリストの使い方もあります。

head<-p1<-・・・<-p11<-[focus]->p12->p13->・・・

これはメモリ容量が小さいときに使われていた小手先の技術なので推奨はしません。読み取りだけでもデータ改変が必要なので、現在はむしろ悪手です

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

一方向は逆方向にたどれないし、削除と言ってもリンクの付替えだけで済むから。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

関連した質問

  • 解決済

    リスト同士で重複する要素を削除したい

    javaで2つのリストに含まれる要素のうち、重複する要素だけを削除する方法を教えてください。 (例) リストA{東京,千葉,埼玉,神奈川} リストB{千葉,茨城,岐阜,神奈川}

  • 解決済

    jqueryでCtrl+Fのような事をやりたい

    jqueryで画面遷移なしでCtrl+Fのような事をやりたいのですが、 有効範囲はテーブル内の一列の対象文字列を検索したいのですがjqueryは初心者で解らない事だらけです。 サン

  • 解決済

    Pythonでの質問

    かなり初歩的に質問になってしまうのですが y = [0.0] * len(x) このような分に例えばxに100が入っていたとしてyは何になるのでしょうか どのような理

  • 解決済

    wordpressのプラグインでおすすめのメールマガジン配信プラグインを教えて下さい。

    下記の内容が実現可能なメールマガジンプラグインを探しています。 おすすめのプラグインがありましたら、教えていただければ幸いです。 登録フォーム(名前・住所・配信希望カテゴリ

  • 解決済

    数列に新しい性質の数列を追加したい

    このコードは 例えばだんだん増加する数列([1,4,5,76,89])ならその要素の和を求めて、 だんだん小さくなる数列([5,4,2,-4])ならその要素の平均を求めているん

  • 受付中

    value="url"使わずにselectで選んだ値に応じて[button_to_cart item...

    こんにちは JavaScriptを利用した見積もりフォームから selectで選んだ値に応じて動的リンクを作って飛ばしたい。 見積もりフォームでvalueを使っている

  • 解決済

    for文での配列の保存の仕方

    Pythonをつかい for文を回していくごとに一回目に[a b c d],二回目に[e f g h],三回目に[i j k l]のような配列ができるのですが、for文を回すごとに

  • 解決済

    [python] リスト内の数値を文字列に変換したい

    リスト内にある数字を文字列に変換したくてコードを書いたのですが、所望の結果が得られず、<map at 0xde2e6d0>のような結果が返ってきます。 リスト内の数字を文字列に

同じタグがついた質問を見る

  • C

    3810questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。