線形リスト
線形リストとは
配列によるデータ格納の問題
順序性を持ったデータを保存するのであれば,「配列」を用いるのが一番手っ取り早いと思います.しかしこれには欠点があります.
メモリ確保の問題
配列は事前にサイズを決めておかないといけませんから、メモリの利用効率が良いとは言えません。
データの柔軟性の問題
下記のように文字列型の二次元配列にデータが入っています.
このデータ表現(配列)が意味することは, 最初のデータはtoritaniで,その次にkanemoto,arai、最後にjoeが格納されている... ということを意味します.当たり前のことのようですが,この意味をよく理解して次の問いに答えなさい.
char str[3][20]= {"toritani","kanemoto","arai"};
(1)このデータの格納状態を図示せよ.
(2)toritaniを後ろに回してaraiを先頭にしたい.これを実現する手順を箇条書きで説明せよ.
(3)プログラムで書くとどうなるか?
上記の例のように,複数のデータを管理しているときに,データを削除したり追加したりする処理は必ずでてきます.上述ではデータ数がすくないため処理は単 純ですが,データ数が多くなるとそれだけ処理に時間がかかるということが,想像できると思います(100万件のデータを創造してみてください).
これが配列によるデータ格納の問題(欠点)です.
以上をまとめると,
配列の利点: 配列というのは,0,1,2,3・・・・というように,自身を番号で表現するデータ型です.この特徴を利用 すると,順序性のあるデータを配列の番号順に格納していくだけで,後でたどっていくことができます
配列の欠点: いったんデータを格納した配列に対して,データを削除したり挿入することは不得意です
線形リストとは
リストとは,順序性のあるデータを格納するデータ構造です。線形リストとは,順序性のあるデータを格納する際に,「その次の データの位置」もあわせて格納するデータ構造です.
図1 リストの構造
次の位置には、次のデータが存在するアドレス(場所)を明記します。
図2 線形リストのイメージ
身近な例でいうと学校等での電話連絡網などがあります。電話連絡網では、次に電話をかける相手の情報のみを管理することで、全員に連絡が行き渡ります。