Thinkers'Studio
JavaとC言語の自習ツール
第3回)リスト構造への挿入操作 insert
 何回かに分けて取り扱うリスト構造の第3回です。 ( 第1回 リスト構造の概要 , 第2回 リスト構造の構造体定義
 今回は、リスト構造にデータをつなぐ insert の操作を紹介します。次の前提とします。
  • データは int型 の n のみとする。
  • リストは、n の昇順に並ぶようにする。
  • データのアクセスは、1方向のみとする。

構造体定義

 自己参照型構造体は次のようになります。
typedef struct entry {
    int n;
    struct entry *next; //次のデータを指すポインタ
} ent_t;
 自己参照するポインタは、構造体タグ名を使って定義します。「struct entry」のところを「ent_t」とすることはできません。

head とダミーデータ

 リストの先頭を覚えておく head ポインタを用意します。 先頭(head)と、自分の次(next)の2種類のポインタを使って、データのつながりをたどります。 リストが空かどうかなどにより処理が煩雑にならないように、ここでは head はダミーレコードを指し、ダミーレコードの次に本当のエントリがつながる構造とします。
ent_t dummy;            //常に先頭扱いのダミーレコード
ent_t *head = &dummy;

データをリストにつなぐ操作(insert)

 もし、データを常にリストの先頭(または末尾)に追加するなら、挿入場所が分かっているので処理は単純です。
 しかしここでは、n の昇順に並ぶリストになるようにしなければなりません。 そのため、入れたいデータの値とリスト中の n を比べて、挿入場所を探すことになります。 そして、ポインタのつなぎ替えにより、その場所への追加を表現します。
 関数 insert の処理手順は、次の3ステップとなります。
  1. 新しいデータを入れるべき挿入場所を見つける
  2. 挿入用のエントリをつくる
  3. ポインタをつなぎ替えて、挿入場所にデータを挿入する

1. 挿入場所を見つける処理

 たとえば、下図のようにデータが並んでいるとして、新データ 25 を入れる場所を探します。
データ挿入場所
 上の例で 20 の次に新データ 25 を入れるつなぎ替えは、次のようなイメージです。
ポインタ付け替え
 挿入場所は、「次のデータを見に行くと、新データの値を超えた!」ところです。
 コードでは、リストの先頭から調べていくので、まずポインタ p がリストの先頭を指すようにします。 リストの終わりまでの間で挿入場所まで p を進める処理はこうです(新データを x とします)。
 ent_t *p = head;
 while( p->next != NULL && p->next->n < x ) p = p->next;
 これで、p が挿入位置の手前のエントリ(上の例の 20)を指しています。
 dummy の次やリストの最後に追加する場合でも、この条件で上手く判定できます。

2.挿入用のエントリをつくる

 malloc を使って、ent_t ひとつ分の領域を用意し、データを入れます。
  ent_t *q;
  q = (ent_t*)malloc( sizeof(ent_t) );
  q-> n = x; //新データを入れる

3. 挿入場所にデータを挿入する

 上の図の青線のように、ポインタのつなぎ替えをします。 p の次に新データ q をつなぎ、q は後ろのデータを指すようにします。
    q->next = p->next;
    p->next = q;
 この2つはこの順でなければなりません。
 もし逆にすると、それまで p->next が指していた場所が上書きされて分からなくなってしまいます。

insert 関数

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

    //1. xを入れるべき挿入場所を見つける
    while( p->next != NULL && p->next->n < x ) p = p->next;

    //2. 挿入用のエントリをつくる
    q = (ent_t*)malloc( sizeof(ent_t) );
    q->n = x;

    //3. 挿入場所にデータを挿入する
    q->next = p->next;
    p->next = q;
}

先頭にダミーありとダミーなしの比較

 ダミーが無かったら ・・・ 先頭にデータを挿入するときは、head がそれを指すようにしなければなりません。リストが空だったり挿入場所が先頭かどうかを判断して、処理を分けて書くことになります。
 ダミーがあると ・・・ リストには常に1つ以上のデータがあるので、先頭かどうかの特別扱いが要りません。リストの途中に入れることになります。上の insert関数を見ても分かるように、いつも同じ処理で任意の場所に挿入ができます。

 次回は、リスト構造の操作例 delete を紹介します。

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

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


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