next up previous contents
Next: 3. リストへの挿入 Up: 1. リストの初歩 Previous: 1. リストの追加

2. リストの削除

リストから特定のオブジェクトを削除する場合には単に free() してはならない。 きちんとオブジェクトの連鎖から取り除いた後に free() しなければならない からである(図 [*])。

\begin{figure}
\begin{center}\epsfile {file=list3}\end{center}\end{figure}


    struct LIST * delList( struct LIST * start, struct LIST * target){
        struct LIST *p=start;
        struct LIST *new;
        while(p->next!=target){
           p=p->next;
        }
        p->next=p->next->next;
        free(target);
        return p;
}

上のプログラムでは、引数にリストの先頭と削除対象のオブジェクトへの ポインタ(target)を与え、target を指している一つ前のオブジェクトの next を一つ飛ばしのオブジェクトへと入れ換えてから、target の オブジェクトをメモリから削除している。

実は、このプログラムには一つ問題がある。それは、もし target が先頭 のオブジェクトだったらどうするのかという問題である。何故これが問題 になるかと言うと、引数である先頭のstartポインタを変更しても呼び出し 元の start ポインタのアドレスは変化しないからである。これに対する 対策は2通りあり、一つは start ポインタの指す先頭オブジェクトはダミー で単なる先頭を示す中身が空のものであると考えることであり、つまりは 本当の先頭は2つめのオブジェクトからとしてしまうやり方、2つめは start のアドレスを保持するポインタを渡すのではなく、そのアドレス 自体を渡すようにするやり方が考えられる(実は、start 変数はグローバル にしてしまうという考え方もある)。 上のプログラムは前者の考え方に従っており、そう考えなければバグが あることになる。一方、後者の考え方に従えば次のようなプログラムに なる。


    struct LIST * delList( struct LIST ** pstart, struct LIST * target){
        struct LIST *p=*pstart;
        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;
}

前のプログラムとの違いは、先頭か否かによってプログラムが異なる点である。

実際にどちらを使うかは設計によって違うが、現実にはグローバル変数( 正確にはモジュール内で定義された外部変数)として扱うことが多いようである。



Noriyo Kanayama 平成14年11月26日