アルゴリズムとデータ構造編【データ構造】 第3章 連結リスト@(単方向・線形)

このエントリーをはてなブックマークに追加

この章の概要

この章の概要です。

連結リスト

配列に続いて取り上げるデータ構造は、連結リスト(リンクドリスト)です。 ここからちょっと難しくなっていきますが、これも基礎的なデータ構造ですから、確実に理解しましょう。

連結リストは、配列のように各要素を連続的に並べることをしません。 各要素は、メモリ上に飛び飛びの位置に置かれており、それぞれを何らかの方法で「連結(リンク)」します。
どう連結するかといえば、C言語であればポインタを使う訳です。 そういう訳で、ここからはポインタの理解が必須事項ですから、そこに不安がある場合はC言語編で学習してからにしましょう。

ポインタの使えない言語の場合、参照の仕組みがあればそれで実現できます。 それも使えないような一部の言語では、 配列で代用して、どの要素同士が連結されているかを添字を使って表現することによって、一応はシミュレートできます。


連結リストは、その実現の仕方によって幾つものパターンに細分化できます。
要素が、A→B→C→D のように、先へ先へと連結されていくものを線形リストと呼びます。 一方、A→B→C→D→A のように、最後の要素の先が最初の要素に戻ってくるようなものは、循環リストと呼ばれます。
更に、A⇔B⇔C⇔D のように、先へも前へも連結されているものを、双方向リストと呼び、 そうでなく、一方向だけに連結されているものを、単方向リストと呼びます。
循環リストや、双方向リストについては、第4章で解説します。

実際にはそれらを組み合わせて、全部で4通りのパターンが作られます。 つまり、

となります。 より特殊な連結リストも存在しますが、まず基本となるのはこの4パターンです。

単方向線形リスト

では、まずは単方向で線形なリストを取り上げます。 この構造のイメージ図は次のようになります。

単方向線形リスト

この図において、1つの塊は次のような構造体で表現できます。

struct LinkedList_tag {
	int                         value;
	struct LinkedList_tag*      next;
};

int型のメンバ value は何でも構いません。 型が違おうと、もっとメンバが多くても、連結リストとしては問題ありません。 これは要するに、配列を使った場合に、配列に格納していたものです。 int型の配列の代わりに連結リストを使うのなら、このように、int型のメンバを持つことになります。

連結リストの鍵となるのは、もう1つのメンバ 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* 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);

/* コマンド実行関数 */
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;
};

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];
	size_t len;
	enum Cmd_tag cmd;
	int i;

	fgets( buf, sizeof(buf), stdin );

	len = strlen( buf );
	buf[len - 1] = '\0';  /* fgets関数が受け取った改行文字を消す */

	for( 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[i]();
	}
	else{
		puts( "そのコマンドは存在しません。" );
	}

	return CMD_RET_VALUE_EXIT;
}

/*
	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* elem;
	struct LinkedList_tag* tail;

	/* リストの末尾を探す */
	tail = search_tail();

	/* 追加する要素を作る */
	elem = malloc( sizeof(struct LinkedList_tag) );
	if( elem == NULL ){
		fputs( "メモリ割り当てに失敗しました。", stderr );
		exit( 1 );
	}
	elem->value = value;
	elem->next = NULL;   /* 末尾に追加するので、次の要素は無い */

	/* これまで末尾だった要素は、末尾から2番目の位置になる。
	   そのため、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 ){
			/* 削除する要素の1つ手前の要素の 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 ){
		/* 削除する要素の1つ手前の要素の 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;
}

このプログラムを実行すると、コマンドの入力を求められます。 例えば、"a" または "add" と入力すれば、リストへ要素を追加しようとします。 このコマンドの場合は、続けて、追加する要素の入力を求められます。
リストへの要素の追加、要素の削除、全削除、探索、中身の出力のコマンドを実装しています。 とりあえず、適当に追加や削除を行い、中身を出力してみて動作を確かめてみて下さい。

さて、1つずつ実装を確認していきましょう。

初期化

まず、main関数の最初に呼び出している init_head関数を見て下さい。 この関数の中で、グローバル変数gHead のメンバを初期化しています。 C言語編で何度か、「グローバル変数を使うべきではない」と書いていますが、ここではサンプルプログラムとして割り切って下さい。 より現実に即した実装方法については、後で詳しく取り上げます

このグローバル変数gHead は、連結リストの先頭の要素のことです。 この先頭要素は、実際にはデータを格納することはせず、ダミーの要素としての役割を持たせています。 このようなダミーの要素を作ることで、連結リストが空の場合を考慮せずに各種機能を実装できます。

gHead.next は NULL が格納されていますが、このように nextポインタが NULL になっている要素は、連結リストの末尾の要素であることを表現しています。 したがって gHead は、連結リストの先頭であると同時に末尾でもある訳です。 この後、addコマンドによって要素を追加すれば、gHead は末尾ではなくなりますが、先頭ではあり続けます。

gHead.value に 0 を格納している点は、特に意味はありません。 どのみちダミーの要素なので、この値が参照されることは無いので、何が入っていても構いません。 しかし、C言語では何もしなければメモリの状態は不定ですから、よからぬトラブルの原因になることもあるので、 一応適当な値を入れておいた方が良いでしょう。

末尾への要素の追加

次に、要素の追加です。 今回のサンプルでは、要素は必ずリストの最後尾に追加されるようになっています。 (要素を途中に挿入する方法は、後で取り上げます

末尾へ追加するには、末尾を探し出す必要があります。 配列とは違い、直接アクセスできませんから、基本的に先頭の要素から順番に nextポインタを辿っていく必要があります。 (末尾の位置を高速に探せるように準備しておくことは可能です。これは次章で取り上げます。)

末尾を探す処理は、search_tail関数が行っています。
末尾の要素を探す方法は、先頭要素である gHead から始めて、nextポインタを辿っていくという単純なものです。 nextポインタが NULL である要素を発見したら、その要素が末尾だと分かります。
単純ですが、要素数が非常に多ければ時間が掛かります。 しかし、特別に工夫を加えない限り、連結リストとしてはやむを得ない部分でもあります。 工夫の例は、今後取り上げます。

末尾の位置が分かれば、新しい要素を追加する作業に取り掛かります。 この部分のコードを抜粋します。

/* 追加する要素を作る */
elem = malloc( sizeof(struct LinkedList_tag) );
elem->value = value;
elem->next = NULL;   /* 末尾に追加するので、次の要素は無い */

