リスト構造の特徴として、リストの可変長データの便利さの反面、 シーケンシャルアクセスしかできないため、N番目データの参照がO(N)で 効率が悪い点を再確認したあと、その問題の解決方法として、双方向リストを説明する。

テキストエディタのような、１つ前の行、次の行をアクセスするような処理が多い場合、 単純リストでは、1つ前の参照は効率が悪い。 その対策として、１つ前のデータの場所を保存すればよい。

struct BDList {
struct BDList* prev ;
int            data ;
struct BDList* next ;
} ;
void bdinsert( struct BDList* p , int x ) {
struct BDList* n ;
n = (struct BDList*)malloc( sizeof( struct BDList ) ) ;
if ( n != NULL ) {
n->data = x ;
n->prev = p ;
n->next = p->next ;
p->next->prev = n ;
p->next = n ;
}
}

しかしながら、このプログラムは、データが数件存在している場合は正しく動作するが、 データ件数が0件の場合には、問題が発生する。 データ件数が0の状態で、top = NULL であれば、この場合だけの特別処理を 記載することになる。これは、効率も悪いしプログラムも分りにくくなる。 この対策として、データ0件の状態を作らなければいい。このため、ダミーのデータを つくりリストの最前端と最後端に入れておけば特別処理が不要となる。 このような、データの端に処理の簡略化のために入れるデータを番兵(sentinel)と呼ぶ。

しかし、双方向リストでは、最前端と最後端に番兵を設けなくても、最後端の１つ前が、 最前端のデータを指すように循環リストを構成してやれば、番兵が１つで済む。 双方向リストでは、このような『双方向循環リスト』として扱う場合が多い。

説明補足用の図がいいのがないかなぁ～と、Google の画像検索をかけると、 イマイチな図ばっかり…と数回次次次とみていって、良い絵をみつける。 けど、よくみりゃ去年自分で書いた図だった…