リストを用いたStack,Queueの説明の次に、 リスト途中へのデータ挿入と削除を説明。

リスト途中への挿入削除

リストの途中にデータを挿入するのであれば、以下の処理となる。 配列であれは、途中へのデータ挿入は挿入場所を作るための、 後ろシフトで、O(N)の処理がかかるけど、リストであれば、O(1)となる。

// mallocの使い方の意味も込めて、
// cons()を使わずに書いてみる。
void insert( struct List* prev , int value ) {
// prevは、挿入すべき場所の1つ前とする。
struct List* n = (struct List*)malloc(sizeof(struct List)) ;
if ( n != NULL ) {
n->data = value ;
n->next = prev->next ;
prev->next = n ;
}
}

今日は、テスト直前ということもあり、説明後は早々に自習の時間とした。 んで、説明後の質問で「先頭にデータを入れるときは？」 このプログラムでは、１つ手前のデータのポインタがあることを前提にしているけど、 先頭の場合はこうはいかない。対応の方法としては、List**型を使うか、 「リストの先頭には必ず1個のデータを入れないダミーのList型を置く」 方法もある。こういった、リストが0件とか先頭とか末尾に伴うデータで特別処理を 書くのはプログラムを複雑にするので、先頭・末尾に置くダミー(番兵とと呼ぶ)を使えば特別処理も不要でプログラムをシンプルにできる。んで、番兵は、リスト処理ではよく見られるテクニック….という追加説明を行う。

同様に、途中データの削除も書いてみる。

void remove( struct List*prev ) {
// prevは、削除したい場所の1つ手前とする。
struct List* del = prev->next ;
prev->next = prev->next->next ;
free( del ) ;
}

リストでの集合演算

ここまでに示したように、リストを使えば要素の追加削除が簡単にできるため、 集合のように扱うことができる。

// p = { 1 , 2 , 3 } のつもり...
struct List* p = cons( 1 , cons( 2 , cons( 3 , NULL ) ) ) ;

実際に、集合積のプログラムを以下に示す。 以下のプログラムでは、p1の各要素が、p2 に含まれていれば、 ans に要素を追加していく。

// 分かりやすく書くための補助関数
int find( struct List* p , int value ) {
for( ; p != NULL ; p = p->next ) {
if ( p->data == value )
return 1 ;
}
return 0 ;
}
// 集合積を求める
struct List* prod( struct List* p1 , struct List* p2 ) {
struct List* ans = NULL ;
for( ; p1 != NULL ; p1 = p1->next ) {
if ( find( p2 , p1->data ) )
ans = cons( p1->data , ans ) ;
}
return ans ;
}

これまた、説明後にて、『 "if ( find( … ) != 0 ) {…" と書くべきでは？』 との質問。ということで、C言語の条件式は、0=false,0以外=true なので、 "if ( find(…) ) { … " で十分と解説する。