CH4단순 연결 리스트의 ADT와 구현(3)

04-2. 단순 연결 리스트의 ADT와 구현 ③

우리는 이제 더미노드가 있는 경우의 연결리스트를 살펴볼 것임.

Untitled

기존의 예제에서 head는 항상 첫번째 노드를 가리키는 의미를 가리키고 있다. 그리고 달리말하면, 첫번째 노드의 주소는 head 라는 구조체 포인터 변수에 저장되어야 한다.

이렇게 분리된 녀석때문에 앞서 본 예제코드에서 출력이나 삭제 시 분기문을 이용해 head를 따로 탐색해야 했어야 한다. 이런 과정을 없애보자. 즉 모든 노드의 처리과정을 동일하게 만들자.

이는 더미노드 기반 연결리스트를 통해 가능하다.

기본 개념은, 항상 첫번째 노드를 깍두기로 두는 것이다. 첫번째 노드에는 유효데이터를 두지 않고, 두번째 노드부터 유효데이터를 둔다.

분기문을 통해 따로 관리해야 했던 첫번째 데이터를 더미노드로 두면, 유효한 활동은 항상 두번째 노드부터 이루어지므로, 분기문 등을 통해 첫 노드를 관리할 필요가 없어진다.

따라서 모든 노드를 일관적인 방식으로 관리할 수 있다.

저자에 따르면, 이런 방식이 연결리스트의 표준에 가깝다. optional한 게 아님.

문제 4-2를 풀어보자.

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

typedef struct _node
{
	int data;
	struct _node * next;
} Node;

int main(void)
{
	Node* tail = NULL;  // NULL 포인터 초기화
	Node* cur = NULL;
	Node* newNode = NULL;

	**Node DMY =
	{ -1,NULL };
	Node * head = &DMY;  // head 더미로 초기화**
	
	int readData;

	/**** 데이터를 입력 받는 과정 ****/
	while(1)
	{
		printf("자연수 입력: ");
		scanf("%d", &readData);
		if(readData < 1)
			break;

		/*** 노드의 추가과정 ***/
		newNode = (Node*)malloc(sizeof(Node));
		newNode->data = readData;
		newNode->next = NULL;

		if (head->next == NULL)
			head->next = newNode;
		else
		{
			tail->next = newNode; //그림에서 화살표의 방향 설정
		}
		tail = newNode; //노드가 늘어나는 방향 설정
	}
	printf("\\n");

	/**** 입력 받은 데이터의 출력과정 ****/
	printf("입력 받은 데이터의 전체출력! \\n");
	if(tail == NULL) 
	{
		printf("저장된 자연수가 존재하지 않습니다. \\n");
	}
	else 
	{
		cur = head;

		while(cur->next != NULL)    // 더미 이후의 데이터 출력
		{
			cur = cur->next;
			printf("%d  ", cur->data);
		}
	}
	printf("\\n\\n");

	/**** 메모리의 해제과정 ****/
	if(tail == NULL) 
	{
		return 0;    // 해제할 노드가 존재하지 않는다.
	}
	else 
	{
		Node * delNode = head;
		Node * delNextNode = head->next;
		
		while(delNextNode != NULL)    // 더미 이후의 노드 삭제 위한 반복문
		{
			
			delNode = delNextNode;
			delNextNode = delNextNode->next; 

			printf("%d을(를) 삭제합니다. \\n", delNode->data);
			free(delNode);    // 두 번째 이후의 노드 삭제
		}
	}

	return 0;
}

원래 코드와 더미가 존재하는 연결리스트 코드의 차이를 살펴보자.

  1. 초기화

Untitled

Untitled