アルゴリズムとデータ構造編【データ構造】 第4章 連結リストA(双方向・循環)

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

この章の概要

この章の概要です。

単方向循環リスト

前章で、連結リストには4通りのパターンがあると書きました。 それは、

この4つです。 このうち、最初の「単方向で線形なリスト」は、前章で解説しました。 本章では、残りの3パターンについて解説します。

まずは、「単方向で循環なリスト」です。

循環というのは、連結リストの末尾の要素の次に、先頭の要素が来るような構造を指します。 イメージ図は次のようになります。

単方向循環リスト

結局のところ、「単方向で線形なリスト」との違いは、末尾の要素の nextポインタが NULL ではなく、先頭の要素を指すようになったという点だけです。

末尾の次が先頭に戻ってくるため、リスト全体の要素に対して何らかの処理を行うとき、最後の要素の nextポインタが NULL かどうかという判定方法が使えなくなります。 代わりに、開始位置を覚えておき、nextポインタが開始位置と一致しているかどうかで、最後の要素を判定します。
しかし、前章の単方向線形リストの例のように、先頭にダミーの要素があるのなら、最後の要素の 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 = head;  /* 循環するので nextポインタは自分自身を指す */

	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 = list;   /* 末尾に追加するので、次の要素は先頭 */

	/* これまで末尾だった要素は、末尾から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 != list ){
		/* 削除する要素の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 == list ){
		puts( "リストは空です。" );
		return;
	}

	while( p != list ){
		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 != list ){
		p = p->next;
	}

	return p;
}

実行結果:

10
20
100
200
1000
2000

循環しない場合との違いは、以下の部分です。

これら以外に違いはありません。 これらの変化はいずれも、最後の要素の次の要素の扱い方が変わったことに起因したものです。


さて、循環リストは、循環しない連結リストと比べて何が良くなっているのでしょうか。

循環リストの方が有利に使えるかどうかは、有利になるように使うかどうかにかかっています。 次の2点が、循環しないリストと比べて、有利になり得る場面です。

途中からでも全体を辿れるという性質は、前回使った要素から処理を再開させるような場合に有利に働きます。 この場合、一周したかどうかという終了判定が必要になりますが、これは開始要素のアドレスを覚えておけば可能です。

最後の要素を記憶しておけば、先頭の要素は nextポインタを見るだけで参照できますから、先頭も末尾も同時に高速参照できるという訳です。 先頭と末尾が、いずれも参照頻度が高いような場合、これは大きな利点になり得ます。

双方向線形リスト

今度は、「双方向で線形なリスト」です。 循環はしないので、前の項から続けて読んでいる人は、一度頭を切り替えて下さい。

単方向な連結リストが、後続の要素へのポインタ(nextポインタ) だけを持つのに対し、 双方向な連結リストは、手前の要素へのポインタも持ちます。 これによって、前後どちらの方向へでも連結を辿ることが可能になります。
なお、双方向の連結リストは、単に双方向リストと呼んだり、重連結リストと呼ばれることもあります。

このタイプのイメージ図は次のようになります。

双方向線形リスト

ちょっと複雑になりますが、1つ前の要素へのポインタが追加されているだけです。 1つ後ろの要素へのポインタを nextポインタと呼んでいたように、今後は1つ前の要素へのポインタは prevポインタと呼ぶことにします。
この prevポインタを保持しなければならなくなったので、要素1つを示す構造体にもメンバが1つ追加されます。

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

次の要素がないとき nextポインタを NULL にするのと同様、前の要素がないときには prevポインタを NULL にします。 先頭にダミーの要素を置いているのなら、ダミー要素の prevポインタが常に NULL になります。

単方向の連結リストと、双方向の連結リストとでは、ポインタのつなぎ変えが起こる場面での実装が変わってきます。 prevポインタの方も書き換えないといけないため、前後両方の要素に影響を与えることになるので、複雑さが増してくるのです。

ここでは、前章の最初のサンプルのように、動作確認が行える大きめのプログラムを示します。

#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);
static struct LinkedList_tag* delete_one_node(struct LinkedList_tag* node);


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

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;
	gHead.prev = 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;   /* 末尾に追加するので、次の要素は無い */
	elem->prev = tail;   /* 末尾に追加するので、前の要素はこれまでに末尾だった要素 */

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

/*
	要素を削除する

	引数:
		value:	削除する要素が持つ数値データ。
	戻り値:
		削除できた要素の個数を返す。
*/
int delete_elem(int value)
{
	struct LinkedList_tag* p = gHead.next;
	int count = 0;

	while( p != NULL ){
		if( p->value == value ){
			p = delete_one_node( p );
			++count;
		}
		else{
			p = p->next;
		}
	}

	return count;
}

/*
	要素を空にする
*/
void clear_list(void)
{
	struct LinkedList_tag* p = gHead.next;

	while( p != NULL ){
		p = delete_one_node( p );
	}
}

