Chapter 04. 단순 연결 리스트의 ADT(추상 자료형)와 구현(2)

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

다음은 노드를 표현한 구조체의 정의입니다. 그리고 연결 리스트의 구현에서 이는 결코 빠지지 않습니다.

typedef struct Node
{
	LData data;
	struct Node* nest;
} Node;

그런데 연결 리스트의 구현에 필요한 다음 유형의 변수들은 별도의 구조체로 묶이지 않고 그냥 main 함수의 지역변수로 선언하기도 하고, 더 나쁜 경우에는 전역 변수로 선언하기도 합니다.

Node* head;
Node* cur;

위 유형의 포인터 변수들은 전역 변수로도, main 함수의 지역변수로도 선언해서는 절대 안 됩니다. 그 이유는 다음과 같습니다.

연결 리스트를 여러 개 구현해야 하는 경우를 예로 들어보겠습니다. 만약 head와 cur를 main함수의 지역변수로 선언한다면 다른 연결 리스트를 구현할 때마다 다음과 같이 변수를 선언해야 할 것입니다.

int main(void)
{
	Node* head1, * cur1;
	Node* head2, * cur2;
	Node* head3, * cur3;
	...
	return 0;
}

물론 이것이 이유의 전부는 아니지만 위 예시만으로도 이유를 충분히 깨달았을 것으로 생각됩니다. 따라서 head와 cur과 같은 포인터 변수를 묶어서 다음과 같이 연결 리스트를 의미하는 구조체를 별도로 정의해야 합니다.

typedef struct LinkedList
{
	Node* head;
	Node* cur;
	Node* before;
	int numOfData;
	int (*comp)(LData d1, LData d2);
} LinkedList;

여기서 before와 comp의 역할이 궁금할 텐데 이는 연결 리스트의 구현을 보이면서 소개하겠습니다. 이제 우리가 구현할 헤더 파일을 소개합니다.

//DLickedList.h 헤더 파일로 저장
#ifndef D_LINKEDLIST_H
#define D_LINKEDLIST_H

#define TRUE 1
#define FALSE 0

typedef int LData;

typedef struct Node
{
	LData data;
	struct Node* next;
} Node;

typedef struct LinkedList
{
	Node* head;
	Node* cur;
	Node* before;
	int numOfData;
	int (*comp)(LData d1, LData d2);
} LinkedList;

typedef LinkedList List;

void ListInit(List* plist);
void LInsert(List* plist, LData data);
int LFirst(List* plist, LData* pdata);
int LNext(List* plist, LData* pdata);
LData LRemove(List* plist);
int LCount(List* plist);
void SetSortRule(List* plist, int (*comp)(LData d1, LData d2));

#endif

 

 

지금부터는 위 헤더 파일을 기반으로, ListInit부터 SetSortRule까지의 함수들을 구현해 봅니다.

 

다음은 연결 리스트를 표현한 구조체의 정의입니다. 연결 리스트를 생성하기 원한다면 다음 구조체의 변수를 하나 선언하거나 동적으로 할당하면 됩니다. 이후부터는 다음 구조체의 변수를 가리켜 그냥 '리스트'라고 하겠습니다

typedef struct LinkedList
{
	Node* head;
	Node* cur;
	Node* before;
	int numOfData;
	int (*comp)(LData d1, LData d2);
} LinkedList;

위 구조체의 변수가 선언되면 이를 대상으로 초기화를 진행해야 하는데, 이때 호출되는 함수는 다음과 같습니다.

void ListInit(List* plist)
{
	plist->head = (Node*)malloc(sizeof(Node));
	plist->heat->next = NULL;
	plist->comp = NULL;
	plist->numOfData = 0;
}

더미 노드를 생성해서 head 포인터가 가리키도록 했고, 더미 노드의 next에는 NULL포인터를 저장했습니다.

그리고 comp는 함수 포인터입니다. 우선은 이 포인터 또한 NULL포인터로 저장하고, 현재 리스트에 저장된 데이터가 없으므로 numOfData도 0으로 초기화했습니다.

 

이제 위의 상황에서 노드의 추가를 위해 호출되는 함수는 다음과 같습니다.

void LInsert(List* plist, LData data)
{
	if (plist->comp == NULL) FInsert(plist, data);    //정렬기준이 마련되지 않았다면 머리에 노드 추가
	else SInsert(plist, data);                        //정렬 기준이 마련되었다면 정렬 기준에 근거하여 노드 추가
}

