next up previous contents
Next: 3. より高度なリスト Up: 21. データ構造 Previous: 3. リストへの挿入

2. より柔軟なリスト

前の節でリンクドリストを学んだが、ここではもう少し使えるものを提示しよう。 前の節ではデータはリスト構造体自体の中に埋めこまれていたが、より柔軟に リスト構造のプログラムが再利用出来るようにするには、どんなデータでも収容 可能なようになっていた方が良いであろう。つまり、データ本体をリスト構造体 に入れるのではなく、データへのポインタになっている方が柔軟である訳である。

そのようなリンクドリスト構造体の定義は次のように考えられる。


    struct eLIST {
        struct eLIST *next;
        void *body;
    };

このような柔軟性の代償としては、データ本体へのポインタの型が分からなく なる点であり、再利用する際にはキャストが必要となる点であるが、これは 致し方のないトレードオフであろう。

追加・挿入・削除をサポートしたプログラムは次のようになる。


    struct eLIST *start=NULL;
    
    struct eLIST *newObj(void * data){
        struct eLIST *p;
        p = (struct eLIST *)malloc(sizeof(struct eLIST));
        p->next=NULL;
        p->data=data;
        return p;
    }
    struct eLIST *getList( void ){
        return start;
    }
    struct eLIST *appList( void * data ){
        return insList(NULL, data);
    }
    struct eLIST *insList( struct eLIST *after, void *data ){
        struct eLIST *new, *p = after;
        if(start==NULL){
            start=newObj(data);
        }else{
            if(p==NULL){
                 p=start;
                 while(p->next != NULL) p=p->next;
            }
            new = newObj(data);
            new->next = p->next;
            p->next = new;
        }
        return new;
    }
    struct eLIST * delList( struct eLIST * target){
        struct LIST *p=start;
        struct LIST *new;
        if(p==target){
            p=target->next;
        }else{
            while(p->next!=target){
               p=p->next;
            }
            p->next=p->next->next;
        }
        free(target);
        return p;
    }

この改良されたプログラムでは、リストの途中に新しいオブジェクトを 挿入する操作と、リストの最後に新しいオブジェクトを追加する操作は ほとんど同じものとして midList() に統一されている。また、オブジェクト を新しく作るための関数も newObj() として提供されているが、この newOjb() で作られるオブジェクトはリストに追加されていない孤立した オブジェクトになっている。 更に、このモジュールを使いやすくするために、リストの先頭のアドレス を返すためだけの getList()関数が追加されている。これによって、 start変数を参照するのではなく、getList()関数を呼び出せば常にリスト の先頭が得られるようになっている。当然、利用する際にはこのほかに リストを次々と参照するようなプログラムが必要であろうし、高度な モジュールでは並び替えなども考えられるが、読者の宿題として置こう。



Noriyo Kanayama 平成14年11月26日