<뇌를 자극하는 알고리즘 #1>: 단일 연결 리스트(SLL) 퀴즈풀이

Vitamin Quiz

---

 문제) SLL_insertAfter( ) 함수는 특정 '노드 뒤'에 새로운 노드를 삽입하는 기능을 수행한다. SLL_InsertNewHead( ) 함수는 '헤드 앞'에 새로운 헤드를 삽입할 수 있다. 그렇다면 특정 '노드 앞'에 새로운 노드를 삽입하는 SLL_InsertBefore( )함수도 존재할 것이다. 이 함수를 구현하라. 원형은 다음과 같다.

void SLL_InsertBefore( Node **Head, Node *Current, Node *NewHead );

 다음으로 링크드 리스트의 모든 노드를 한 번에 제거하는 SLL_DestroyAllNodes( ) 함수를 작성하라. 원형은 다음과 같다.

SLL_DestroyAllNodes( Nodes **List );

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

---

/* 교재의 소스 코드 중, 문제풀이에 꼭 필요한 소스코드만 가져다 썼습니다. 전부 다 쓰기엔 가독성도 떨어지고, 문제풀이에 크게 도움이 되지 않습니다. 또한 실제 소스는 헤더파일을 따로 만들어줬지만 문제풀이에서는 하나의 .c파일에 담았습니다. 또한 교재의 소스코드에 사용된 변수와 함수 이름을 가독성을 위해 다소 줄였습니다. 교재의 원본 소스가 궁금하신 분들은 아래 첨부해놨으니 가져가 보시면 되겠습니다. */

/*************************************************
 ** 단일 연결리스트 (Single Linked List) Vitamin Quiz
*************************************************/

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

typedef int element;

typedef struct Node {
	element data;
	struct Node *link;
} Node;

Node* createNode(element data); // 동적할당을 이용해 새로운 노드를 생성한다.
void appendNode(Node **head, Node *newNode); // createNode를 통해 생성된 노드를 리스트에 연결한다.
Node* getNodeAt(Node *head, int location); // 원하는 인덱스의 노드 주소를 반환하는 함수다.
int getNodeCount(Node *head); // list에 현재 존재하는 노드가 몇 개인지 계산해준다.

// current가 가리키는 노드의 바로 직전에 새로 생성된 newHead 노드를 연결해준다.
void insertBefore(Node **head, Node *current, Node *newHead); 
// list의 모든 노드를 삭제한다.
void deleteAllNodes(Node **list);

void main()
{
	int i = 0; // 반복문을 위한 변수 i
	int count = 0; // 노드의 수를 저장하기 위한 카운터 변수
	Node *list, *current, *newNode;

	// 포인터 변수는 항상 NULL로 초기화 시켜두는 것이 안전한다.
	list = current = newNode = NULL; // 변수 초기화

	// 5개의 노드를 새로 생성하여 list를 구성한다.
	for (i = 0; i < 5; i++)
	{	// i 값을 가지는 노드를 동적할당으로 새로 생성한다.
		// 동적할당된 노드의 주솟값을 newNode에 저장한다.
		newNode = createNode(i);
		// 새로 생성된 노드 newNode를 list에 연결해준다.
		appendNode(&list, newNode);
	}

	count = getNodeCount(list);
	for (i = 0; i < count; i++)
	{
		// 리스트의 i번째에 해당하는 노드의 주솟값을 current에 저장한다.
		current = getNodeAt(list, i);
		// i번째에 해당하는 노드에 대한 포인터 current로 해당 노드의 정보를 확인한다.
		printf("list[%d]: %d\n", i, current->data);
	}

	// inputBefore 함수를 본격적으로 테스트해본다.
	printf("\nTest inputBefore()...\n");

	// 먼저 삭제를 원하는 위치의 노드 주소를 current에 저장한다.
	while (1) { // 사용자의 오류를 방지하기 위해 만들어진 루프
		printf("\nInput node index what you want to find\n");
		printf("\n입력한 위치 바로 전에 새로운 노드가 삽입됩니다.\n");

		scanf("%d", &i);
		current = getNodeAt(list, i);
		// 사용자가 잘못된 위치를 얻으려 했다면 current값은 NULL이 될 것이다.

		if (current != NULL) // 만약 NULL이라면 루프를 빠져나가지 못하고 반복한다.
			break;
	}

	// 새로 삽입할 newNode를 만든다. 정수 2500을 갖고 있는 노드다.
	newNode = createNode(2500);

	// 위에서 입력한 원하는 위치의 바로 직전에 newNode를 삽입한다.
	insertBefore(&list, current, newNode);

	// 제대로 잘 삽입이 되었는지 for문을 이용해 모든 리스트의 노드를 출력해본다.
	count = getNodeCount(list);
	for (i = 0; i < count; i++)
	{
		current = getNodeAt(list, i);
		printf("list[%d]: %d\n", i, current->data);
	}

	printf("\nTest deleteAllNodes()...\n");
	deleteAllNodes(&list);
}

Node* createNode(element data)
{
	Node *newNode = (Node *)malloc(sizeof(Node));
	if (!newNode) // if(newNode == NULL)과 동일, 동적할당 실패시
	{
		fprintf(stderr, "동적할당 실패\n");
		exit(EXIT_FAILURE); // 프로그램을 종료해버린다.
	}
	// 새로운 노드의 정보 입력 및 리턴
	newNode->data = data;
	newNode->link = NULL;
	return newNode;
}

