![[*]](crossref.png)
)。
前にも、後ろにもリンクをたどれるためには、前後のオブジェクトへの
ポインタを有していれば良い。そこで、双方向リンクドリストの構造体の
定義は、次のようにすれば良いであろう(図 )。
struct dLINK {
struct dLINK *prev; /* 前のオブジェクトへのポインタ */
struct dLINK *next; /* 後ろのオブジェクトへのポインタ */
void * data;
};
|
双方向リンクドリストで重要な点は、リストの両端にあるオブジェクトでは、必ず prev か、あるいは next 変数の何れかが NULL になっている点である。 双方向リンクドリストでは、片方向リンクドリストと違って、特別な先頭アドレス を覚えておく必要はなく、リストのどれかのオブジェクトの位置さえ失わなければ 、常にリストの全オブジェクトが得られるが、そのためにリスト中を行ったり来たり しなければならなくなるので、効率という点からするとやはり先頭アドレスを 保持していた方が良いであろう。
双方向リンクドリストは更に応用として、リングバッファに利用出来る。リング は文字どおり円環上にメモリがなっているようなもので、双方向リンクドリストの 両端の prev,next 変数に NULL を入れるのではなく、先頭は末尾に、末尾は先頭 に繋げてしまうのである。これによって、先頭という概念は失われるので、 どこから検索をしても丁度一周で全てのデータを検索出来るという利点 がある(先に述べたように双方向リンクドリストでは先頭を保持していなければ、 一旦先頭あるいは末尾に戻ってからそこから検索をしなければならないので、 その分余分な処理をしなければならない事になる）。一方、そのために順序関係 は失われるので、順序関係のあるデータには用いる事が出来ない。 双方向リンクドリストを用いたリングバッファには、その他にも リストなので常にデータを追加出来るという利点もある。
この他にも、双方向リンクドリストには片方向リンクドリストに比較して、 一つ余分にポインタ変数を使うためにメモリを余分に使うという欠点があるが、 メモリを節約したい場合には、prev と next の xor 演算を取ったものを 格納するという方法もある(xor 演算では、A xor B = C ならば、B xor C=A, C xor A = B という性質がある)。これによって、前後どちらかのアドレスが 分かっている場合には、反対側のオブジェクトへのアドレスは xor 演算を 施すことによって計算出来ることになり、双方向の利便性と、片方向の メモリの節約という２つの性質を同時に持つことが出来るが、その一方で 演算処理が増えるという欠点がある。こうした二律背反は、時間とスペースの トレードオフ問題として知られている。
