連結リスト(片方向)でpushとpopをc言語で実装(サンプルコードあり)

連結リスト(片方向)でpushとpopをc言語で実装

連結リスト(片方向)でpushとpopをc言語で実装してみました。

下記の記事で、配列をスタック構造としてpush/popを実装しています。
参考：スタックのpush,pop関数をC言語とPythonで実装

まずは、片方向リストを構造体で定義します。
リストの構造体には、先頭のノードのポインタをメンバ変数に定義します。
ノードの先頭がわかるようになるので、実装が楽になりました。

typedef struct node{
	int			data;
	struct node*	pNextNode;
}node_t;

typedef struct list{
	node_t* pTopNode;
}list_t;

ノードをmalloc()で確保

続いて、下記は初期化関数です。
最初のノードをmalloc()で確保します。
ノードのpNextNodeにはNULLを代入します。

関数の引数に構造体を渡す場合の注意点を、下記の記事で書いています。
参考：[c言語]関数の引数に構造体を渡す場合の注意(サンプルコードあり)

node_t* initNode(int data){
	node_t* pNode = NULL;
	
	pNode = (node_t*)malloc(sizeof(node_t));
	if(pNode == NULL){
		printf("malloc error\n");
		return NULL;
	}
	pNode->data = data;
	pNode->pNextNode = NULL;

	return pNode;
}
list_t* initList(int data){
	list_t* pList = NULL;
	
	pList = (list_t*)malloc(sizeof(list_t));
	if(pList == NULL){
		printf("init list malloc error\n");
		return NULL;
	}

	pList->pTopNode = initNode(data);
	if(pList->pTopNode == NULL){
		printf("init node error\n");
		free(pList);
		return NULL;
	}
	printfList(pList);
	
	return pList;
}

push関数

push関数になります。
while()で終端ノードを探索します。
新規で作成したノードのポインタを、終端ノードのpNextNodeに格納します。

void push(list_t* pList, int data){
	node_t* pNode = NULL;

	if(pList == NULL){
		printf("NULL chk error\n");
		return;
	}
	//リストが空の場合はノードを生成
	if(pList->pTopNode == NULL){
		pList->pTopNode = initNode(data);
		if(pList->pTopNode == NULL){
			printf("push error\n");
		}
		printfList(pList);
		return;
	}
	
	pNode = pList->pTopNode;
	
	while(pNode->pNextNode != NULL){
		pNode = pNode->pNextNode;		
	};
	
	pNode->pNextNode = initNode(data);
	if(pNode->pNextNode == NULL){
		printf("push erro\n");
		return; 
	}
	
	printfList(pList);
	
	return;
}

pop関数

pop関数になります。
while()で終端ノードを探索します。
終端ノードをfree()して、終端ノードの一つ前のpNextNodeにNULLを格納します。

void pop(list_t* pList){
	node_t* pPreNode = NULL;
	node_t* pNode = NULL;
	
	if(pList == NULL){
		printf("NULL chk error\n");
		return;
	}
	if(pList->pTopNode == NULL){
		printf("list empty\n");
		return;
	}
	
	pPreNode = pList->pTopNode;
	pNode = pList->pTopNode;
	
	while(pNode->pNextNode != NULL){
		pPreNode = pNode;
		pNode = pNode->pNextNode;
	}
	pPreNode->pNextNode = NULL;
	
	//リストが空になった場合の処理
	if(pNode == pList->pTopNode){
		pList->pTopNode = NULL;
		free(pNode);
		
		return;
	}
	free(pNode);		
	printfList(pList);

	return;
}

指定した値を持つノードを削除

指定した値を持つノードを削除する関数です。
連結リストの各ノードをループ処理しながら、指定した値を持つノードを探索します。
探索で位置したノードがあれば、そのノードをfree()して、前後のノードを連結し直します。
pPreNode, pTmpNode, pNodeを３つの変数を用いているところがコーディングのポイントですね。

void deleteNodeData(list_t* pList, int data){
	node_t* pNode = NULL;
	node_t* pPreNode = NULL;
	node_t* pTmpNode = NULL;

	if(pList == NULL){
		printf("NULL chk error\n");
		return;
	}
	if(pList->pTopNode == NULL){
		printf("list empty\n");
		return;
	}
	pNode = pList->pTopNode;
	pPreNode = pNode;
	while(pNode != NULL){
		if(pNode->data == data){
			//ノードの張替え
			if(pNode == pList->pTopNode){
				pList->pTopNode = pNode->pNextNode;
			}else{
				pPreNode->pNextNode = pNode->pNextNode;
			}
			pTmpNode = pNode;
			pNode = pNode->pNextNode;
			free(pTmpNode);
		}else{
			pPreNode = pNode;
			pNode = pNode->pNextNode;
		}	
	}
	printfList(pList);
	
	return;
}

重複したノードを削除

続いて、重複した値を持つノードを削除して、ユニークなノードのみにする関数です。
ノードのポインタを２つ用意して、２重にループ処理して各ノード同士の値を比較していきます。
比較して一致した場合には、片方向のノードをfree()して、前後のノードを再連結していきます。