void appendNode(Node **head, Node *newNode)
{
	if ((*head) == NULL) // 헤드노드가 없다는 건 리스트가 아예 비어있었다는 뜻이다.
		// 비어 있는 리스트이므로, 새로 생성된 노드가 헤드노드가 된다.
		*head = newNode;
	else
	{ // 비어 있는 노드가 아니었다면
		Node *tail = (*head); // 헤드노드를 가리키는 tail 포인터변수
		// 아래의 while 조건문으로 제일 마지막에 연결되어 있는 노드로 이동
		while (tail->link != NULL)
		{
			tail = tail->link;
		}
		// 제일 마지막에 있었던 노드의 다음 노드가 newNode를 가리키게끔 변경
		tail->link = newNode;
	}
}

Node* getNodeAt(Node *head, int location)
{
	Node *current = head;
	while (current != NULL && (--location) >= 0)
	{
		current = current->link;
	}
	// 만약 location이 list를 넘어서는 범위였다면 current은 NULL이 될 것이다.
	return current;
}

int getNodeCount(Node *head)
{
	int count = 0;
	Node *current = head;

	while (current != NULL)
	{
		// 존재하는 노드가 있을 때마다 +1 카운트
		count++;
		current = current->link;
	}

	return count;
}

void insertBefore(Node **head, Node *current, Node *newHead)
{
	// current에 위치한 노드의 바로 전에 newHead가 가리키는 노드를 삽입한다.
	// 그러기 위해선 포인터 변수가 두 개가 필요하다.

	// 전에 있는 노드를 가리키기 위한 prev 포인터
	// 당연히 처음에 있는 노드의 전 노드는 없으므로 초기값은 NULL이다.
	Node *prev = NULL;

	// 현재의 노드를 가리키기 위한 now 포인터
	// 초기값은 가장 선두에 있는 head노드다.
	Node *now = *head;

	/* 예외처리가 가장 중요하다. 어떤 상황에서 예외가 발생하는지를 생각해보자. */

	// 예외상황 1: 헤드노드가 없었을 때
	if (now == NULL) {
		// 사용자가 잘못 사용한 경우다. 원하는 위치 전에 삽입해야 하는데
		// 원하는 위치 자체가 존재하지 않는다. 아무것도 없는 list이기 때문에.
		fprintf(stderr, "잘못 사용하셨습니다. 비어있는 리스트입니다.\n");
		return;
	}

	// 예외상황 2: 헤드노드만 있을 때
	else if (now->link == NULL) {
		if (now == current) { // 헤드노드가 사용자가 찾는 노드였다면
			newHead->link = *head; // 새로운 노드가 새로운 헤드가 된다.
			*head = newHead;
			return; // 목적을 달성했으므로 리턴
		}
	}

	// 나머지 상황: 노드가 2개 이상 존재할 때

	// 리스트의 처음부터 끝까지 while문을 통해 접근한다.
	while (now->link != NULL)
	{
		// 예외상황2를 통과하여 여기로 왔다는 것은 일단 헤드노드는
		// 내가 찾던 노드가 아니라는 뜻이므로, prev와 now를 갱신해준다.
		prev = now; // 새롭게 정의된 prev
		now = now->link; // now는 다음 노드를 가리키게 변경
		
		// 만약 내가 찾던 노드가 now가 맞다면 while문 탈출
		if (now == current)
			break;
	}

	// while문을 빠져나왔다는 건 내가 찾던 노드의 주소가 now에 저장되어 있다는 의미다.
	// 찾던 노드가 없을 경우는 이 함수내에서 있을 수 없다. 이미 함수를 사용하기 전 사전작업으로
	// 꼭 존재하는 노드에 대해서만 이 함수를 사용할 수 있게끔 해놨기 때문이다.

	// 새로 생성된 노드 newHead를 now 전에 삽입해주는 작업을 진행한다.
	newHead->link = now;
	// now 전에 있던 prev의 다음에 연결되야 하므로 아래 작업을 처리한다.
	prev->link = newHead;
}

void deleteAllNodes(Node **list)
{
	// 현재 노드 위치를 가리키는 current 포인터 변수
	Node *current = *list;

	// 다음 노드 위치를 가리킬 next 포인터 변수
	Node *next = current->link;
	// 이 변수가 필요한 이유는 현재노드를 가리키는 포인터가 반납되버리면
	// 다음 노드를 current->link로 사용할 수 없기 때문이다.

	/* 예외상황 1: 노드가 하나만 존재했을 때 */
	if (next == NULL)
	{
		// 존재하는 하나의 노드만 삭제하고 바로 리턴
		free(current); 
		return;
	}

	// 정상상황: 노드가 2개 이상 존재할 때
	while (next != NULL) // 노드의 끝까지 while문 반복
	{
		free(current); // 현재노드를 반납한다.
		current = next; // 현재노드는 이제 다음노드가 된다.
		next = next->link; // 마찬가지로 다음노드는 다다음 노드가 된다.
	}

	// 반복문을 빠져 나왔으면, 현재 노드의 다음 노드는 존재하지 않는 상황이다.
	// 따라서 마지막 노드인 현재 노드를 반납해주면 모든 반납이 완료된다.
	free(current);
}

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

/* deleteAllNodes( )의 경우 테스트 방법은 디버깅으로 직접 확인해보는 방법이 있습니다. 왜냐하면 실행 후에 list는 이미 온데 간데 없을것이므로 접근자체도 안되고, 그 안의 정보를 알아내는 방법또한 없습니다. */

LinkedList.zip

데브맷 풀이.c