위의 함수에서 보이듯이 노드의 추가는 리스트의 멤버 comp에 무엇이 저장되어 있느냐에 따라서 FInsert 또는 SInsert 함수를 통해 진행됩니다. 그런데 이 두 함수 모두 헤더 파일에 선언된 함수가 아닙니다. 이들 함수는 리스트 내부적으로 호출이 되도록 정의된 함수들이기 때문에 프로그래머가 직접 호출할 수는 없습니다. 먼저 FInsert 함수를 보겠습니다.

void FInsert(List* plist, LData data)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	newNode->next = plist->head->next;
	plist->head->next = newNode;

	plist->numOfData++;
}

위 함수를 이해하는 데에는 어려움이 없습니다. 혹여 이해가 어렵다면 언제든지 질문 바랍니다. 

 

SInsert 함수에 대한 설명은 아직 나오지 않았습니다. 나중에 이 함수에 대한 설명도 나올 것으로 보입니다.

---

이제 리스트에 저장된 데이터를 조회하는 기능을 구현해 보겠습니다. 조회와 관련된 함수는 LFirst와 LNext 함수입니다. 먼저 LFirst 함수를 보겠습니다.

int LFirst(List* plist, LData* pdata)
{
	if (plist->head->next == NULL) return FALSE;
	
	plist->before = plist->head;
	plist->cur = plist->head->next;

	*pdata = plist->cur->data;

	return TRUE;
}

위 함수를 이해하는 데는 어려움은 없을 것입니다. 다만, before가 무엇에 쓰이는지 궁금하실 겁니다. cur 포인터 변수는 참조할 노드를 가리키고, before 포인터 변수는 현재 참조하는 노드의 앞에 있는 노드를 가리킵니다. before 포인터 변수는 삭제와 관련해서 쓰임이 있습니다. 

 

배열 기반 리스트를 구현했을 때를 생각해 보겠습니다. 배열 기반 리스트에서, 데이터의 삭제가 이뤄지기 전에 LFirst함수나 LNext함수를 통해서 참조가 먼저 이루어졌던 것을 기억할 것입니다. 그리고 데이터를 삭제하면 그 다음 데이터를 앞으로 복사해서 가져와서 리스트를 쭉 연결했던 것을 기억할 것입니다.

 

연결 리스트의 경우도 마찬가지입니다. LFirst함수나 LNext함수로 먼저 위치를 참조하고, cur이 가리키는 노드를 삭제할 것입니다. 그렇게 cur 노드를 삭제하면 그 이전의 노드들과 그 이후의 노드들이 분리가 되게 됩니다. 이들을 다시 연결시키기 위해 before 노드를 활용합니다. 따라서 before 노드의 next에 cur의 next를 저장한 후 cur을 삭제하는 방식으로 데이터의 삭제가 이루어질 것으로 예상합니다.

 

다음은 LNext함수입니다.

int LNext(List* plist, LData* pdata)
{
	if (plist->cur->next == NULL) return FALSE;

	plist->before = plist->cur;
	plist->cur = plist->cur->next;

	*pdata = plist->cur->data;

	return TRUE;
}

LNext함수는 LFirst 함수와 매우 유사하기 때문에 LFirst함수를 이해했다면, LNext함수도 이해하기 쉬울 것입니다. 

---

이제 데이터의 삭제와 관련한 LRemove 함수의 구현입니다.

LData LRemove(List* plist)
{
	Node* delNode = plist->cur;
	LData delNodeData = delNode->data;

	plist->before->next = plist->cur->next;
	plist->cur = plist->before;

	free(delNode);
	plist->numOfData--;

	return delNodeData;
}

위 함수를 보면 cur 노드를 삭제하기에 앞서 cur의 위치를 before와 동일하게 한 후 삭제처리를 하고 있습니다. 즉, cur의 위치를 한 칸 앞으로 당긴 것입니다. 이는 배열 기반 리스트에서 했던 것과 같습니다. 그런데 cur의 위치를 한 칸 앞으로 당기고 나니 cur와 before의 위치가 같게 되었습니다. before의 위치도 한 칸 앞으로 당겨야 할 것 같지만, 그러기가 까다로울뿐더러 굳이 그러지 않아도 됩니다. 왜냐하면 다음번 참조를 위해 Lfirst나 LNext함수를 호출하게 되면 저절로 위치가 조정될 것이기 때문입니다.

---

