링크드 리스트 (Linked List)

자료구조하면 정말 처음 나오지만, 참 중요한 링크드 리스트이다. 수업 시간 때 거진 이론만 배우고, 대충 이해하고 말아 아쉬운 부분이 있었는데, 이번에 윤성우씨 책으로 나름대로? 공부하고 있는 것 같다.

Linked List하면 이 그림이 제일 먼저 기억 날 것이다. 

Node로 구성된 자료구조가 연결되어있는 구조이다.

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

노드는 다음과 같이 구성되어 있다.

1. 데이터

2. 다음 노드 포인터 

이 노드 포인터가 참 재밌는 역할을 한다. 

 

ADT는 다음과 같다.

void ListInit(List * plist);
void LInsert(List * plist, LData data);

int LFirst(List *plist, LData *pdata);
int LNext(List *plist, LData *pdata);

void FInsert(List *plist, LData data);
void SInsert(List *plist, LData data);

LData LRemove(List *plist);
int LCount(List *plist);

void SetSortRule(List *plist, int(*comp)(LData d1, LData d2));

기본적으로 arraylist와 동일하지만 FInsert, SInsert, SetSortRule이라는 메소드가 추가되었다. 

간단하게 설명하면 FInsert는 대소비교 X 삽입, SInsert는 대소비교 O 삽입, SetSortRule은 대소비교 여부 설정

 

여기서 특이한 부분은 SetSortRule인데, 생소한 [함수 포인터] 라는 개념이 등장한다. (쪽팔린 일이지만 처음본다!)

SetSortRule은 인자로 함수 포인터를 받기 때문에 comp 함수를 어떻게 설정하냐에 따라 프로그램을 바꿀 수 있다.

 

LinkedList 자료구조는 다음과 같이 구성되어 있다.

typedef struct _linkedList {
	Node * head;
	Node * cur;
	Node * before;
	int numOfData;
	int(*comp)(LData d1, LData d2); //함수 포인터
}LinkdedList;

typedef LinkdedList List;

head는 맨 앞의 값을 가리키는 포인터가 될 것이다.

그 구조는 다음과 같다.

 

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

코드 상에서는 첫 번째 node가 dummy로 사용되게 된다. 이는 Insert를 편리하게 하기 위해서이다. 만약 dummy 노드가 없다면 첫 번째 삽입과, 그 다음 삽이이 달라질 것이기 때문이다.

 

이제 Insert 메소드를 살펴보자.

void LInsert(List * plist, LData data) {
	if (plist->comp == NULL)
		FInsert(plist, data);
	else
		SInsert(plist, data);
}

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는 나중에 보고 FInsert를 먼저 살펴보자. 

단순히 노드하나를 삽입하는데 노드가 삽입되는 방향을 잘 보자. 

우리는 통상 뒤로 줄을 서듯 줄줄히 붙을 것이라 생각하지만 이 코드에서는 dummy 노드 뒤에 newNode가 붙게된다. 

다음과 같은 식으로 dummy node 뒤에 붙는다. 

 

 

이제 LFirst와 LNext를 살펴보자

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;
}

First와 Next는 둘 다 특정한 Node를 가리키기 위한 메소드들이다. 

각각 특정 노드를 before과 cur(현재위치)로 가리키는데, 처음을 가리킬 것인지, 아니면 다음값을 가리킬 것인지의 차이이다. 

이 두 메소드는 Remove에서 사용된다.

LData LRemove(List *plist) {
	Node *rpos = plist->cur;
	LData rdata = rpos->data;

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

	free(rpos);
	(plist->numOfData)--;
	return rdata;
}

지울 node를 저장하고, free로 메모리에서 해제해준다. 삭제된 노드의 이전노드의 next의 삭제된 노드의 next로 연결해주고, cur를 수정한다. 이 때 cur과 before은 같은 노드를 가리키게 되는데, 재조정 할 필요는 없다. 

** cur을 수정하지 않으면, 참조되지 않은 상태의 노드를 가리키게 되는데, 이는 다음 next 호출 시에 넘어가버리는 문제가 생긴다!

 

이제 얼추 기본적인 기능의 소개는 끝났고, 대소비교 즉 정렬삽입을 소개하고 글을 마친다.

void SetSortRule(List *plist, int(*comp)(LData d1, LData d2)) { //comp를 초기화 하는 함수
	plist->comp = comp;
}

단순히 plist->comp를 comp로 설정해준다.

void SInsert(List *plist, LData data) {
	Node *newNode = (Node*)malloc(sizeof(Node));
	Node *pred = plist->head; //더미 노드를 가리킴
	newNode->data = data;

	while (pred->next != NULL && plist->comp(data, pred->next->data) != 0) {
		pred = pred->next;
	}
	newNode->next = pred->next;
	pred->next = newNode;

	(plist->numOfData)++;
}

comp(d1,d2)는 d1이 크면 1, d2가 크면 0을 반환한다. 

pred는 dummy node에서 시작해, 현재 삽입하는 데이터가 더 큰 위치를 찾을 때까지, 가리키는 노드를 옮긴다.

(pred = pred->next)

찾게 되면 반복문을 탈출하고, 삽입을 진행한다.

 

 

 

코드 전체는 하나하나 설명하려니 글재주가 없어... 쉽지 않다. 아직 누구를 가르쳐줄 실력은 아닌거 같다.

멀고 먼 코딩의 길 ㅋㅋ