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

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

質問する

ただいまの
回答率

90.96%

  • C

    3112questions

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

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

受付中

回答 4

投稿

  • 評価
  • クリップ 0
  • VIEW 182
fao

fao

score -39

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

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 4 件

link

+4

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

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

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

link

0

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

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

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/06/01 10:25

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

    キャンセル

link

0

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

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

link

-1

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

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/06/01 10:23

    逆方向にたどれることで削除が速くなる理由がわかりません
    単方向だと一箇所のリンクの付替えで双方向だと二箇所で遅くなりせんか？

    キャンセル

  • 2018/06/01 10:48

    その本では一方向より双方向のほうが早くなる、とかいてあるのでしょうか？
    も一度読み直してはどうでしょう

    キャンセル

  • 2018/06/01 11:08

    最初と言ってること違うね

    キャンセル

  • 2018/06/01 11:13

    どこが？

    キャンセル

  • 2018/06/01 11:38

    「削除と言ってもリンクの付替えだけで済むから」
    これ詳しく説明しろ
    間違ってんだろ

    キャンセル

  • 2018/06/01 11:40

    ああ、そういうテの人でしたか
    人に教えを乞うような態度じゃないですねえ
    育ちが察せられます
    こまったもんだｗ

    キャンセル

  • 2018/06/01 11:42

    何でそんな知識レベルで人に教えてんの？
    適当なこと教えられても迷惑なんだわ

    キャンセル

  • 2018/06/01 11:43

    はいはい、よかったですねｗ

    キャンセル

  • 2018/06/01 11:44

    議論の内容じゃなくて態度気にしちゃうのか
    受けた教育レベルが察せられます

    キャンセル

  • 2018/06/01 11:46

    あらあら、また困ったちゃんですねー
    ひとに対してものを教えてもらうときは、おねがいします、教えてください、と頭を下げなさいとおかーさんに教えてもらわなかったですか？

    このよのなかでいきていくにはひつようなことですので、おぼえておきましょうねーｗ

    キャンセル

  • 2018/06/01 11:48

    黙れニート
    社会不適合者がなに言ってんの？

    キャンセル

  • 2018/06/01 11:50

    じこしょうかいでしょうか。
    よのなかつらいことばかりでしょうけど、つよくいきていきましょうね。

    キャンセル

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

  • ただいまの回答率 90.96%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる
質問する

関連した質問

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

  • C

    3112questions

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

SNSアカウントでログイン

  • Facebookでログイン
  • Twitterでログイン
  • Googleでログイン
  • Githubでログイン
  • Hatenaでログイン

teratailアカウントでログイン

思考するエンジニアのためのQ&Aサイト「teratail」について詳しく知る