void deleteDupNode(list_t* pList){
	node_t* pNode_1 = NULL;
	node_t* pNode_2 = NULL;
	node_t* pPreNode_2 = NULL;
	node_t* pTmpNode = NULL;
	
	if(pList == NULL){
		printf("NULL chk error\n");
		return;
	}
	if(pList->pTopNode == NULL){
		printf("list empty\n");
		return;
	}
	
	pNode_1 = pList->pTopNode;
	pPreNode_2 = pNode_1;
	pNode_2 = pNode_1->pNextNode;

	
	while(pNode_1->pNextNode != NULL){
		while(pNode_2 != NULL){
			if(pNode_1->data == pNode_2->data){
				pPreNode_2->pNextNode = pNode_2->pNextNode;
				pTmpNode = pNode_2;
				pNode_2 = pNode_2->pNextNode;
				free(pTmpNode);
			}else{
				pPreNode_2 = pNode_2;
				pNode_2 = pNode_2->pNextNode;	
			}
		}
		pNode_1 = pNode_1->pNextNode;
		pPreNode_2 = pNode_1;
		//最終ノードが削除された場合は、pNode_1=NULLとなる
		//pNode_1->pNextNodeでfaultするのを回避
		if(pNode_1 == NULL){
			break;
		}else{
			pNode_2 = pNode_1->pNextNode;
		}
	}
	printfList(pList);
	
	return;	
}

リストをfree()してメモリ解放

構造体のメンバ変数を参照するサンプルコードを下記の記事で書いています。
参考：[c言語]構造体のメンバ変数を参照するサンプルコード

最後に、リストをfree()してメモリ解放する関数になります。
各ノードを先頭から解放して、最後にリストを解放します。

void deleteList(list_t* pList){
	node_t* pPreNode = NULL;
	node_t* pNode = NULL;
	
	if(pList == NULL){
		printf("NULL chk error\n");
		return;
	}

	pPreNode = pList->pTopNode;
	pNode = pList->pTopNode;
	
	while(pNode != NULL){
		pPreNode = pNode;
		pNode = pNode->pNextNode;
		free(pPreNode);
	}
	free(pList);
	
	return;
}

サンプルコード

下記がサンプルコードになります。
main()関数では、動作確認も兼ねていたので、push/popを複数回繰り返しています。
呼び出し元でのエラーチェックは今回は行っていません。

 $ cat sample.c 
#include <stdio.h>
#include <stdlib.h>

typedef struct node{
	int			data;
	struct node*	pNextNode;
}node_t;

typedef struct list{
	node_t* pTopNode;
}list_t;

void printfList(list_t* pList){
	node_t* pNode = pList->pTopNode;

	if(pList == NULL){
		printf("NULL chk error\n");
		return;
	}

	while(pNode != NULL){
		printf("%d ", pNode->data);
		pNode = pNode->pNextNode;
	};
	printf("\n");
	
	return;
}

node_t* initNode(int data){
	node_t* pNode = NULL;
	
	pNode = (node_t*)malloc(sizeof(node_t));
	if(pNode == NULL){
		printf("malloc error\n");
		return NULL;
	}
	pNode->data = data;
	pNode->pNextNode = NULL;

	return pNode;
}

void push(list_t* pList, int data){
	node_t* pNode = NULL;

	if(pList == NULL){
		printf("NULL chk error\n");
		return;
	}
	//リストが空の場合はノードを生成
	if(pList->pTopNode == NULL){
		pList->pTopNode = initNode(data);
		if(pList->pTopNode == NULL){
			printf("push error\n");
		}
		printfList(pList);
		return;
	}
	
	pNode = pList->pTopNode;
	
	while(pNode->pNextNode != NULL){
		pNode = pNode->pNextNode;		
	};
	
	pNode->pNextNode = initNode(data);
	if(pNode->pNextNode == NULL){
		printf("push erro\n");
		return; 
	}
	
	printfList(pList);
	
	return;
}

void pop(list_t* pList){
	node_t* pPreNode = NULL;
	node_t* pNode = NULL;
	
	if(pList == NULL){
		printf("NULL chk error\n");
		return;
	}
	if(pList->pTopNode == NULL){
		printf("list empty\n");
		return;
	}
	
	pPreNode = pList->pTopNode;
	pNode = pList->pTopNode;
	
	while(pNode->pNextNode != NULL){
		pPreNode = pNode;
		pNode = pNode->pNextNode;
	}
	pPreNode->pNextNode = NULL;
	
	//リストが空になった場合の処理
	if(pNode == pList->pTopNode){
		pList->pTopNode = NULL;
		free(pNode);
		
		return;
	}
	free(pNode);		
	printfList(pList);

	return;
}