/* これまで末尾だった要素は、末尾から2番目の位置になる。
   そのため、nextメンバを書き換えて、新たな末尾の要素を指すようにする */
tail->next = elem;

まず、要素を作ります。 これは動的なメモリ割り当てを行うことになります。 単なる、ローカル変数では関数を抜け出したら消えてしまうのでダメです。
作られた要素の valueメンバに値を格納し、nextポインタには NULL を格納しておきます。 今回は末尾に追加するので、nextポインタが NULL になる訳です。

さて、この後が問題です。 新しく作られた要素が末尾に来る訳ですから、今まで末尾にあった要素はもはや末尾ではなくなります。 ですから、今まで末尾だった要素の nextポインタを、新しく作った要素を指し示すように書き換える必要があるのです。
このようにポインタの付け替えを頻繁に行うのが、連結リストの実装の特徴の1つになります。 ポインタの理解は必須なのです。

要素の探索

末尾の要素の探し方を確認したので、先に、目的の要素の探し方を取り上げておきましょう。 これは、search_elem関数が行っています。

方法としては、やはり先頭要素から順番に nextポインタを辿っていくだけです。 nextポインタが NULL の要素を見つけるまでの間に、valueメンバの中身が目的の値と一致しているものがあるかを調べています。

なお、search_tail関数と違い、最初に探す場所が gHead ではなくて gHead.next から始まっていることに注意して下さい。 gHead はダミーの要素なので、ここを探索対象に加えてしまうと、偶然ダミーデータと一致してしまうかも知れません。

要素の削除

続いて、要素の削除です。 実装は delete_elem関数を見て下さい。
何だか複雑そうですが、実際複雑です。 連結リストの理解で一番難しいのは、恐らく、この削除の部分です。 ポインタの理解が曖昧だったり、連結リストの図解イメージが頭に浮かんでいなかったりすると理解できないでしょう。 コードだけから理解しようとしないことが懸命です。

削除する要素を探し出す部分は、先ほど見た search_elem関数と同様、先頭から順番に nextポインタを辿るだけですが、 残念ながら search_elem関数をそのまま使うことができません。 これは、削除を行うときに、削除する要素の1つ手前の要素をどうにかして知る必要があるからです。 なぜかというと、削除された要素の1つ手前の要素には nextポインタがあり、それは削除する要素を指し示しているからです。 削除によって存在しなくなる要素を指し示したままにする訳にはいかないので、書き換える必要があります。

そこで、目的の要素を探しながら、1つ手前の要素も保存しておくようにします。 1つ前の要素を指し示すポインタは、prev という名前になっていますが、これは「前の」という意味の「previous」を略したもので、よく使われる名前です。 今後は prevポインタと表現します。
prevポインタさえ保存しておけば、1つ手前の要素の nextポインタの書き換えが可能になります。 ややこしいですが、prev->next を書き換えるということです。

nextポインタの状態がどうなるかというと、

となります。 すなわち、

prev->next = p->next;

です。 この文の実行は、実際に要素を削除するコード (free関数の呼び出し)よりも先に行わなくてはなりません。 free関数を呼び出したら、もうポインタp が指す先の状態は不定ですから、p->next は不定になっているためです。

