[C] Double Linked List 구현

https://github.com/DJmong/Data-Structure/tree/master/doubleLinkedList

 

프로그램 실행

코드 전문

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#define TRUE 1
#define FALSE 0
//#define _DEBUG_

typedef struct data{
	char szName[128];
	int iValue;
	struct data *prev;
	struct data *next;
}DATA;

DATA* nextList(const DATA *node);
void addList(DATA *node);
void delList(DATA **node);
DATA *prevList(const DATA *node);
void insertData(DATA *node);
void drawList(DATA *root, DATA *now);

int main(int argc, char **argv){
	int iNeedDel = TRUE;
	system("clear"); // 화면 초기화용
	DATA *root = malloc(sizeof(DATA)); // 루트 노드 값
	memset(root, 0, sizeof(DATA));
	char cInput = 0; // 입력 값 확인 용
	DATA *nowNode = root; // 현재 노드 값
	while(cInput != 'x'){
		drawList(root, nowNode);
		DATA *travel = 0; // 탐색용 노드
		printf("Please Insert command!\n");
		printf("1. n - go to next list\n");
		printf("2. p - go to prev list\n");
		printf("3. d - delete list \n");
		printf("4. a - add list \n");
		printf("5. i - insert data \n");
		printf("6. x - exit\n");
		scanf("%c", &cInput);
		switch(cInput){
			case 'n': // 다음 노드로
				travel = nextList(nowNode);
				if(travel != NULL) nowNode = travel;
				break;
			case 'p': // 이전 노드로
				travel = prevList(nowNode);
				if(travel != NULL) nowNode = travel;
				break;
			case 'd': // 노드 삭제
				travel = nowNode; // 탐색 노드로 현재 노드 이동
				delList(&nowNode); // 현재 노드 제거
				if(travel == root){ // 제거한 노드가 루트 노드일 경우 루트 노드 업데이트
					root = nowNode;
				}
				if(nowNode == NULL){ // 마지막 노드가 제거된 경우 종료
					printf("root node is deleted!\n");
					cInput = 'x';
					iNeedDel = FALSE;
				}
				break;
			case 'a':
				addList(nowNode); // 노드 추가
				break;
			case 'i':
				insertData(nowNode); // 데이터 입력
				break;
			case 'x': // 종료
				printf("good Bye!\n");
				break;
		}
		system("clear");
	}

	while(1){ // 할당된 데이터가 전부다 해제되지 않았을 경우 할당 해제해줌
		if(iNeedDel == FALSE) break; 
		if(root->next != NULL){
			delList(&root->next);
		}
		else{
			delList(&root);
			break;
		}
	}
	
}

// 다음 리스트 탐색 후 존재할 경우 리턴
DATA* nextList(const DATA *node){
	if(node->next == NULL){
		printf("%p is end list\n", node);
		return 0;
	}
#ifdef _DEBUG_
	printf("travle to %p\n", node->next);
#endif
	return node->next;
}

// 다음 노드에 새 리스트 추가
void addList(DATA *node){
	DATA *newList = malloc(sizeof(DATA));
	memset(newList, 0, sizeof(DATA));
	DATA *right = node->next;
	if(right != NULL){
		newList->next = right;
		right->prev = newList;
	}
	newList->prev = node;
	node->next = newList;
}

// 현재 리스트 제거 및 노드가 남아있을 경우 현재 노드를 변경해줌
void delList(DATA **node){ // 포인터 값을 변경해야 하므로 이중 포인터 써야함
	if(*node == NULL){
		printf("%p is already empty!\n", node);
		return;
	}
	DATA *left = (*node)->prev;
	DATA *right = (*node)->next;
	if(left == NULL){
		if(right == NULL){
			printf("root node %p is deleted\n", *node);
			DATA *temp = *node;
			free(temp);
			*node = NULL; // 댕글링 포인터 방지
			return;
		}
		printf("left empty, right exist case\n");
		right->prev = NULL; // 댕글링 포인터 방지
		DATA *temp = *node;
		*node = right;
		free(temp);
		return;
	}
	if(right == NULL){
		left->next = NULL;
		DATA *temp = *node;
		*node = left;
		free(temp);
		temp = NULL; // 댕글링 포인터 방지
		return;
	}
	left->next = right;
	right->prev = left;
	DATA *temp = *node;
	*node = left;
	free(temp);
	temp = NULL; // 댕글링 포인터 방지
	
	return;
}

// 이전 리스트 탐색 후 있을 경우 이동
DATA *prevList(const DATA *node){
	if(node->prev == NULL){
		printf("%p is root list\n", node);
		return 0;
	}
	return node->prev;
}

// 현재 노드에 데이터 입력
void insertData(DATA *node){
	if(node == NULL){
		printf("ERROR! %p is invalid!\n", node);
		return;
	}
	printf("Please input the string\n");
	scanf("%s", node->szName);
	printf("Please input the value\n");
	scanf("%d", &node->iValue);
}

// 전체 리스트 탐색 후 이를 그려줌
void drawList(DATA *root, DATA *now){
	int iIndex = 1;
	DATA *travel = root;
	while(1){
		printf("-------------------------\n");
		if(travel == now) printf("| %d. <<<\t\t|\n", iIndex++);
		else printf("| %d. \t\t\t|\n",iIndex++);
		printf("| Name  : %-10s\t|\n", travel->szName);
		printf("| Value : %-4d\t\t|\n", travel->iValue);
		printf("-------------------------\n");
		DATA *next = nextList(travel);
		if(next == NULL) break;
		printf("%10s\n", "| |");
		travel = next;
	}
}

코드가 좀 긴데,

 

함수 이름만 봐도 최대한 알아먹을 수 있도록 짜놨으니 함수 선언만 봐도 괜찮을 듯?

 

구현하는데 걸린 시간은 3시간 정도인데

1시간 정도는 delList의 이중 포인터 때문에 막힌 듯

 

이전에 구현했을 때는 이중포인터로 잘 처리 했었는데

 

오랜만에 만들어보니 이중포인터 써야한다는 것도 까먹고

댕글링 포인터 때문에 참조 에러 나서 gdb로 디버깅하고 난리였다.

 

댕글링 포인터 방지를 위해 free 이후에 반드시 포인터 주소 초기화까지 진행해줘야 할 듯

 

시간나면 힙이나 트리도 구현해보고 싶은데

 

힙 정리 알고리즘은 도저히 엄두가 안난다.

 

트리부터 잘 구현해봐야지