C言語教室 第21回 - 循環リスト
前回までに単方向リストと双方向リストを説明しましたが、今回は、これらをもう一捻りした循環リストを取り上げます。
C言語教室 第19回 - 単方向リスト
C言語教室 第20回 - 双方向リスト
循環リストはリストの両端にあるノードを繋いだもので、単方向リストでも双方向リストでも適用できます。考えてみればリストの順序が関係なければ、どこが先頭であっても最後であっても構わなく、どこかのノードを指すポインタさえあれば、ぐるっと回って同じアドレスのノードに出会うまで辿ればリストを一周することができます。
このようにすれば双方リストで末尾へのポインタをわざわざ覚えておかなくても、先頭へのポインタからひとつ戻るだけで末尾のノードを辿ることができるようになります。
もうひとつの工夫として、番兵ノードと呼ばれるノードを置くという工夫があります。今までの例では、最後のノードの次のノード、双方リストでは最初のノードの前のノードを示すポインタには NULL を使っていましたが、これに代わって値が入っていない（無効な値が入っている）ノードを指すようにします。リストを作成する時に、まず番兵ノードを作ることにより、リスト処理で例外的な操作が必要であった両端の挿入、削除の処理を他のノードと同じにすることが出来るのです。
この手法は、大昔のLISPの時代に実装されたのが始まりのようで、今では多くのリストの実装に使われています。番兵ノードをどのように実装するかはバリエーションがあるようですが、C++ の STLコンテナのひとつである list も、この手法で実装されています。
ということで、STLはテンプレートなのでソースコードを見ることが出来ます。ちょっと見てみましょうか。
stl_list.h
https://cs.brown.edu/people/jwicks/libstdc++/html_user/stl__list_8h-source.html
このコードは、もしかしたら最新ではないかもしれませんが、C++をビルドできる環境を作れば、必ずソースを見ることは出来るはずです。もっともC++を読めないとどうにもなりませんし、テンプレートの実装はお世辞にも読みやすいとは言えないものなので、判るところだけつまみ食いをすれば充分に勉強になります。
STLは非常に多く使われている標準的なコードなので、下手に自分で書くよりもよほど頼りになります。類似の機能が必要になったときは、こういった広く使われているコードを読みながら、必要な機能を例えばC言語に翻訳して実装することが多いです。
さすがにソースを読んでねでは理解するのは大変なので、C++が前提ではありますが、以下の説明がわかりやすそうです。
双方向リストクラス std::list とは
C言語ではなくてC++の説明になってしまいますが、リスト操作のやり方と必要な関数は、これを参考にすれば良さそうです。
std::list
C++ List (英語なんで翻訳して読んで下さい)
さあ、単方向リストと双方向リストで学んだことを使って課題と演習を解いてみましょうか。
課題
番兵ノードを用い循環リストで実装した双方向リストを使って、以下のリスト処理を行う関数を書きなさい。
1. リストの先頭に要素を追加する。
2. リストの最後に要素を追加する。
3. リストの先頭の要素を削除する。
4. リストの最後の要素を削除する。
実装の方法は、いろいろあると思いますが、リストに格納する型は整数とし、以下のコードを元に書いてください。リスト構造体が指すノードが番兵ノードとします。
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int val;
struct node* next;
struct node* prev;
} Node;
typedef struct list {
struct node* top;
} List;
Node* create_node(int val) {
Node *node = (Node*)malloc(sizeof(Node));
node->val = val;
node->next = NULL;
node->prev = NULL;
return node;
}
void create_list(List* list) {
Node *dummy = (Node*)malloc(sizeof(Node));
dummy->next = dummy;
dummy->prev = dummy;
list->top = dummy;
}
void destroy_list(List* list) {
Node *current = list->top->next;
Node *next;
while (current != list->top) {
next = current->next;
free(current);
current = next;
}
free(list->top);
list->top = NULL;
}
void print_list(List* list) {
Node *current = list->top->next;
while (current != list->top) {
printf("%d ", current->val);
current = current->next;
}
printf("\n");
}演習
1. リストに引き数で渡した値を持つノードのアドレスを返す関数を書きなさい。
2. リストに含まれるノードへのポインタと値を引き数とし、渡したノードの位置に渡した値のノードを挿入する関数を書きなさい。その結果、渡したノードは挿入したノードの次のノードとなります。
3. リストに含まれるノードへのポインタを渡して、そのノードをリストから削除する関数を書きなさい。なお番兵ノードを渡した場合は削除してはいけません。
次回は、寄り道をして今までの知識を使う例を取り上げてみるつもりです。