線形リスト

線形リストとは

配列によるデータ格納の問題

順序性を持ったデータを保存するのであれば,「配列」を用いるのが一番手っ取り早いと思います.しかしこれには欠点があります.

メモリ確保の問題

配列は事前にサイズを決めておかないといけませんから、メモリの利用効率が良いとは言えません。

データの柔軟性の問題

下記のように文字列型の二次元配列にデータが入っています.

このデータ表現(配列)が意味することは, 最初のデータはtoritaniで,その次にkanemoto,arai、最後にjoeが格納されている... ということを意味します.当たり前のことのようですが,この意味をよく理解して次の問いに答えなさい.

char str[3][20]= {"toritani","kanemoto","arai"};

(1)このデータの格納状態を図示せよ.

(2)toritaniを後ろに回してaraiを先頭にしたい.これを実現する手順を箇条書きで説明せよ.

(3)プログラムで書くとどうなるか?

上記の例のように,複数のデータを管理しているときに,データを削除したり追加したりする処理は必ずでてきます.上述ではデータ数がすくないため処理は単 純ですが,データ数が多くなるとそれだけ処理に時間がかかるということが,想像できると思います(100万件のデータを創造してみてください).

これが配列によるデータ格納の問題(欠点)です.

以上をまとめると,

配列の利点: 配列というのは,0,1,2,3・・・・というように,自身を番号で表現するデータ型です.この特徴を利用 すると,順序性のあるデータを配列の番号順に格納していくだけで,後でたどっていくことができます

配列の欠点: いったんデータを格納した配列に対して,データを削除したり挿入することは不得意です

線形リストとは

リストとは,順序性のあるデータを格納するデータ構造です。線形リストとは,順序性のあるデータを格納する際に,「その次の データの位置」もあわせて格納するデータ構造です.

図1 リストの構造

次の位置には、次のデータが存在するアドレス(場所)を明記します。

図2 線形リストのイメージ

身近な例でいうと学校等での電話連絡網などがあります。電話連絡網では、次に電話をかける相手の情報のみを管理することで、全員に連絡が行き渡ります。

線形リストの実装方法

線形リストは、構造体を用いて実装します。代表的な方法として

    1. 配列の番号をアドレスとする方法
  1. ポインターを利用する方法 (推奨)

の 2通りがあります.