単方向線形リスト 🔗
単方向線形リストのイメージ図は次のようになります。
この図で、２つの □ が組み合わさったものが１つの要素を表しています。「35」や「24」といったものが、その要素が持つ値（データ）だと思ってください。もう１つの空の □ がポインタ変数になっており、青い線によって、次の要素を指し示しています。
struct LinkedList_tag {
int value; // データ
struct LinkedList_tag* next; // 次の要素へのポインタ
};ここでは、扱いたいデータが int型であることを想定していますが、もちろんどんな型のデータを持たせても構いません。
// データが文字列
struct LinkedList2_tag {
const char* name;
struct LinkedList_tag* next;
};
// データが複数
struct LinkedList2_tag {
const char* name;
int age;
struct LinkedList_tag* next;
};連結リストを実装するカギとなるのは、next というメンバです。これは、次の要素を指し示すポインタです。要素を指すので、この構造体と同じ型のポインタになります。
今後、このメンバnext のことを「nextポインタ」と呼ぶことにします。
構造体メンバが、自分の属する構造体と同じ型の構造体変数を参照する形は、自己参照構造体と呼ばれます（Ｃ言語編第３７章）。
実際にプログラムを作って、動作を確かめてみます。長いですが、いろいろと実験できるプログラムを作りました。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// コマンド
enum Cmd_tag {
CMD_ADD,
CMD_DELETE,
CMD_SEARCH,
CMD_CLEAR,
CMD_PRINT,
CMD_EXIT,
CMD_NUM
};
// コマンド文字列の種類
enum CmdStr_tag {
CMD_STR_SHORT,
CMD_STR_LONG,
CMD_STR_NUM
};
// コマンドの戻り値
enum CmdRetValue_tag {
CMD_RET_VALUE_CONTINUE,
CMD_RET_VALUE_EXIT,
};
// コマンド文字列
static const char* const CMD_STR[CMD_NUM][CMD_STR_NUM] = {
{ "a", "add" },
{ "d", "delete" },
{ "s", "search" },
{ "c", "clear" },
{ "p", "print" },
{ "e", "exit" }
};
static void init_head(void);
static void print_explain(void);
static void print_blank_lines(void);
static enum CmdRetValue_tag get_cmd(void);
static enum CmdRetValue_tag cmd_add(void);
static enum CmdRetValue_tag cmd_delete(void);
static enum CmdRetValue_tag cmd_search(void);
static enum CmdRetValue_tag cmd_clear(void);
static enum CmdRetValue_tag cmd_print(void);
static enum CmdRetValue_tag cmd_exit(void);
static void add_elem(int value);
static int delete_elem(int value);
static void clear_list(void);
static void print_list(void);
static struct LinkedList_tag* search_tail(void);
static struct LinkedList_tag* search_elem(int value);
static void get_line(char* buf, size_t size);
// コマンド実行関数
typedef enum CmdRetValue_tag (*cmd_func)(void);
static const cmd_func CMD_FUNC[CMD_NUM] = {
cmd_add,
cmd_delete,
cmd_search,
cmd_clear,
cmd_print,
cmd_exit
};
// 連結リスト型
struct LinkedList_tag {
int value;
struct LinkedList_tag* next;
};
static struct LinkedList_tag gHead; // 先頭の要素
int main(void)
{
init_head();
while( 1 ){
print_explain();
if( get_cmd() == CMD_RET_VALUE_EXIT ){
break;
}
print_blank_lines();
}
return 0;
}
/*
先頭要素を初期化
*/
void init_head(void)
{
gHead.value = 0;
gHead.next = NULL;
}
/*
説明文を出力
*/
void print_explain(void)
{
puts( "コマンドを入力してください。" );
printf( " 連結リストに要素を追加する: %s (%s)\n", CMD_STR[CMD_ADD][CMD_STR_SHORT], CMD_STR[CMD_ADD][CMD_STR_LONG] );
printf( " 連結リストから要素を削除する: %s (%s)\n", CMD_STR[CMD_DELETE][CMD_STR_SHORT], CMD_STR[CMD_DELETE][CMD_STR_LONG] );
printf( " 連結リストから要素を探す: %s (%s)\n", CMD_STR[CMD_SEARCH][CMD_STR_SHORT], CMD_STR[CMD_SEARCH][CMD_STR_LONG] );
printf( " 連結リストを空にする: %s (%s)\n", CMD_STR[CMD_CLEAR][CMD_STR_SHORT], CMD_STR[CMD_CLEAR][CMD_STR_LONG] );
printf( " 連結リストの中身を出力する: %s (%s)\n", CMD_STR[CMD_PRINT][CMD_STR_SHORT], CMD_STR[CMD_PRINT][CMD_STR_LONG] );
printf( " 終了する: %s(%s)\n", CMD_STR[CMD_EXIT][CMD_STR_SHORT], CMD_STR[CMD_EXIT][CMD_STR_LONG] );
puts( "" );
}
/*
空白行を出力
*/
void print_blank_lines(void)
{
puts( "" );
puts( "" );
}
/*
コマンドを受け付ける
*/
enum CmdRetValue_tag get_cmd(void)
{
char buf[20];
get_line( buf, sizeof(buf) );
enum Cmd_tag cmd = CMD_NUM;
for( int i = 0; i < CMD_NUM; ++i ){
if( strcmp( buf, CMD_STR[i][CMD_STR_SHORT] ) == 0
|| strcmp( buf, CMD_STR[i][CMD_STR_LONG] ) == 0
){
cmd = i;
break;
}
}
if( 0 <= cmd && cmd < CMD_NUM ){
return CMD_FUNC[cmd]();
}
else{
puts( "そのコマンドは存在しません。" );
}
return CMD_RET_VALUE_CONTINUE;
}
/*
addコマンドの実行
*/
enum CmdRetValue_tag cmd_add(void)
{
char buf[40];
int value;
puts( "追加する数値データを入力してください。" );
fgets( buf, sizeof(buf), stdin );
sscanf( buf, "%d", &value );
add_elem( value );
return CMD_RET_VALUE_CONTINUE;
}
/*
deleteコマンドの実行
*/
enum CmdRetValue_tag cmd_delete(void)
{
char buf[40];
int value;
puts( "削除する数値データを入力してください。" );
fgets( buf, sizeof(buf), stdin );
sscanf( buf, "%d", &value );
if( delete_elem(value) >= 1 ){
puts( "要素を削除しました。" );
}
else{
puts( "削除する要素は見つかりませんでした。" );
}
return CMD_RET_VALUE_CONTINUE;
}
/*
searchコマンドの実行
*/
enum CmdRetValue_tag cmd_search(void)
{
char buf[40];
int value;
puts( "探索する数値データを入力してください。" );
fgets( buf, sizeof(buf), stdin );
sscanf( buf, "%d", &value );
if( search_elem(value) == NULL ){
printf( "%d は連結リスト中に存在しません。\n", value );
}
else{
printf( "%d は連結リスト中に存在します。\n", value );
}
return CMD_RET_VALUE_CONTINUE;
}
/*
clearコマンドの実行
*/
enum CmdRetValue_tag cmd_clear(void)
{
clear_list();
return CMD_RET_VALUE_CONTINUE;
}
/*
printコマンドの実行
*/
enum CmdRetValue_tag cmd_print(void)
{
print_list();
return CMD_RET_VALUE_CONTINUE;
}
/*
exitコマンドの実行
*/
enum CmdRetValue_tag cmd_exit(void)
{
puts( "終了します。" );
return CMD_RET_VALUE_EXIT;
}
/*
要素を追加する
引数：
value: 追加する要素の数値データ。
*/
void add_elem(int value)
{
// リストの末尾を探す
struct LinkedList_tag* tail = search_tail();
// 追加する要素を作る
struct LinkedList_tag* elem = malloc( sizeof(struct LinkedList_tag) );
if( elem == NULL ){
fputs( "メモリ割り当てに失敗しました。", stderr );
exit( 1 );
}
elem->value = value;
elem->next = NULL; // 末尾に追加するので、次の要素は無い
// これまで末尾だった要素は、末尾から２番目の位置になる。
// そのため、nextメンバを書き換えて、新たな末尾の要素を指すようにする。
tail->next = elem;
}
/*
要素を削除する
引数：
value： 削除する要素が持つ数値データ。
戻り値：
削除できた要素の個数を返す。
*/
int delete_elem(int value)
{
struct LinkedList_tag* p = gHead.next;
struct LinkedList_tag* prev = &gHead;
int count = 0;
while( p != NULL ){
if( p->value == value ){
// 削除する要素の１つ手前の要素の nextメンバを、
// 削除する要素の次の要素を指すように書き換える
prev->next = p->next;
// 要素は malloc関数で生成したので、free関数による解放が必要。
// 上記の prev->next = p->next よりも後で行わないと、不正なポインタが
// prev->next に代入されてしまうことに注意。
free( p );
// 続行するなら、p を正しい要素を指すようにする
p = prev->next;
++count;
}
else{
prev = p;
p = p->next;
}
}
return count;
}
/*
要素を空にする
*/
void clear_list(void)
{
struct LinkedList_tag* p = gHead.next;
struct LinkedList_tag* prev = &gHead;
while( p != NULL ){
// 削除する要素の１つ手前の要素の nextメンバを、
// 削除する要素の次の要素を指すように書き換える
prev->next = p->next;
// 要素は malloc関数で生成したので、free関数による解放が必要。
// 上記の prev->next = p->next よりも後で行わないと、不正なポインタが
// prev->next に代入されてしまうことに注意。
free( p );
p = prev->next;
}
}
/*
要素を出力する
*/
void print_list(void)
{
struct LinkedList_tag* p = gHead.next;
if( p == NULL ){
puts( "リストは空です。" );
return;
}
while( p != NULL ){
printf( "%d\n", p->value );
p = p->next;
}
}
/*
末尾の要素を探す
戻り値：
連結リストの末尾にある要素を指すポインタ。
*/
struct LinkedList_tag* search_tail(void)
{
struct LinkedList_tag* p = &gHead;
while( p->next != NULL ){
p = p->next;
}
return p;
}
/*
指定した値を持つ要素を探す
引数：
value： 探し出す要素が持つ数値データ。
戻り値：
先頭から連結リストをたどり、最初に見つけた value と同じ値を持つ要素のメモリアドレス。
見つからなかった場合は NULL を返す。
*/
struct LinkedList_tag* search_elem(int value)
{
struct LinkedList_tag* p = gHead.next;
while( p != NULL ){
if( p->value == value ){
return p;
}
p = p->next;
}
return NULL;
}
/*
標準入力から１行分受け取る
受け取った文字列の末尾には '\0' が付加される。
そのため、実際に受け取れる最大文字数は size - 1 文字。
引数：
buf: 受け取りバッファ
size: buf の要素数
戻り値：
buf が返される
*/
void get_line(char* buf, size_t size)
{
fgets(buf, size, stdin);
// 末尾に改行文字があれば削除する
char* p = strchr(buf, '\n');
if (p != NULL) {
*p = '\0';
}
}このプログラムを実行すると、コマンドの入力を求められます。たとえば、“a” または “add” と入力すると、連結リストへ要素を追加しようとします。このコマンドの場合は、続けて、追加する要素の入力を求められます。
リストへの要素の追加、要素の削除、全削除、探索、中身の出力のコマンドを実装しています。とりあえず、適当に追加や削除を行い、中身を出力してみて動作を確かめてみてください。
それでは、１つずつ実装を確認していきます。
初期化 🔗
まず、main関数から呼び出している init_head関数を見てください。この関数の中で、グローバル変数gHead のメンバを初期化しています。Ｃ言語編では何度か「グローバル変数を使うべきではない」と書いていますが、ここではサンプルプログラムとしての割り切りです。より実戦的な実装方法を後で詳しく取り上げます。
このグローバル変数gHead は、単方向線形リストの先頭の要素のことです。この先頭要素は、有効なデータを格納せず、ダミーの要素という役割を持たせています。このようなダミーの要素を作ることで、リストが空の場合を考慮せずに各種機能を実装できます。
gHead.next には NULL が格納されています。線形リストでは、nextポインタを NULL にすることで、線形リストの末尾の要素であることを表現します。次がないので末尾だということです。
gHead.next が NULL なので、gHead はリストの先頭であると同時に末尾でもあります。この後、addコマンドによって要素を追加すれば、gHead は末尾ではなくなりますが、先頭ではあり続けます。
gHead.value に 0 を格納していることには、特に意味はありません。どのみちダミーの要素なので、この値が参照されることはないので、何が入っていても構いません。しかし、Ｃ言語では有効な値を与えないと不定な状態のままですから、一応適当な値を入れておいた方が良いでしょう。
末尾への要素の追加 🔗
次に、要素の追加です。今回のサンプルでは、要素は必ずリストの末尾に追加するようになっています（要素を途中に挿入する方法は、後で取り上げます）。
配列と違って、連結リストの各要素を添字でアクセスすることができませんから、末尾へ追加するには、まずは末尾の要素を探し出さなければなりません。
そのためには、先頭の要素から順番に nextポインタをたどっていく必要があります。nextポインタが NULL の要素を発見したら、それが末尾の要素です。この処理は、search_tail関数が行っています。
想像どおり、末尾を探す処理は効率が悪いです。リストの要素数が多ければ多いほど時間がかかることも想像できると思います。
末尾を探す時間を減らすには、末尾の要素をどこかに記憶しておくと良いでしょう。
末尾の位置が分かれば、新しい要素を追加する作業に取り掛かります。この部分のコードを抜粋します。
// 追加する要素を作る
struct LinkedList_tag* elem = malloc( sizeof(struct LinkedList_tag) );
if( elem == NULL ){
fputs( "メモリ割り当てに失敗しました。", stderr );
exit( 1 );
}
elem->value = value;
elem->next = NULL; // 末尾に追加するので、次の要素は無い
// これまで末尾だった要素は、末尾から２番目の位置になる。
// そのため、nextメンバを書き換えて、新たな末尾の要素を指すようにする。
tail->next = elem;まず、新しい要素を作ります。ここでは、動的メモリ割り当てを行います。通常のローカル変数では、関数を抜け出した時点で消えてしまうので正しくありません。
作られた要素の valueメンバに値を格納し、nextポインタには NULL を格納しておきます。今回は末尾に追加するので、nextポインタは NULL です。
さて、この後が問題です。新しく作られた要素が末尾に来なければならないのですから、今まで末尾にあった要素は末尾ではなくなります。ですから、今まで末尾だった要素の nextポインタを、新しく作った要素を指し示すように書き換える必要があります。
このようにポインタの付け替えを頻繁に行うのが、連結リストの実装の特徴の１つです。ポインタの理解は必須なのです。
要素の探索 🔗
次に、目的の要素の探し方を確認しておきましょう。この処理は、search_elem関数が行っています。
方法としては、やはり先頭要素から順番に nextポインタをたどっていくだけです。nextポインタが NULL の要素を見つけるまでの間に、valueメンバの中身が目的の値と一致しているものがあるかを調べています。
なお、search_tail関数と違い、最初に探す場所が gHead ではなくて gHead.next から始まっていることに注意してください。gHead はダミーの要素なので、ここを探索対象に加えてしまうと、偶然ダミーデータと一致してしまうかもしれません。
要素の削除 🔗
続いて、要素の削除です。
実装は delete_elem関数を見てください。連結リストの理解で一番難しいのは、恐らく、この削除の部分です。ポインタの理解が曖昧だったり、連結リストの図解イメージが頭に浮かんでいなかったりすると理解できないでしょう。コードだけから理解しようとしないことが懸命です。
削除する要素を探し出す部分は、先ほど見た search_elem関数と同様に、先頭から順番に nextポインタをたどるだけですが、残念ながら search_elem関数をそのまま使うことはできません。
なぜかというと、削除する要素の１つ手前の要素を知りたいからです。要素が削除されたら、その手前の要素の nextポインタが、削除された要素の次の要素を指すように書き換わらなければならないのです。
そこで、目的の要素を探しながら、１つ手前の要素も保存しておくようにします。１つ前の要素を指し示すポインタは、prev という名前になっていますが、これは「前の」という意味の「previous」を略したもので、よく使われる名前です。今後は prevポインタと表現します。
prevポインタを保存しておけば、１つ手前の要素の nextポインタの書き換えが可能です。ややこしいですが、prev->next を書き換えるということです。
削除する要素の１つ手前の要素の nextポインタは、削除する要素の後ろにある要素を指し示すようになります。すなわち、次のようになります。
prev->next = p->next;この文の実行は、実際に要素を削除するコード (free関数の呼び出し）よりも先に行わなくてはなりません。free関数を呼び出してしまったら、ポインタp が指す先の状態は不定であって、アクセスしてはいけないからです。
削除後、リストをたどる作業を続けるのなら、p = prev->next として、正しい要素を指し示すポインタp を用意しなおします。
要素のクリア 🔗
要素の削除の方法さえ理解すれば、全要素を削除する処理はそれほど苦労しないでしょう。実装は、clear_list関数を見てください。
今回はすべての要素がなくなるので、１つ手前の要素の nextポインタを書き換える必要はありません。それでも prevポインタを作っているのは、free関数の呼び出し後に、続きから再開できるようにするためだけです。
リストの出力 🔗
最後に、リストの全要素の出力です。これは、print_list関数を見てください。
ここまで理解できていたら、この関数は簡単です。先頭要素から nextポインタをたどりながら、データを出力するだけです。
