先週でのリストの追加のネタの前に、いつもであればリストの挿入削除を説明していたのに、 説明が抜けていたので、挿入処理と削除処理を説明する。

昇順リストにデータを挿入

昇順にデータを保存しているリストに対し、与えられた値を挿入。 授業では、consを用いた例と使わない例をしめした。 ここでは、consを使わない例を記録しておく。

void insert( struct List* p , int key ) {
struct List *q = p , *r ;
while( p != NULL && p->data < key ) {
q = p ;
p = p->next ;
}
r = (struct List*)malloc( sizeof( struct List) ) ;
if ( r != NULL ) {
r->data = x ;
r->next = q->next ;
q->next = r ;
}
}

説明の後、挿入場所が先頭だったら、末尾だったらの確認をしないと、 動かない場合があるから、チェックは大切と「次の番兵」の伏線を…

リスト中の削除

リストの途中のデータを削除する処理。 処理を短く書くために、削除すべき場所を探す処理は、別に行うものとする。 pは消したいデータの１つ前の要素を指している。

void remove( struct List* p ) {
struct List* del = p->next ;
p->next = p->next->next ;
free( del ) ;
}

この説明の後、学生さんより「消したいデータが末尾だったら？」と質問される。
# 伏線の効果あり…
ということで、番兵のテクニックの概要を紹介しておく。