サイトアイコン GAMEWORKS LAB

連結リスト

チャラ

連結リスト

連結リストとは各ノードに別のノードへのリンクを持つことによりデータ間を連結していくデータ構造になっています。
リンクリストとも呼ばれます。
又、連結リストにはいくつか種類があります。

今回の記事では線形リストについて説明していきます。

連結リストの種類

連結リストの基本的な構造には2種類があります。

 

連結リストの特徴

連結リストは使い勝手のいいデータ構造なのですが、メリットとデメリットがあります。

メリット
デメリット

他にもありますが、大きくはこんな感じになるかと思います。

 

連結リストの仕組み

連結リストの各種類について実装を説明していきます。

片方向リスト

片方向リストとは各ノードが次のノードへのリンクのみ持っているリスト構造です。
※単方向リストとも呼ばれます。

ノード上に値(データ)とリンクを持っています。
各ノードは次のノードへのみ参照可能です。

このリストでは手前のノードに対して参照はできません。

 

双方向リスト

双方向リストとは各ノードが前後両方のリンクを持っているリスト構造です。

片方向と同じで値(データ)とリンクを持っています。
ただし、各ノードは前後のノードへの参照が可能です。

遡って参照が可能なので便利ですが、その分リンクの情報が増えます。

 

片方向リストの実装例 (C言語)

今回はC言語でリンクリストを実装する際の例を記述します。

ノード構造定義
struct LinkedNode
{
	int value;         // 値(任意のデータ)
	LinkedNode* pNext; // 次のノードへのポインタ(リンク)
};

ノードは任意のデータとリンク情報を持ちます。
※実際に使う際にはデータの部分を用途に応じて変更します。

 

ノードの基本処理
LinkedNode* pHead = NULL;	// 先頭ノード
LinkedNode* pTail = NULL; 	// 末尾ノード

// ノードの追加
void AddNode(LinkedNode* pNode)
{
	// ノードがない場合は先頭=末尾のノードとなる
	if (pHead == NULL)
	{
		pHead = pTail = pNode;
		return;
	}
	// 現在の末尾の次のノードとして登録する
	pTail->pNext = pNode;
	// 追加されたノードを末尾にする
	pTail = pNode;
}

// ノードの削除
void RemoveNode(LinkedNode* pNode)
{
	LinkedNode* prev = NULL;
	LinkedNode* temp = pHead;
	// 先頭のノードから順に一致するノードを検索していく
	while (temp)
	{
		// 一致すれば削除
		if (temp == pNode)
		{
			// 削除するノードの手前にノードがあれば
			// 手前のノードの次を削除するノードの次のノードとつなぎ合わせる
			if (prev) prev->pNext = pNode->pNext;

			// 先頭ノードが削除される場合は先頭ノードを次のノードに差し替える
			if (pNode == pHead) pHead = pNode->pNext;
			// 末尾のノードが削除される場合は手前のノードに差し替える
			if (pNode == pTail) pTail = prev;

			// メモリを解放する
			free(pNode);
			break;
		}
		// 手前のノードと現在のノードを進める
		prev = temp;
		temp = temp->pNext;
	}
}

// ノードの作成
LinkedNode* CreateNode(int value)
{
	// ノードのメモリを確保する
	LinkedNode* pNode = (LinkedNode*)malloc(sizeof(LinkedNode));

	// ノードの値を設定して次のノードを初期化
	pNode->value = value;
	pNode->pNext = NULL;

	return pNode;
}
// ノードの削除
void DeleteAll(void)
{
	// ノードが無くなるまで削除し続ける
	while(pHead)
	{
		RemoveNode(pHead);
	}
}

これでノードの追加や削除を行う基本の処理が出来ました。
では実際に追加や削除を行うテスト処理を作ってみましょう。

// ノードの実装テスト
void NodeTest(void)
{
	// データの追加と削除のテスト
	// 2, 5, 3, 1のデータを追加してから2のノードを削除する
	LinkedNode* temp = CreateNode(2);
	AddNode(temp);
	AddNode(CreateNode(5));
	AddNode(CreateNode(3));
	AddNode(CreateNode(1));
	RemoveNode(temp);

	// 現在のノード内容を順番に表示する
	LinkedNode* pNode = pHead;
	while (pNode)
	{
		printf("Value:%d\n", pNode->value);
		pNode = pNode->pNext;
	}
	// ノードを全て削除する
	DeleteAll();
}

・実行結果

Value:5
Value:3
Value:1

このようにデータの追加と削除が行えます。

 

双方向リストの実装例 (C言語)

次は双方向リストの実装例について記載していきます。

ノード構造定義
struct LinkedNode
{
	int value;         // 値(任意のデータ)
	LinkedNode* pNext; // 次のノードへのポインタ(リンク)
	LinkedNode* pPrev; // 前のノードへのポインタ(リンク)
};

双方向リストのノードも任意のデータとリンク情報を持ちます。

 

ノードの基本処理
LinkedNode* pHead = NULL;	// 先頭ノード
LinkedNode* pTail = NULL; 	// 末尾ノード<

// ノードの追加
void AddNode(LinkedNode* pNode)
{
	// ノードがない場合は先頭=末尾のノードとなる
	if (pHead == NULL)
	{
		pHead = pTail = pNode;
		return;
	}

	// 現在の末尾の次のノードとして登録する
	pTail->pNext = pNode;
	// 末尾を追加したノードの手前のノードとして登録する
	pNode->pPrev = pTail;

	// 追加されたノードを末尾にする
	pTail = pNode;
}

// ノードの削除
void RemoveNode(LinkedNode* pNode)
{
	// 手前にノードがある場合は次のノードとリンクさせる
	if (pNode->pPrev) pNode->pPrev->pNext = pNode->pNext;
	// 次のノードがある場合は手前のノードとリンクさせる
	if (pNode->pNext) pNode->pNext->pPrev = pNode->pPrev;

	// 先頭ノードが削除される場合は先頭ノードを次のノードに差し替える
	if (pNode == pHead) pHead = pNode->pNext;
	// 末尾のノードが削除される場合は手前のノードに差し替える
	if (pNode == pTail) pTail = pNode->pPrev;

	// メモリを解放する
	free(pNode);
}


// ノードの作成
LinkedNode* CreateNode(int value)
{
	// ノードのメモリを確保する
	LinkedNode* pNode = (LinkedNode*)malloc(sizeof(LinkedNode));

	// ノードの値を設定して前後のノードを初期化
	pNode->value = value;
	pNode->pNext = NULL;
	pNode->pPrev = NULL;

	return pNode;
}
// ノードの削除
void DeleteAll(void)
{
	// ノードが無くなるまで削除し続ける
	while(pHead)
	{
		RemoveNode(pHead);
	}
}

双方向リストは前後のリンクを持っているの削除処理の際にノードの検索が不要になります。
今回の例では大きな違いは削除処理だけですが、実際に使う用途に応じてどちらのリストが都合がいいかは変わってきます。

実際に使う際には配列とリストのどちらが都合がいいのか？
片方向と双方向のどちらのリストがいいのか？

それぞれの利点に合わせて設計をしましょう。

モバイルバージョンを終了