前回のリストを使った集合演算のように、データを連ねたリストは、 単純リストとか線形リストと呼ばれる。 特徴はデータ数に応じてメモリを確保する点や、途中へのデータの挿入削除が得意な点 があげられる。 一方で、配列は想定最大データ件数で宣言してしまうと、 実際のデータ数が少ない場合、メモリの無駄も発生する。 しかし、想定件数と実データ件数が一致していれば、無駄も必要最小限となる。 リスト構造では、次のデータへのポインタを必要とすることから、 常にポインタ分のメモリは、データにのみ注目すれば無駄となる。

もう１つの欠点がシーケンシャルアクセスとなる。 テープ上に記録された情報を読む場合、後ろのデータを読むには途中データを読み飛ばす 必要があり、データ件数に比例したアクセス時間を要する。 一方配列は、どの場所であれ、一定時間でデータの参照が可能であり、これは ランダムアクセスと呼ばれる。O(1)のアクセス時間。 線形リストは、シーケンシャルアクセスを行うため、データ件数が増えれば N番目 データの参照には、O(N)の時間を要する。

このため、エディタの文字データの管理などに単純リストを用いた場合、 １つ前の行に移動するには、先頭から編集行までの移動で O(N) の時間がかかり、 大量の行数の編集では、使いものにならない。

これらの問題に対応するために、１つ前のデータへのポインタを保存する、 双方向リストが利用される。

struct BDList {
struct BDList* prev ;
int  data ;
struct BDList* next ;
} ;

このデータ構造の特徴を理解してもらうための簡単なプログラムとして、 双方向リストの指定ポインタの前に１件データ挿入を紹介。

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