次の項目のタイムライン: ハッシュ表のチェイン法による実装における単方向or双方向連結リストの比較
現在のライセンス: CC BY-SA 4.0
5 件のイベント
日時 書式を切り替える | 内容 | ユーザー | ライセンス | コメント | |
---|---|---|---|---|---|
2019年7月5日 4:36 | 投票 | 承認 | Akiyama Nao | ||
2019年6月7日 5:23 | コメント | 追加済み | yudedako | 実際の有用性という意味で見ると、双方向リストにすることにそれほどメリットはないと思います。一つはおっしゃられるように、そんな使い方そうそうしないだろうという点で、 もう一つは単方向リストでも削除は検索と同じ計算量ででき、たいていはそれで充分という点です(うまく実装すれば平均O(1)。ただしその場合でも最悪O(N)なので双方向リストを使うことで最悪O(1)に改善できる)。 | |
2019年6月7日 3:11 | コメント | 追加済み | Akiyama Nao | まぁ双方向のほうが多少メモリ使うけど、ノードが特定できてたら双方向のほうがO(1)で削除できて速いというメリットが教示できるから 単方向よりは素直にこれ使ったほうがいいでしょ、ということですかね。 | |
2019年6月7日 3:09 | コメント | 追加済み | Akiyama Nao | なるほど、ありがとうございます。 いただいた説明や英語版の質問を読んで以下のように理解しました。 - 双方向を使って、削除の対象がノード自体のときは、prev, nextのノードを探索する必要なくつなぎ替えることができるのでO(1) - ハッシュ表のキーを指定して削除するなら、単方向も双方向もO(N) ただ、そもそもハッシュ表に入ってるノードが手元にあってにあって、 それを使って削除するシーンってそんなにあるんですかね。 大体はキーを指定して削除するような。。。 たとえば、 delete user_hash[user_id] なオペレーションするときって、まずはuser_hash[user_id]のノードをO(N)で探索しますよね。 そのあとでO(1)で削除。 もし user = user_hash[user_id] で一度ノードを取得しておいてそのあとで、いろいろごにょごにょやって、その後で delete user とかならO(1)で削除できて今回の有用性が大変理解できます。 | |
2019年6月6日 14:00 | 履歴 | 回答済み | yudedako | CC BY-SA 4.0 |