2. より柔軟なリスト

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

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

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

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

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

    /* 呼び出しがわで
    struct eLIST *start=NULL;
    を用意し、必ず以下の関数に対して hogeList( &start, ...) と
    して使う。
    */
    /* eLIST のオブジェクトを作り、それはdataを保持 */
    struct eLIST *newObj(void * data){
        struct eLIST *p;
        p = (struct eLIST *)malloc(sizeof(struct eLIST));
        p->next=NULL;
        p->data=data;
        return p;
    }
    /* リストの末尾に要素を追加し、要素は data を持つ */
    struct eLIST *appList( struct eLIST **pstart, void * data ){
        return insList(pstart, NULL, data);
    }
    /* 一般的な要素の追加、但し先頭への追加のみできず */
    struct eLIST *insList( struct eLIST **pstart,
                           struct eLIST *after, void *data ){
        struct eLIST *new, *p = after;
        if(*pstart==NULL){       /* リストが空なら */
            *pstart=newObj(data);
        }else{
            if(p==NULL){         /* after が NULL なら末尾を探す */
                 p=*pstart;
                 while(p->next != NULL) p=p->next;
            }
            new = newObj(data);
            new->next = p->next;
            p->next = new;
        }
        return new;
    }
    /* 要素を削除 */
    struct eLIST * delList( struct eLIST **pstart, struct eLIST * target){
        struct LIST *p=*pstart, *new;
        if(p==target){              /* 先頭の要素を削除するとき */
            *pstart = target->next;
        }else{
            while(p->next!=target){
               p=p->next;
            }
            p->next=target->next;
        }
        free(target);
        return p;
    }

この改良されたプログラムでは、リストの途中に新しいオブジェクトを 挿入する操作と、リストの最後に新しいオブジェクトを追加する操作は ほとんど同じものとして midList() に統一されている。また、オブジェクト を新しく作るための関数も newObj() として提供されているが、この newOjb() で作られるオブジェクトはリストに追加されていない孤立した オブジェクトになっている。