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

シーケンシャルアクセス・ランダムアクセス

もう１つの欠点がシーケンシャルアクセスとなる。テープ上に記録された情報を読む場合、後ろのデータを読むには途中データを読み飛ばす必要があり、データ件数に比例したアクセス時間を要する。このような N番目 データ参照に、O(N)の時間を要するものは、シーケンシャルアクセスと呼ばれる。

一方、配列はどの場所であれ、一定時間でデータの参照が可能であり、これは ランダムアクセスと呼ばれる。N番目のアクセス時間がO(1)を要する。

このため、プログラム・エディタの文字データの管理などに単純リストを用いた場合、１つ前の行に移動するには、先頭から編集行までの移動で O(N) の時間がかかり、大量の行数の編集では、使いものにならない。ここで、シーケンシャルアクセスでも１つ前にもどるだけでも処理時間を改善してみよう。

双方向リスト

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

// データ構造宣言
struct BDList {
    struct BDList* prev ; // 一つ前のデータへのポインタ
    int  data ;
    struct BDList* next ; // 次のデータへのポインタ
} ;
// データ生成補助関数
struct BDList* bd_cons( struct BDList* pr , int x , struct BDList* nx ) {
    struct BDList* ans ;
    ans = (struct BDList*)malloc( sizeof( struct BDList ) ) ;
    if ( ans != NULL ) {
        ans->data = x ;
        ans->prev = pr ;
        ans->next = nx ;
    }
}
// つかってみる
void main() {
    struct List* top = bd_cons( NULL , 1 ,
                       bd_cons( NULL , 2 ,
                       bd_cons( NULL , 3 , NULL ) ) ) ;
    top->next->prev = top ;
    top->next->next->prev = top->next ;
}

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

void insert( struct BDList* p , int x ) {
    struct BDList* n ;
    // ポインタの理解のため、あえて bd_cons() は使わない
    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 ;
    }
}
void main() {
    struct BDList* top = .... ;
    :
    insert( top->next , 11 ) ; // 問1. どういう順番にデータが並ぶ？
    insert( top , 0 ) ;        // 問2. 先頭にデータが入る？
}

この insert() では、先頭に入れることができない。かといって、先頭に入れるため専用の別関数を作るのは煩雑。このため、双方向リストの先頭と末尾には、ダミーデータを入れた番兵を置くのが一般的。また、その際にダミーが２ヶ所あるのもムダなので、循環リストにして末尾データと先頭データを兼用する。(双方向循環リスト)

問題提起

ここまでで、配列やリスト構造を使ったアルゴリズムを話してきたが、どの程度効果があるのだろうか？
配列やリストにデータを保存しておいて、目的とするデータが含まれていなかったらデータを追加するという処理を考える。

リスト構造で高速にデータを探せる方法は無いのか？