Thinkers'Studio
JavaとC言語の自習ツール
第1回)リスト構造の概要
 何回かに分けて、リスト構造の話題を取り扱います。
 第1回の今回は、リスト構造の用途やポインタのつなぎ替えなどについて触れ、イメージをつかみます。

リスト構造はどんなときに使う?

 多数のデータを扱うときはよく配列を使いますが、末尾以外でのデータの追加や削除が多いときは、リスト構造が便利です。

リスト構造とはどんなデータ構造?

 個々のデータを入れるのは構造体です。メンバには自分と同じ構造体型へのポインタを定義します。このポインタで、次のデータを指し示すのです。次のデータのポインタは、またその次のデータを指すようにします。 このようにして、チェーンのようにデータをつないでリストの構造を作ります。 下図はそのイメージ(前から後ろへ単方向でつないだ例)です。
リスト構造のイメージ
 malloc を使って動的に領域を確保することで、必要なデータ分の領域だけを用意することができます。もちろん、不要になったら free関数を使って解放しておくべきです。
 データの削除や追加は、ポインタのつなぎ替えによって実現できます。

途中に挿入する場合のイメージ

リスト構造にデータを挿入
  挿入場所の前のデータのポインタが新しいデータを指すようにして、リストデータのつながりに仲間入りさせます。

途中のデータを削除する場合のイメージ

リスト構造からデータを削除
  前のデータが次のデータを指すようにして、要らなくなったデータをリストから外します。

配列と比べると?

  ポインタの付け替えにより、挿入/削除/並べ替えが効率よく処理できる
  慣れないと、プログラミングが煩雑になりがちだ
  実行時に必要な領域を割り当てるので、データ量が決まらない場合にも対応できる
  その分、freeなどメモリ管理に注意が要る
  特定のデータを選ぶ操作は、ポインタを順にたどってデータを探す必要がある
    (配列は、添字が分かればすぐさま参照できる)

 ○ のメリットの恩恵が △ を上回るなら、リスト構造を使おう!ということになります。

リスト構造はどんな風につくるの?

 取り扱うデータの内容とどんな操作をするかによって、まず構造体の内容を検討します。どんな処理が要るかも大体のところを考えます。 この続きは次回の第2回)リスト構造の構造体定義で・・・。 リスト構造に使う自己参照型構造体をどんなふうに検討していくかについて扱う予定です。

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

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

前回のクイズの答え: (前回の問題を見る
     while( (s[j++] = s[i++]) != '\0' ) ;
 このコードは、s[j] に s[i] を代入した結果が '\0' でない間は、繰り返しが実行され、j++, i++ で添字が進められます。繰り返しの中身は空文です。 '\0' がコピーされると、!= '\0' の条件を満たさないのでループを抜けます。
 文字列終端の '\0' を含めて、文字がコピーされることになります。