연결 리스트

노드의 데이터 구조

typedef struct tagNode
{
    int Data;
    Node* NextNode;
} Node;

데이터와 다음 노드의 주소가 필요하다.

 

노드를 이어붙이면 연결 리스트가 된다.

 

따라서 노드의 생성, 리스트에 추가, 리스트에서 삭제, 노드 검색정도의 기능을 구현해 보았다.

 

Node* CreateNode((void*) NewData)
{
	Node* temp = (Node*)malloc(sizeof(Node));

	temp->Data = NewData;
	temp->NextNode = NULL;

	return temp;
}

void AppendNode(Node** Head, Node* NewNode)
{
	Node* temp = (*Head);

	if (temp == NULL) {
		(*Head) = NewNode;
	}
	else {
    	// 마지막 노드 찾기
		while (temp->NextNode) {
        	// 다음 노드로 이동
			temp = temp->NextNode;
		}				
        // 빠져나오면 temp는 마지막 노드
        // temp의 다음 노드는 생성된 노드
		temp->NextNode = NewNode;	
	}
}

노드의 생성은 노드를 담을 메모리를 확보하고, 노드의 데이터들을 초기화하고 리턴한다.

 

생성된 노드는 리스트에 추가할 때는 리스트에 노드가 있는지 체크한 뒤, 없으면 헤드에 생선된 노드를 가르키게 한다.

 

만약 리스트에 이미 노드가 있다면 리스트의 마지막 노드를 찾아간 뒤, 마지막 노드의 다음 노드를 가르키는 데이터에 생성된 노드를 입력한다.   

 

노드를 생성하고 리스트에 추가하는 코드가 이해되면 제거와 검색은 간단하다.

void RemoveNode(Node** Head, int Data)
{
	Node* temp = (*Head);
	Node* temp1 = NULL;

	if ((*Head) == NULL) {
		printf("No Data\n");
		return;
	}
	else if (temp->Data == Data) {
		(*Head) = temp->NextNode;
		return;
	}
	else {
		while (temp) {
			temp1 = temp;
			temp = temp->NextNode;
			if (temp != NULL) {
				if (temp->Data == Data)
					break;
			}
		}
		if (temp == NULL) {
			printf("No Data\n");
		}
		else {
			temp1->NextNode = temp->NextNode;
			free(temp);
		}
	}
}

void SerachNode(Node* Head) {
	Node* temp = Head;
	int i = 1;

	if (temp == NULL) {
		printf("No Data !!\n");
		return;
	}

	while (temp) {
		printf("Node [%d] : %d\n", i++, temp->Data);
		temp = temp->NextNode;
	}
}