아직 SInsert함수나 SetSortRule 함수에 대해서는 설명하지 않았지만 지금까지 설명한 내용으로도 연결 리스트를 충분히 구현할 수 있으므로 이를 바탕으로 구현해 보도록 하겠습니다.

//DLickedList.h 헤더 파일로 저장
#ifndef D_LINKEDLIST_H
#define D_LINKEDLIST_H

#define TRUE 1
#define FALSE 0

typedef int LData;

typedef struct Node
{
	LData data;
	struct Node* next;
} Node;

typedef struct LinkedList
{
	Node* head;
	Node* cur;
	Node* before;
	int numOfData;
	int (*comp)(LData d1, LData d2);
} LinkedList;

typedef LinkedList List;

void ListInit(List* plist);
void LInsert(List* plist, LData data);
int LFirst(List* plist, LData* pdata);
int LNext(List* plist, LData* pdata);
LData LRemove(List* plist);
int LCount(List* plist);
void SetSortRule(List* plist, int (*comp)(LData d1, LData d2));

#endif

//DLinkedList.c 소스 파일로 저장
#include "DLickedList.h"
#include <stdio.h>
#include <stdlib.h>

void ListInit(List* plist)
{
	plist->head = (Node*)malloc(sizeof(Node));
	plist->head->next = NULL;
	plist->comp = NULL;
	plist->numOfData = 0;
}
void FInsert(List* plist, LData data)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	newNode->next = plist->head->next;
	plist->head->next = newNode;

	plist->numOfData++;
}
void SInsert(List* plist, LData data)
{
	//잠시 후 설명합니다.
}
void LInsert(List* plist, LData data)
{
	if (plist->comp == NULL) FInsert(plist, data);
	else SInsert(plist, data);
}
int LFirst(List* plist, LData* pdata)
{
	if (plist->head->next == NULL) return FALSE;
	
	plist->before = plist->head;
	plist->cur = plist->head->next;

	*pdata = plist->cur->data;

	return TRUE;
}
int LNext(List* plist, LData* pdata)
{
	if (plist->cur->next == NULL) return FALSE;

	plist->before = plist->cur;
	plist->cur = plist->cur->next;

	*pdata = plist->cur->data;

	return TRUE;
}
LData LRemove(List* plist)
{
	Node* delNode = plist->cur;
	LData delNodeData = delNode->data;

	plist->before->next = plist->cur->next;
	plist->cur = plist->before;

	free(delNode);
	plist->numOfData--;

	return delNodeData;
}
int LCount(List* plist)
{
	return plist->numOfData;
}
void SetSortRule(List* plist, int (*comp)(LData d1, LData d2));

//main.c 소스 파일로 저장
#include <stdio.h>
#include "DLickedList.h"

int main(void)
{
	//리스트의 생성 및 초기화
	List list;
	int data;
	ListInit(&list);

	//5개의 데이터 저장
	LInsert(&list, 11); LInsert(&list, 11);
	LInsert(&list, 22); LInsert(&list, 22);
	LInsert(&list, 33);

	//저장된 데이터의 전체 출력
	printf("현재 데이터의 수 : %d\n", LCount(&list));

	if (LFirst(&list, &data))
	{
		printf("%d ", data);
		while (LNext(&list, &data))
		{
			printf("%d ", data);
		}
	}
	printf("\n\n");

	//숫자 22를 검색하여 모두 삭제
	if (LFirst(&list, &data))
	{
		if (data == 22) LRemove(&list);

		while (LNext(&list, &data))
		{
			if (data == 22) LRemove(&list);
		}
	}

	//삭제 후 남아 있는 데이터 전체 출력
	printf("현재 데이터의 수 : %d\n", LCount(&list));

	if (LFirst(&list, &data))
	{
		printf("%d ", data);
		while (LNext(&list, &data))
		{
			printf("%d ", data);
		}
	}
	printf("\n\n");

	return 0;
}

/*
실행결과

현재 데이터의 수 : 5
33 22 22 11 11

현재 데이터의 수 : 3
33 11 11

*/

위 main함수를 보면 배열 기반 리스트를 구현할 때 사용한 것과 동일합니다. 즉, 우리가 구현한 두 리스트 자료구조는 소스코드의 변경 없이도 대체가 가능합니다.

 

아직 더미 기반 연결 리스트의 모든 설명이 끝난 것은 아닙니다. 이어서 정렬과 관련된 설명이 이어집니다.