リスト構造の利点は、データを扱う件数が可変にできる所。 通常なら配列で書いていたプログラムも、リストを使うと便利。 以下のようにデータの途中にデータを挿入する場合でも、 記入場所を確保するためのデータの移動 の処理が不要で、 単純なリストのつなぎかえの の処理で済む。

// あえてcons()を使わずに書いておく
void insert_next( int x , struct List* p ) {
struct List* ans ;
ans = (struct List*)malloc( sizeof( struct List ) ) ;
if ( ans != NULL ) {
ans->data = x ;
ans->next = p->next ;
p->next = ans ;
}
}

Stack(スタック)

データの後入れ先出し(Last In First Out)を行う Stack は基本的なデータの管理法。 配列で実装すれば、以下のような処理となる。

int stack[ SIZE ] ;
int sp = 0 ;
void push( int x ) {
stack[ sp++ ] = x ;
}
int pop() {
return stack[ --sp ] ;
}
void main() {
push( 1 ) ; push( 2 ) ; push( 3 ) ;
printf( "%d" , pop() ) ;  // 3
printf( "%d" , pop() ) ;  // 2
printf( "%d" , pop() ) ;  // 1
}

しかし配列であれば、SIZEを超えるデータは保管できない。そこで、push/pop をリスト構造で 記載してみる。

struct List* stack = NULL ;
void push( int x ) {
stack = cons( x , stack ) ;
}
int pop() {
int ans = stack->data ;
struct List* del = stack ;
stack = stack->next ;
free( del ) ;
return ans ;
}

Queue(待ち行列)

先入れ先出し(First In First Out)は、一般的に待ち行列と呼ばれ、 プログラムは、先頭データと末尾データの2つの情報で管理される。

int queue[ SIZE ] ;
int wp = 0 , int rp = 0 ;
void put( int x ) {
queue[ wp++ ] = x ;         // リングバッファ法
if ( wp >= SIZE ) wp = 0 ;  // 末尾なら先頭に戻る
}
int get() {
int ans = queue[ rp++ ] ;
if ( rp >= SIZE ) rp = 0 ;  // 末尾なら先頭に戻る
return ans ;
}
void main() {
put( 1 ) ; put( 2 ) ; put( 3 ) ;
printf( "%d" , get() ) ;  // 1
printf( "%d" , get() ) ;  // 2
printf( "%d" , get() ) ;  // 3
}

ただし、上記プログラムは登録件数が0になったことのチェックが無い手抜き記載なので、 理解できている人はさらに対策を記載する必要があることを考えること。

この待ち行列をリストを使ってプログラムで書けば、以下のようになる。 ただし、このリストのつなぎかえでは、データ件数0の状態が問題になるため、 最初にdummyデータが1件入れてあるものとする。

struct List* top = cons( 999 , NULL ) ; // dummy
struct List** tail = &( top->next ) ;
void put( int x ) {
*tail = cons( x , NULL ) ;
tail = &( (*tail)->next ) ;
}
int get() {
int ans = top->data ;
struct List* del = top ;
top = top->next ;
free( del ) ;
return ans ;
}