キャッシング情報

リスト構造

データ構造の基本中の基本。

大変個人的な意見ですが、ポインタを幅広く活用する為にはデータ構造の分野を学ぶ事をオススメします。
先ず言語ありき（そういう考えは否定しないけど）で始まるとおざなりになりがち。
せっかくポインタがちょっと分かったので使ってみたい！という人は、真っ先にデータ構造の本を手にとってみるのが良いでしょう。
ここではCを前提に話を進めていきますが、他言語でも考え方は応用できます。

考え方

リスト構造に関することは以下のリンク参照。
リスト構造(google)
いきなりgoogleに丸投げでやる気が有るのかと思われそうですが、キモになっているのは、
「データを鎖のように繋いでいく構造」
というのが分かるはずです。図を書いてみます。

図.1


データを矢印で繋いでいますね。このように一直線に並べることでデータを取り扱いやすくします。
このコンテンツで紹介するのは「単方向リスト」という種類のリスト構造です。これは、参照している方向を一方通行にしている為です。

リストにする利点は大体次が挙げられます。

・データの管理がしやすい。
・そのものを単体として扱える。
・他のデータ構造に応用が利く（木とかハッシュチェインとか）


他にも色々利点がありますがここでは割愛します。
逆に欠点としては、

・ポインタをいじるので不正なメモリアクセスに気を遣わなければならない。
・配列よりもちょっと遅い（殆ど誤差の範囲だけど）
・うまくまとめないと煩雑になりがち。

但ししっかり作れば強力なデータ構造です。
煩雑になるような時は入力と出力、およびデータを明確に分けて管理するのが定石です。

実装

実装なんて大げさな事言っていますが、C/C++で作る分には苦労しません。
冒頭で述べたように、Cにおけるポインタはリスト構造で大いに役に立ちます。
で、とりあえず構造体でリストを作ってみる事にします(構造体を理解していないのであれば教書を紐解いて学んでみてください) 

typedef struct tagLISTCELL {
	/* 次のリスト */
	struct tagLISTCELL *next;
	
	/* データ */
	int data;
} LISTCELL;
これで完成です。シンプルです。

上記の構造体のメンバで、 

	struct tagLISTCELL *next;
という部分がありますが、ここが図.1の矢印にあたる部分です。
つまり、自分自身と同じデータ構造への次のポインタ（アドレス）をメンバに追加する事で、同じデータ構造を鎖状に繋ぐ事が出来るわけです。
次に、構造体のメンバに 

	int data;
と、ありますが「ここにデータの実体を入れます」。
今回はint型のデータを一つ入れてみました。

例

作り方も分かった所で例を挙げます。
Sample1

ちょっとコード量が多い＆適当ですが、分けて考えればなんてことはないです。
上記のソースだと、

・初期化用の関数
・データを追加する関数
・データをリストの先頭から表示する関数
・データをリストの先頭から削除する関数
・終了する関数

に分かれています。
ソースを見ていくと分かりますが、mallocで「動的にリストのメモリを確保」しています。
言い換えればメモリが許す限りデータを追加する事が出来ます(とは言っても限界はあるけどね)
当然「freeでリストのメモリを開放」しなければなりません。
ここら辺のメモリ管理はプログラマのモラルにかかっています。


他にも双方向リストとか、利点とか欠点とかあるけど、大体これでイイや。
Back
2005/03/03 更新 Gyabo