<뇌를 자극하는 알고리즘 #2>: 이중 연결 리스트(DLL) 퀴즈풀이

Vitamin Quiz

---

 문제) 더블 링크드 리스트를 역순으로 출력하는 함수를 작성해라. 원형은 다음과 같다.

void PrintReverse(Node *head);

풀이 // 이 글은 드래그 및 복붙이 안되므로, 최하단에 첨부한 문제풀이 소스코드를 따로 받아보시길 바랍니다.

---

/* 교재의 소스 코드 중, 문제풀이에 꼭 필요한 소스코드만 사용했습니다. 또한 데브맷이 임의적으로 변수의 이름과 함수의 이름을 재설정해줬습니다. 가독성과 의미를 고려한 결정이었습니다. 헤더파일 분할 없이 데브맷 풀이.c 에 코드를 담았으며 교재의 원본소스와 문제풀이 답안을 포함한 자체제작 소스 둘 다 최하단에 첨부해놨습니다. */

 

 맨 마지막에 정의되어 있는 printReverse 함수를 집중적으로 살펴보도록 하자. 나머지는 교재의 소스코드와 별반 차이가 없다. 핵심 개념 (오른쪽 끝의 노드에 접근했다가 다시 왼쪽 끝 노드로 옮겨가면서 데이터를 출력한다.)이 중요한 것이니까.

/*************************************************
 ** 이중 연결 리스트 (DDL Vitamin Quiz 문제풀이 포함 소스코드)
*************************************************/

#include <stdio.h>
#include <stdlib.h>

typedef int element;

typedef struct DNode {
	element data;
	struct DNode *prev, *next;
} DNode;

DNode* createDNode(element data);
void appendDNode(DNode **head, DNode *newNode);
DNode* getDNodeAt(DNode *head, int location);
void removeDNode(DNode **head, DNode *remove);
void insertAfter(DNode *current, DNode *newNode);
int getDNodeCount(DNode *head);
void printReverse(DNode *head);

void main()
{
	int i, count;
	DNode *list, *newNode, *current;

	i = count = 0;
	list = newNode = current = NULL;

	for (i = 0; i < 5; i++)
	{
		newNode = createDNode(i);
		appendDNode(&list, newNode);
	}
	count = getDNodeCount(list);
	for (i = 0; i < count; i++)
	{
		current = getDNodeAt(list, i);
		printf("list[%d]: %d\n", i, current->data);
	}
	
	// 역순으로 출력한다.
	printReverse(list);

	// 모든 노드를 메모리에서 제거
	printf("\ndelete list...\n");
	count = getDNodeCount(list);
	for (i = 0; i < count; i++)
	{
		// 맨 앞의 노드가 없어지고 새롭게 head노드가 갱신되는 원리를 사용
		current = getDNodeAt(list, 0);

		// 결국 마지막에 존재하던 노드까지 사라졌다면
		// getDNodeAt 의 반환 결과는 NULL일 것이다.
		if (current != NULL)
		{
			removeDNode(&list, current);
		}
	}
}

DNode* createDNode(element data)
{
	DNode *newDNode = (DNode *)malloc(sizeof(DNode));
	if (!newDNode) {
		fprintf(stderr, "동적할당오류");
		exit(EXIT_FAILURE);
	}
	newDNode->data = data;
	newDNode->prev = newDNode->next = NULL;

	return newDNode;
}

void appendDNode(DNode **head, DNode *newNode)
{
	if (*head == NULL) {
		*head = newNode;
	}
	else {
		DNode *tail = *head;
		while (tail->next != NULL)
			tail = tail->next;
		tail->next = newNode;
		newNode->prev = tail;
	}
}

DNode* getDNodeAt(DNode *head, int location)
{
	while (head->next != NULL && (--location) >= 0)
	{
		head = head->next;
	}
	return head;
}

void removeDNode(DNode **head, DNode *remove)
{
	if (*head == remove)
	{
		*head = (*head)->next;
		(*head)->prev == NULL;
	}
	else {
		remove->prev->next = remove->next;
		if(remove->next != NULL)
			remove->next->prev = remove->prev;
	}
	remove->prev = remove->next = NULL;
	free(remove);
}

void insertAfter(DNode *current, DNode *newNode)
{
	newNode->next = current->next;
	newNode->prev = current;
	
	if (current->next != NULL)
		current->next->prev = newNode;
	current->next = newNode;
}

int getDNodeCount(DNode *head)
{
	unsigned int count = 0;
	while (head != NULL)
	{
		count++;
		head = head->next;
	}
	return count;
}

void printReverse(DNode *head)
{
	printf("역순으로 출력을 시작합니다.\n");
	int index = 0;

	// 예외상황: 노드가 하나 뿐이었을 때
	if (head->next == NULL)
		printf("list[%d]: %d\n", index, head->data);
	
	// 정상: 노드가 2개 이상 존재할 때
	while (head->next != NULL) { // 노드의 끝까지 index를 더해가며 접근한다.
		index++;
		head = head->next;
	}

	// while문을 빠져나왔다면 성공적으로 마지막 노드에 접근을 한 것이다.
	if (head->next == NULL) {
		// 다시 첫 노드로 되돌아가는 작업을 하는데 이 때의 조건은 head != NULL 이다.
		while (head != NULL) {
			// 첫 노드의 전에노드는 NULL일 것이므로, 조건을 이렇게 줬다.

			printf("list[%d]: %d\n", index, head->data);
			head = head->prev; // 이전 노드로 이동한다.
			index--; // 인덱스 값을 하나씩 감소시킨다.
		}
	}
}

/*************************************************
 ** End Line
*************************************************/

DoublyLinkedList.zip

데브맷 풀이.c