Thinkers'Studio
JavaとC言語の自習ツール
第4回)リスト構造からの削除操作 delete

 何回かに分けて取り扱うリスト構造の最終回です。 ( 第1回 概要 , 第2回 構造体定義, 第3回 リストへの挿入操作
 今回は、リスト構造からデータを削除する delete 操作です。最後に、リスト全体を free する関数も紹介します。

 ひとくちに削除と言っても、下記のような取り扱いが考えられます。
  リストの先頭データを削除/リスト末尾データを削除/特定のデータを探して削除
 いずれの場合も、リスト構造の削除処理では次の2つの操作が必要となります。
  • リスト構造からそのデータを外して、リストを整備する
  • データ領域を malloc で取っているので、それを free で解放する

 リスト構造のように領域をつないで使う場合、適切な順序や手順で解放しないと、free できないブロックが残るなどの問題が起こります。それらが積み重なるとメモリリーク(メモリが漏れ続けて足りなくなる)につながりますから、注意が必要です。

 ここでは「特定のデータを探し出し、それを削除する」関数 delete を作ります。 使用する構造体は下記です。
typedef struct entry {
    int n;
    struct entry *next; //次のデータを指すポインタ
} ent_t;
 リストは n の昇順に並んでいます。 リストの先頭を指す head ポインタは dummy を指し、その次から本当のエントリがつながる構造とします(前回の記事)。

データをリストから削除する操作(delete)

1. 削除するデータを見つける処理

 削除したいデータのひとつ前を探します。下記の例で 30 を削除するなら 20 を見つけます。
 ポインタ p をリストの先頭から進めながら、次のデータ( p->next )が削除したいデータなら、そこで探索を終わります。 データ探索
 コードでは、こうです(x が削除したいデータの値)。
 ent_t *p = head;
 while( p->next != NULL && p->next->n != x ) p = p->next;
 これで、p は削除するひとつ手前のエントリ(上の例の 20)を指しています。

2. 削除する

 リスト構造からエントリを外すには、前後のポインタの付け替えを行います。
 このとき注意が必要です。 考えなしにそのまま前後のポインタを付け替えると、いざ削除対象を free しようとしたときに、そのアドレスが分からなくなってしまうからです。 そこで、次のように "取り置き" を使います。
  //ここまでの処理でpは20を指している

  ent_t *temp;
  temp = p->next;       //tempに30の所在を取り置く
  p->next = temp->next; //20の次を40とする
ポインタ付け替え
 それまで 30 のデータが指していたデータ 40 を 20 が指すようにして、リストから 30 を外します。

3. 削除データのエントリを free する

 あとは、temp に取り置いていたエントリを free します。
    free( temp );
削除完了

delete 関数

   関数全体は次の通りです。head の宣言はこの関数の上にあります。
void delete( int x )
{
    ent_t *p = head; //リストの先頭を指すように
    ent_t *temp;

    //1. xのひとつ前のエントリを見つける
    while( p->next != NULL && p->next->n != x ) p = p->next;
    //最後まで見つからなかった
    if( p->next == NULL ) return;
    //2. xのデータをリストから外しfreeする
    temp = p->next;
    p->next = temp->next;
    free( temp );
}

リスト全体のfree

 リスト構造自体が要らなくなったときは、すべてのエントリを解放する必要があります。 下記にその関数を示します。
void freeList()
{
    ent_t *p, *temp;

    while( p != NULL ) {
        temp = p->next; //次のデータの参照を取っておく
        free( p );
        p = temp;       //tempを次の処理対象に
    }
}
 ここでの例題プログラムでは、head が dummy エントリを指す前提です。dummy の領域は、動的に確保したものではないので free しません。 そのため、head->nextから始めます。ここでも temp に p->next を取り置いて、p を free します。

 リスト構造の特集は、今回で終わりです。

  (今回のクイズはありません)

[ 関連記事 ] 第1回)リスト構造の概要, 第2回)リスト構造の構造体定義, 第3回)リストへの挿入操作
[ ご案内 ] 構造体やポインタの要点を学習できるコース:要点講座


  (前回のクイズはありませんでした)