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

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

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

下記の記事で、連結リスト(片方向)でpush/popを実装しています。
参考：連結リスト(片方向)でpushとpopをc言語で実装(サンプルコードあり)

まずは、双方向リストを構造体で定義します。
前後のノードへのポインタをメンバ変数に持つようにします。
リストの構造体には、先頭のノードのポインタをメンバ変数に定義します。。

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

typedef struct list{
	node_t* pTopNode;
}list_t;

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

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->pPreNode = NULL;
	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関数になります。
while()で終端ノードを探索します。
新規で作成したノードのポインタを、終端ノードのpNextNodeに格納します。
また、新規で追加したノードのpPreNodeに、終端ノードだったノードへのポインタを格納します。

void push(list_t* pList, int data){
	node_t* pNode = NULL;
	node_t* pNewNode = 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;		
	};
	
	pNewNode = initNode(data);
	if(pNewNode == NULL){
		printf("push erro\n");
		return; 
	}
	pNode->pNextNode = pNewNode;
	pNewNode->pPreNode = pNode;
	
	printfList(pList);
	
	return;
}

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

void pop(list_t* pList){
	node_t* pNode = NULL;
	
	if(pList == NULL){
		printf("NULL chk error\n");
		return;
	}
	if(pList->pTopNode == NULL){
		printf("list empty\n");
		return;
	}

	pNode = pList->pTopNode;
	while(pNode->pNextNode != NULL){
		pNode = pNode->pNextNode;
	}
	//リストが空になった場合の処理
	if(pNode == pList->pTopNode){
		pList->pTopNode = NULL;
		free(pNode);
		
		return;
	}
	pNode->pPreNode->pNextNode = NULL;

	free(pNode);		
	printfList(pList);

	return;
}

最後に、リストを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*	pPreNode;
	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->pPreNode = NULL;
	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;
}

void push(list_t* pList, int data){
	node_t* pNode = NULL;
	node_t* pNewNode = 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;		
	};
	
	pNewNode = initNode(data);
	if(pNewNode == NULL){
		printf("push erro\n");
		return; 
	}
	pNode->pNextNode = pNewNode;
	pNewNode->pPreNode = pNode;
	
	printfList(pList);
	
	return;
}

void pop(list_t* pList){
	node_t* pNode = NULL;
	
	if(pList == NULL){
		printf("NULL chk error\n");
		return;
	}
	if(pList->pTopNode == NULL){
		printf("list empty\n");
		return;
	}

	pNode = pList->pTopNode;
	while(pNode->pNextNode != NULL){
		pNode = pNode->pNextNode;
	}
	//リストが空になった場合の処理
	if(pNode == pList->pTopNode){
		pList->pTopNode = NULL;
		free(pNode);
		
		return;
	}
	pNode->pPreNode->pNextNode = NULL;

	free(pNode);		
	printfList(pList);

	return;
}

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;
}

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);
	
	return 0;
}

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

 $ gcc sample.c -o sample
 $ ./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