削除後、続けてリストを辿る作業を続けるのなら、p = prev->next として、正しい要素を指し示すポインタp を用意し直します。

要素のクリア

要素の削除の方法さえ理解すれば、全要素を削除する処理はそれほど苦労しないでしょう。 実装は、clear_list関数を見て下さい。

今回はどうせ、全ての要素は存在しなくなるので、1つ手前の要素の nextポインタを書き換える必要はありません。 それでも、prevポインタを作っているのは、free関数の呼び出し後に、続きから再開できるようにするためだけです。
もちろん、nextポインタの方を取っておいてから、free関数を呼ぶような方法でもまったく問題ありません。

リストの出力

最後に、リストの全要素の出力です。 これは、print_list関数を見て下さい。

ここまで理解できていたら、この関数は簡単です。 やはり先頭要素から nextポインタを辿っていくだけです。

要素を挿入する

先ほどのサンプルでは、要素は末尾に追加する形を取りました。 そのためには、要素を先頭から辿っていき、末尾を探し出す必要があり、実は最も時間が掛かる場所に追加しています。

逆に、一番先頭に追加するのが一番高速です。 配列の場合、後続の要素をすべてずらす必要がありますから、先頭に追加する方が時間が掛かります。 その意味では、効率面では逆の関係にあります。

先頭への要素の追加は、次のようなコードになります。

void add_elem_front(int value)
{
	struct LinkedList_tag* elem;

	/* 追加する要素を作る */
	elem = malloc( sizeof(struct LinkedList_tag) );
	if( elem == NULL ){
		fputs( "メモリ割り当てに失敗しました。", stderr );
		exit( 1 );
	}
	elem->value = value;
	elem->next = gHead.next;

	/* ダミーの先頭要素の次は、追加した要素になる */
	gHead.next = elem;
}

先頭に追加するといっても、ダミーの先頭要素よりも手前に置くのではなくて、ダミーの直後に挿入します。 ダミーが持つ nextポインタの値を、追加する要素の nextポインタに代入し、 ダミーの nextポインタは、追加した要素を指すように書き換えます。


途中に要素を挿入する方法も、結局のところは同じことです。 添字が使えないため、挿入位置の指定方法が特殊になりますが、別に難しくはありません。
次の関数は、指定した値を持つ要素を探し、その要素の直後に挿入します。

int insert_elem(int value, int pos)
{
	struct LinkedList_tag* p;
	struct LinkedList_tag* elem;

	/* 追加位置を探す */
	p = search_elem( pos );
	if( p == NULL ){
		return 0;
	}

	/* 追加する要素を作る */
	elem = malloc( sizeof(struct LinkedList_tag) );
	if( elem == NULL ){
		fputs( "メモリ割り当てに失敗しました。", stderr );
		exit( 1 );
	}
	elem->value = value;
	elem->next = p->next;  /* p と p->next の隙間に挿入する */

	p->next = elem;
	
	return 1;
}

挿入位置を探し出すには、既に作成済みの search_elem関数が利用できます。 もし、挿入位置が見つからなければ、0 を返して終了するようにしてあります。 成功した場合は 1 を返しています。

ここでもやはり、ポインタの付け替えが肝になります。 挿入位置は、見つけた要素の直後なので、p の次が elem、elem の次が p->next になるように付け替えればいいことになります。
ちなみに、挿入位置がリストの末尾に来る可能性もありますが、この場合でも問題なく動作します。

ライブラリ化の方法

今回使ったサンプルプログラムでは、グローバル変数にダミーの先頭要素を用意しておき、ここを起点としてリストを形作っています。 しかし、実戦では、複数のリストを同時に扱いたいこともあるはずですから、この方法はサンプルとしてしか価値がありません。

同時に複数のリストを作るには、ダミーの先頭要素を必要な数だけ作り出せる必要があります。 そのためには、先頭要素自体も動的に作ります。 そうすれば、必要に応じて何個でもリストを作り出せます。

この考え方で作成したプログラムは以下の通りです。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>


static struct LinkedList_tag* create_list(void);
static void add_elem(struct LinkedList_tag* list, int value);
static void clear_list(struct LinkedList_tag* list);
static void print_list(struct LinkedList_tag* list);
static void delete_list(struct LinkedList_tag* list);
static struct LinkedList_tag* search_tail(struct LinkedList_tag* list);


/* 連結リスト型 */
struct LinkedList_tag {
	int                         value;
	struct LinkedList_tag*      next;
};


