豚吐露＠wiki
問20回答
最終更新：
ohden
-
view
ウ
片方向リンクと双方向リンクのイメージは以下の通り。
片方向リンク
双方向リンク
片方向リンク
双方向リンク
片方向リンクよりオーバヘッドが小さい。
オーバーヘッドとは、目的の処理以外でかかる時間を指す。
プログラム自体の問題や、ディスクアクセスにかかる時間などが原因で発生する。
データサイズが同じであれば、目的の情報の取得にかかる時間は同じである。
オーバーヘッドとは、目的の処理以外でかかる時間を指す。
プログラム自体の問題や、ディスクアクセスにかかる時間などが原因で発生する。
データサイズが同じであれば、目的の情報の取得にかかる時間は同じである。
追加は、最後尾だけに対して行える。
リンク構造さえ維持していれば、最後尾以外へのキューの追加は可能である。
リンク構造さえ維持していれば、最後尾以外へのキューの追加は可能である。
途中への挿入・取外しが容易に行える。
リンク構造のとき、途中へキューの挿入・取外しを行う場合を考える。
片方向リンクの場合、挿入位置の『前データの次データへのリンク』を修正する必要があるが、前データを特定するためにはリンク先頭から辿っていく必要がある。
双方向リンクの場合、挿入位置の『前データの次データへのリンク』『挿入位置データの前データへのリンク』を修正する必要があるが、挿入位置のデータは『前データへのリンク』を保持しているため、挿入辞にリンク先頭から辿っていく必要が無い。
取外しの場合も同様で挿入位置の『前データの次データへのリンク』『次データの前データへのリンク』を修正する必要がある。
よって、双方向リンクの方が途中への挿入・取外しが容易に行える。
リンク構造のとき、途中へキューの挿入・取外しを行う場合を考える。
片方向リンクの場合、挿入位置の『前データの次データへのリンク』を修正する必要があるが、前データを特定するためにはリンク先頭から辿っていく必要がある。
双方向リンクの場合、挿入位置の『前データの次データへのリンク』『挿入位置データの前データへのリンク』を修正する必要があるが、挿入位置のデータは『前データへのリンク』を保持しているため、挿入辞にリンク先頭から辿っていく必要が無い。
取外しの場合も同様で挿入位置の『前データの次データへのリンク』『次データの前データへのリンク』を修正する必要がある。
よって、双方向リンクの方が途中への挿入・取外しが容易に行える。
取外しは、先頭だけに対して行える。
リンク構造さえ維持していれば、先頭以外へのキューの取外しは可能である。
リンク構造さえ維持していれば、先頭以外へのキューの取外しは可能である。
更新日： 2009年11月17日 (火) 13時55分29秒
[Amazon商品]
ASINが有効ではありません。
