ランダムアクセス・シーケンシャルアクセスから双方向リスト

ランダムアクセスO(1)とシーケンシャルアクセスO(N)の説明を踏まえ、リスト構造のO(N)の改善にむけた解説を行う。

リスト構造の利点と欠点

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

例えば、整数型のデータを最大 MAX 件保存したいけど、実際は それ以下の、平均 N 件扱うとする。この時のメモリの使用量 M は、以下のようになるであろう。(sizeof()はC言語での指定した型のメモリByte数を返す演算子)

配列の場合	リスト構造の場合
	(ただしヒープ管理用メモリ使用量は無視)

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

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

一方、配列はどの場所であれ、一定時間でデータの参照が可能であり、これは ランダムアクセスと呼ばれる。N番目のアクセス時間がO(1)を要する。配列であれば、N/2 番目のデータをO(1)で簡単に取り出せるから2分探索法が有効だが、リスト構造であれば、N/2番目のデータを取り出すのにO(N)かかってしまう。

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

単純リストから双方向リストへ

ここまで説明してきた単純リストは、次のデータへのポインタを持つ。ここで、１つ後ろのデータ(N番目からN+1番目)をアクセスするのは簡単だけど、１つ前のデータ(N-1番目)を参照しようと思ったら、先頭から(N-1)番目を辿るしかない。でも、これは O(N) の処理であり時間がかかる処理。
ではどうすればよいのか？

この場合、一つ前のデータの場所を覚えているポインタがあれば良い。

Javaの場合

import java.util.*;

class BDListNode {
    BDListNode prev ;
    int        data ;
    BDListNode next ;
    
    BDListNode( BDListNode p , int d , BDListNode n ) {
        this.prev = p ;
        this.data = d ;
        this.next = n ;
    }
}

public class Main {
    public static void main(String[] args) throws Exception {
        BDListNode top
            = new BDListNode( null , 1 ,
                 new BDListNode( null , 2 ,
                    new BDListNode( null , 3 , null ) ) ) ;
        top.next.prev = top ;
        top.next.next.prev = top.next ;
        for( BDListNode p = top ; p != null ; p = p.next )
            System.out.println( p.data ) ; // 1,2,3
        for( BDListNode p = top.next.next ; p != null ; p = p.prev )
            System.out.println( p.data ) ; // 3,2,1
    }
}

• Javaによる双方向リスト

C言語の場合

// 双方向リストの宣言
struct BD_List {
    struct BD_List* prev ; // 1つ前のデータへのポインタ
    int             data ;
    struct BD_List* next ; // 次のデータへのポインタ
} ;

このデータ構造は、双方向リスト(bi-directional list)と呼ばれる。では、簡単なプログラムを書いてみよう。双方向リストのデータを簡単に生成するための補助関数から書いてみる。

// リスト生成補助関数
struct BD_List* bd_cons( struct BD_List* p ,
                         int d ,
                         struct BD_List* n ) {
    struct BD_List* ans ;
    ans = (struct BD_List*)malloc(
                         sizeof( struct BD_List ) ) ;
    if ( ans != NULL ) {
        ans->prev = p ;
        ans->data = d ;
        ans->next = n ;
    }
    return ans ;
}
void main() {
    struct BD_List* top ;
    struct BD_List* p ;

    // 順方向のポインタでリストを生成
    top = bd_cons( NULL , 1 ,
          bd_cons( NULL , 2 ,
          bd_cons( NULL , 3 , NULL ) ) ) ;
    // 逆方向のポインタを埋める
    top->next->prev = top ;
    top->next->next->prev = top->next ;

    // リストを辿る処理
    for( p = top ; p->next != NULL ; p = p->next )
        printf( "%d\n" , p->data ) ;
    for(         ; p->prev != NULL ; p = p->prev )
        printf( "%d\n" , p->data ) ;
}

• bidirectional-list.cxx

双方向リストの関数作成

以上の説明で、双方向の基礎的なプログラムの意味が分かった所で、練習問題。

先のプログラムでは、1,2,3 を要素とするリストを、ナマで記述していた。実際には、どんなデータがくるか分からないし、指定したポインタ p の後ろに、データを1件挿入する処理 bd_insert( p , 値 ) , また、p の後ろのデータを消す処理 bd_delete( p ) を書いてみよう。

Javaの場合

public class Main {
    // 指定したノードの後ろに1件追加
    static void bd_insert( BDListNode p , int d ) {
        p.next = new BDListNode( null , d , p.next ) ;
        p.next.next.prev = p.next ;
        p.next.prev = p ;
    }
    // 指定したノードの後ろを1件削除
    static void bd_delete( BDListNode p ) {
        p.next = p.next.next ;
        p.next.prev = p ;
    }
    public static void main(String[] args) throws Exception {
        // 双方向リストの追加,削除            
        BDListNode top2
            = new BDListNode( null , 1 ,
                 new BDListNode( null , 2 ,
                    new BDListNode( null , 4 , null ) ) ) ;
        top2.next.prev = top2 ;
        top2.next.next.prev = top2.next ;
        
        // 途中に挿入の実験
        bd_insert( top2.next , 3 ) ;
        for( BDListNode p = top2 ; p != null ; p = p.next )
            System.out.println( p.data ) ; // 1,2,3,4
        for( BDListNode p = top2.next.next.next ; p != null ; p = p.prev )
            System.out.println( p.data ) ; // 4,3,2,1
        
        // 途中を削除の実験
        bd_delete( top2.next ) ;
        for( BDListNode p = top2 ; p != null ; p = p.next )
            System.out.println( p.data ) ; // 1,2,4
        for( BDListNode p = top2.next.next ; p != null ; p = p.prev )
            System.out.println( p.data ) ; // 4,2,1
    }
}

C言語の場合

// 双方向リストの指定場所 p の後ろに、値 d を要素とするデータを挿入せよ。
void bd_insert( struct BD_List* p , int d ) {
   struct BD_List*n = bd_cons( p , d , p->next ) ;
   if ( n != NULL ) {
      p->next->prev = n ;
      p->next = n ;
   }
}

// 双方向リストの指定場所 p の後ろのデータを消す処理は？
void bd_delete( struct BD_List* p ) {
   struct BD_List* d = p->next ;
   d->next->prev = p ;
   p->next = d->next ;
   free( d ) ;
}

// この手のリスト処理のプログラムでは、命令の順序が重要となる。
// コツとしては、修正したい箇所の遠くの部分を操作する処理から
// 書いていくと間違いが少ない。

番兵と双方向循環リスト

前述の bd_insert() だが、データの先頭にデータを挿入したい場合は、どう呼び出せば良いだろうか？
bd_insert() で、末尾にデータを挿入する処理は、正しく動くだろうか？

同じく、bd_delete() だが、データの先頭のデータを消したい場合は、どう呼び出せば良いだろうか？
また、データを消す場合、最後の1件のデータが消えて、データが0件になる場合、bd_delete() は正しく動くだろうか？

こういった問題が発生した場合、データが先頭・末尾で思ったように動かない時、0件になる場合に動かない時、特別処理でプログラムを書くことは、プログラムを読みづらくしてしまう。そこで、一般的には 循環リストの時にも紹介したが、番兵(Sentinel) を置くことが多い。

しかし、先頭用の番兵、末尾用の番兵を2つ用意するぐらいなら、循環リストにした方が便利となる。このような双方向リストでの循環した構造は、双方向循環リスト(bi-directional ring list)と呼ばれる。