リストのデータ追加処理とデータの型

# 先週の講義のメモが残してないので、１週遅れで記載。

前回の説明では、リストを処理で手作業で作っていたが、 データの入力に合わせて追加して区処理を説明する。

先頭挿入型の追加処理

配列でデータを扱えば、C言語では固定サイズになるため、リスト構造を使えば不定長の データの取り扱いも楽。

struct List {
int data ;
struct List* next ;
} ;
struct List* cons( int x , struct List* n ) {
struct List* ans ;
if ( (ans = (struct List*)malloc( sizeof(struct List ))) != NULL ) {
ans->data = x ;
ans->next = n ;
}
return ans ;
}
void main() {
struct List* top = NULL ;
int  x ;
while( scanf( "%d" , &x ) == 1 ) {
top = cons( x , top ) ;
}
}

このプログラムでは、リストの先頭に次々とデータを挿入していく。 このためデータは、挿入順と逆に並ぶことになる。

末尾追加型の追加処理

前の例では、管理するためのポインタがtopだけで良いため、シンプルではあるが、 データが逆順になってしまう。データの挿入順に並びたいのであれば、以下のような プログラムとなる。

void main() {
struct List* top = NULL ;
struct List** tail = &top ;
int  x ;
while( scanf( "%d" , &x ) == 1 ) {
*tail = cons( x , NULL ) ;
tail = &( (*tail)->next ) ;
}
}

しかしこのプログラムでは、tail の宣言が『Listへのポインタのポインタ』といった宣言で、 必ずしも読みやすいものではない。しかし、式の部分的な型が何なのかを明確に 理解できれば、イメージ図があれば、それなりに理解もできるようになるはず。

// ややこしい部分の型を考える。
&( (*tail)->next ) の型は？
tail               : List**
*tail              : List*  (List**の先を参照)
(*tail)->next      : List*  (List*の先のnext部を参照)
&( (*tail)->next ) : List** (next部のアドレスを取り出す)