int main(void)
{
	struct LinkedList_tag* list0;
	struct LinkedList_tag* list1;
	struct LinkedList_tag* list2;

	/* リストを作る */
	list0 = create_list();
	list1 = create_list();
	list2 = create_list();

	/* リストに要素を追加 */
	add_elem( list0, 10 );
	add_elem( list0, 20 );
	add_elem( list1, 100 );
	add_elem( list1, 200 );
	add_elem( list2, 1000 );
	add_elem( list2, 2000 );

	/* 各リストの中身を出力 */
	print_list( list0 );
	print_list( list1 );
	print_list( list2 );

	/* リストを破棄 */
	delete_list( list0 );
	delete_list( list1 );
	delete_list( list2 );

	return 0;
}

/*
	リストを作成する

	戻り値:
		作成されたリスト。
*/
struct LinkedList_tag* create_list(void)
{
	struct LinkedList_tag* head;
	
	head = malloc( sizeof(struct LinkedList_tag) );
	if( head == NULL ){
		fputs( "メモリ割り当てに失敗しました。", stderr );
		exit( 1 );
	}

	head->value = 0;
	head->next = NULL;

	return head;
}

/*
	リストを破棄する

	引数:
		list:	破棄するリスト。
*/
void delete_list(struct LinkedList_tag* list)
{
	clear_list( list );

	free( list );
}

/*
	要素を追加する

	引数:
		list:	対象のリスト。
		value:	追加する要素の数値データ。
*/
void add_elem(struct LinkedList_tag* list, int value)
{
	struct LinkedList_tag* elem;
	struct LinkedList_tag* tail;

	/* リストの末尾を探す */
	tail = search_tail( list );

	/* 追加する要素を作る */
	elem = malloc( sizeof(struct LinkedList_tag) );
	if( elem == NULL ){
		fputs( "メモリ割り当てに失敗しました。", stderr );
		exit( 1 );
	}
	elem->value = value;
	elem->next = NULL;   /* 末尾に追加するので、次の要素は無い */

	/* これまで末尾だった要素は、末尾から2番目の位置になる。
	   そのため、nextメンバを書き換えて、新たな末尾の要素を指すようにする */
	tail->next = elem;
}

/*
	要素を空にする

	引数:
		list:	対象のリスト。
*/
void clear_list(struct LinkedList_tag* list)
{
	struct LinkedList_tag* p = list->next;
	struct LinkedList_tag* prev = list;

	while( p != NULL ){
		/* 削除する要素の1つ手前の要素の nextメンバを、
			削除する要素の次の要素を指すように書き換える */
		prev->next = p->next;

		/* 要素は malloc関数で生成したので、free関数による解放が必要。
			上記の prev->next = p->next よりも後で行わないと、不正なポインタが
			prev->next に代入されてしまうことに注意。 */
		free( p );

		p = prev->next;
	}
}

/*
	要素を出力する

	引数:
		list:	対象のリスト。
*/
void print_list(struct LinkedList_tag* list)
{
	struct LinkedList_tag* p = list->next;

	if( p == NULL ){
		puts( "リストは空です。" );
		return;
	}

	while( p != NULL ){
		printf( "%d\n", p->value );
		p = p->next;
	}
}

/*
	末尾の要素を探す

	引数:
		list:	対象のリスト。
	戻り値:
		連結リストの末尾にある要素を指すポインタ。
*/
struct LinkedList_tag* search_tail(struct LinkedList_tag* list)
{
	struct LinkedList_tag* p = list;

	while( p->next != NULL ){
		p = p->next;
	}

	return p;
}

実行結果:

10
20
100
200
1000
2000

リストを作るには、create_list関数を呼び出します。 この関数の内部で、ダミーの先頭要素が動的に作られ、メンバを初期化した後、戻り値として返されます。 これを受け取れば、グローバル変数で管理する必要はなくなります。
リストを削除するときには、delete_list関数を使います。

create_list関数以外の関数はすべてそうですが、引数に struct LinkedList_tag型のポインタを渡すようになっています。 ここに、create_list関数が返したポインタを渡せば、そのリストを対象として処理が行われます。 これで、何個リストが存在していても、適切なリストに対して処理が行える訳です。

まとめ

[長所]

[短所]


練習問題

問題@ この章の最初のサンプルプログラムに、連結リストに含まれている要素の個数を返すコマンドを追加して下さい。

問題A この章の最初のサンプルプログラムに、連結リストの要素を逆順に並べなおすコマンドを追加して下さい(やや難しいです)

問題B 連結リストの要素を、配列のように添字でアクセスするように出来るでしょうか?実装してみて下さい。 この機能は、実用上どのような問題があるでしょうか。


解答ページはこちら


参考リンク

更新履歴

'2015/2/21 サンプルプログラムで、ファイルスコープでよい関数に static を付加。

'2014/12/20 サンプルプログラムで、コマンド処理の方法を整理。

'2014/12/16 誤字修正。

'2011/9/2 新規作成。



前の章へ

次の章へ

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