連結リスト

片方向リストの実装例 (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

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