連結リスト(リスト構造）

前々回、前回と構造体のなかに構造体型のポインタのメンバをもった構造体型配列での連結リスト（リスト構造）
を作りました。さて、今日はその連結リストについて説明します。

連結リストはひとつの構造体が次の構造体を指すポインタで繋がっています。ちょうど鎖のように。
データが繋がっているというか連なっているという点では配列もそうですね。

配列と連結リストが違うところは

連結リストはしっかりと次の構造体（データ）を指しているのに対して、

配列は次の要素（データ）との繋がりは無いです。ただ並んでいるだけです。



もっと簡単に考えると、たくさんの人間がいたとして、

連結リストはみんなが手をつないで並んでいますが、

配列はみんなが一列に整列して立ち尽くしていると考えてください。
もちろん人間一人がデータひとつです。



このふたつがどんな構造か感覚的にでも理解してもらえたでしょうか。
ではそれぞれがどんな利点があるのかを考えます。




�@データ検索



たとえば大量のデータが配列か連結リストのどちらかで構成されているとします。
ではあるクラス40人の生徒の名前が出席番号順に並んでいるとします。
配列の場合は添え字が3なら出席番号3番、
連結リストなら先頭から3番目の構造体が出席番号3番の名前が格納されているとします。



そこで出席番号7番の生徒の名前を検索する場合ですが、配列なら添え字7の要素を見ればOKですね。



しかし連結リストの場合はどうでしょう。先頭から7番目にあるということはわかっていますが
先頭から順にポインタをたどっていく以外方法はないのです。

どうやらデータの検索は配列のほうが速いですね。








�Aデータ追加、削除

先ほどの生徒名簿の例の続きですが、例えばそのクラスに転入生がやってきたとします。
ですから新しくその転入してきた生徒の名前データを追加しなければいけません。
生徒はこれで41人になりました。転入生の出席番号が12番だとします。


配列の場合、今まで12番だった生徒を13番に、13番だった生徒を14番に………40番だった生徒を41番にずらす
必要があります。そして転入生は12番の添え字の要素にデータを格納します。
並んでいた列に転入生が横から入ってきたから、その後ろの生徒たちは彼一人分空けるため後ろへさがったというわけです。


これが連結リストの場合はどうでしょう。
まず先頭から11番目の構造体のポインタを転入生に指します。そして転入生の構造体のポインタは
今まで12番だった生徒の構造体を指します。するとどうでしょう、転入生の構造体は先頭から12番目ということになります。
手をつないだ例でたとえると11番と12番の生徒たちの繋いでいた手を一度放し、転入生の片手は11番の生徒と、
もう片手は12番の生徒と繋げばOKなのです。


また、データを削除する（クラスから転校生が出た）場合でも配列はその転校生以降の番号の子を前にずらす必要がありますが、
連結リストは手を繋ぎかえるだけです。


というわけでデータの追加、削除の操作の容易さでは連結リストに部があるようです♪


配列、連結リストのメリット・デメリットをしっかりとおさえておきましょう。

というわけで長く（？）続いた構造体もこれで一段落です。
しかし最後に連結リストの練習問題をやろうと計画中です♪それではまた！