/*
	要素を出力する
*/
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;
}

/*
	1つの要素を削除する

	引数:
		node:	削除する要素を指すポインタ。
	戻り値:
		削除後に有効なポインタ。
*/
struct LinkedList_tag* delete_one_node(struct LinkedList_tag* node)
{
	/* 削除する要素の1つ手前の要素を保存しておく。
	   多少分かりやすくなるという意味もあるが、それよりも、このあと node は free関数で解放されるため、
	   誤って node->prev や node->next を参照しないようにすることに意味がある。
	*/
	struct LinkedList_tag* const prev = node->prev;

	/* 削除する要素の1つ後ろの要素の prevポインタは、
	   削除する要素の1つ手前の要素を指すように書き換える。
	   ただし、1つの後ろの要素が存在しない可能性を考慮しなければならない。
	*/
	if( node->next != NULL ){
		node->next->prev = prev;
	}

	/* 削除する要素の1つ手前の要素の nextポインタを、
	   削除する要素の次の要素を指すように書き換える。
	   node->next は NULL の可能性があるが、その場合、prev->next が NULL になるのが正解なので、
	   そのまま代入してしまえば良い。
	*/
	prev->next = node->next;

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

	/* 削除した要素の次にあった要素へのポインタを返す。これは NULL の可能性もある。
	   ここで、node->next のように書くと、free関数で解放済みの領域をアクセスしてしまうので不適切。
	*/
	return prev->next;
}

内容は前章のものと同じですが、双方向リストになるように書き換えています。

一番難しいのは、要素を削除するときです。 今回は、要素1つを削除する部分を delete_one_node関数にまとめてあります。 かなり詳細なコメントを加えてあるので、じっくり読んでみて下さい。

一箇所だけ NULLチェックを必要としている箇所があります。 これは、末尾の要素を削除するケースでは、node->next が NULL であるため、node->next->prev を参照できないからです。
これについては、循環式の双方向リストであれば、node->next が先頭の要素を指しているはずなので、NULLチェックは不要になります。 あるいは、ダミーの先頭要素を用意するのと同じ考え方で、ダミーの末尾要素を置いておけば不要になります。


双方向の連結リストの利点は、リスト内のどの要素を参照しても、前後両方の要素を辿れることにあります。 単方向のリストでは、要素の削除を行うときに常に手前の要素を保存しながら走査する必要がありましたが(前章参照)、 そういう厄介事から解放されます。

一方で、prevポインタが増えたことにより、1要素ごとにポインタ変数1個分のメモリを多く消費するようになることが欠点です。 現代的には、メモリに余裕がある環境が大半ですが、場合によってはやはり節約したいこともあります。
プログラミング言語の種類によっては、標準ライブラリの中にリスト構造が用意されていることもありますが、 メモリ消費量が気になる場合、これが双方向として実装されているのかどうかは確認しておくべきです。

例えば、C++ の標準ライブラリに含まれている list は双方向リストです。 単方向で十分な場合、これは無駄になってしまうため、非標準の単方向リストを別途用意しているコンパイラが多くあります。 このような事情を踏まえ、C++11 では、正式仕様として単方向版の forward_list が追加されることになりました。

また、prevポインタが増えたことで、要素の挿入や削除の際に付け替えなければならないポインタの数が倍になっていますから、 作業量が増加することも欠点になります

双方向循環リスト

最後に、「双方向で循環なリスト」です。

これはもう簡単なのでさらっと流します。 要するに、nextポインタと prevポインタを両方持っており、かつ、最後の要素の次に最初の要素が来るように循環しているものを指します。 循環の場合の特徴、双方向の場合の特徴はいずれも、これまでに見てきた通りであり、それが組み合わさっただけです。

まとめ

2章に渡って、連結リストの4つのパターンを見てきました。 どのパターンであっても、連結リストとしての共通特性は持っています(これは前章のまとめの通りです)

メモリ消費量の増加と、ポインタの付け替えの作業量の増加という双方向リストの欠点を受け入れられるのであれば、 通常、単方向リストよりも双方向リストの方が便利に使えます。

循環リストは、リスト内の途中の要素から走査を開始するようなことが多いのであれば有利に働きます。


練習問題

問題@ 双方向循環リストの末尾から先頭に向かって、要素の値を出力する関数を作成して下さい。

問題A 単方向循環リストから目的の要素を探し出す関数を作成して下さい。 このとき、リスト内の要素のアドレスを引数に取るようにし、その位置から探索を始めるように実装して下さい。

問題B 双方向線形リストにおいて、要素を途中に挿入する関数を作成して下さい。 前章の insert_elem関数と同じ引数・戻り値を持つように実装して下さい。


解答ページはこちら


参考リンク

更新履歴

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

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

'2011/9/24 新規作成。



前の章へ

次の章へ

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

Programming Place Plus のトップページへ