list_t* initList(int data){
	list_t* pList = NULL;
	
	pList = (list_t*)malloc(sizeof(list_t));
	if(pList == NULL){
		printf("init list malloc error\n");
		return NULL;
	}

	pList->pTopNode = initNode(data);
	if(pList->pTopNode == NULL){
		printf("init node error\n");
		free(pList);
		return NULL;
	}
	printfList(pList);
	
	return pList;
}

void deleteList(list_t* pList){
	node_t* pPreNode = NULL;
	node_t* pNode = NULL;
	
	if(pList == NULL){
		printf("NULL chk error\n");
		return;
	}

	pPreNode = pList->pTopNode;
	pNode = pList->pTopNode;
	
	while(pNode != NULL){
		pPreNode = pNode;
		pNode = pNode->pNextNode;
		free(pPreNode);
	}
	free(pList);
	
	return;
}

void deleteNodeData(list_t* pList, int data){
	node_t* pNode = NULL;
	node_t* pPreNode = NULL;
	node_t* pTmpNode = NULL;

	if(pList == NULL){
		printf("NULL chk error\n");
		return;
	}
	if(pList->pTopNode == NULL){
		printf("list empty\n");
		return;
	}
	pNode = pList->pTopNode;
	pPreNode = pNode;
	while(pNode != NULL){
		if(pNode->data == data){
			//ノードの張替え
			if(pNode == pList->pTopNode){
				pList->pTopNode = pNode->pNextNode;
			}else{
				pPreNode->pNextNode = pNode->pNextNode;
			}
			pTmpNode = pNode;
			pNode = pNode->pNextNode;
			free(pTmpNode);
		}else{
			pPreNode = pNode;
			pNode = pNode->pNextNode;
		}	
	}
	printfList(pList);
	
	return;
}

void deleteDupNode(list_t* pList){
	node_t* pNode_1 = NULL;
	node_t* pNode_2 = NULL;
	node_t* pPreNode_2 = NULL;
	node_t* pTmpNode = NULL;
	
	if(pList == NULL){
		printf("NULL chk error\n");
		return;
	}
	if(pList->pTopNode == NULL){
		printf("list empty\n");
		return;
	}
	
	pNode_1 = pList->pTopNode;
	pPreNode_2 = pNode_1;
	pNode_2 = pNode_1->pNextNode;

	
	while(pNode_1->pNextNode != NULL){
		while(pNode_2 != NULL){
			if(pNode_1->data == pNode_2->data){
				pPreNode_2->pNextNode = pNode_2->pNextNode;
				pTmpNode = pNode_2;
				pNode_2 = pNode_2->pNextNode;
				free(pTmpNode);
			}else{
				pPreNode_2 = pNode_2;
				pNode_2 = pNode_2->pNextNode;	
			}
		}
		pNode_1 = pNode_1->pNextNode;
		pPreNode_2 = pNode_1;
		//最終ノードが削除された場合は、pNode_1=NULLとなる
		//pNode_1->pNextNodeでfaultするのを回避
		if(pNode_1 == NULL){
			break;
		}else{
			pNode_2 = pNode_1->pNextNode;
		}
	}
	printfList(pList);
	
	return;	
}

int main(){
	list_t* pList = NULL;
	
	pList = initList(1);	
	push(pList,2);
	push(pList,3);
	pop(pList);
	push(pList,3);
	pop(pList);
	pop(pList);
	pop(pList);
	pop(pList);
	push(pList,1);
	push(pList,2);
	pop(pList);
	pop(pList);
	pop(pList);
	push(pList,1);
	push(pList,2);
	push(pList,3);
	deleteList(pList);
	
	pList = initList(1);	
	push(pList,2);
	pop(pList);
	pop(pList);
	pop(pList);
	deleteList(pList);
	
	pList = initList(1);	
	push(pList,1);
	push(pList,1);
	deleteDupNode(pList);
	pop(pList);
	pop(pList);
	pop(pList);
	push(pList,1);
	push(pList,1);
 	push(pList,2);
 	push(pList,2);
 	push(pList,3);
 	push(pList,3);
	deleteDupNode(pList);
	deleteList(pList);

	pList = initList(1);	
 	push(pList,1);
 	push(pList,2);
 	push(pList,3);
 	push(pList,1);
	push(pList,2);
 	push(pList,1); 
 	push(pList,1);	
	deleteNodeData(pList, 1);
	deleteList(pList);
			
	return 0;
}

下記が実行結果になります。

 $ gcc -o sample sample.c
 $ ./sample 
1 
1 2 
1 2 3 
1 2 
1 2 3 
1 2 
1 
list empty
1 
1 2 
1 
list empty
1 
1 2 
1 2 3 
1 
1 2 
1 
list empty
1 
1 1 
1 1 1 
1 
list empty
list empty
1 
1 1 
1 1 2 
1 1 2 2 
1 1 2 2 3 
1 1 2 2 3 3 
1 2 3 
1 
1 1 
1 1 2 
1 1 2 3 
1 1 2 3 1 
1 1 2 3 1 2 
1 1 2 3 1 2 1 
1 1 2 3 1 2 1 1 
2 3 2