Chapter 04-2. 연결 리스트(Linked List) 2

 

---

1. 단순 연결 리스트의 ADT와 구현

/* 추가된 함수 */
void SetSortRule(List* plist, int (*comp)(LData d1, LData d2));
- 리스트에 정렬의 기준이 되는 함수를 등록한다.

인자로 전달이 가능한 함수의 예는 아래와 같다.

int WhoIsPrecede(LData d1, LData d2)
{
    if(d1 < d2)
        return 0;     // d1이 정렬 순서상 앞선다.
    else
        return 1;     // d2가 정렬 순서상 앞서거나 같다.
}

 

새 노드를 연결 리스트의 머리에 추가하는 경우

장점 : 포인터 변수 tail이 불필요하다.

단점 : 저장된 순서를 유지하지 않는다.

 

새 노드를 연결 리스트의 꼬리에 추가하는 경우

장점 : 포인터 변수 tail이 불필요하다.

단점 : 저장된 순서를 유지하지 않는다.

 

SetSortRule 함수 선언에 대한 이해 (정렬)

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

반환형이 int 이고,                                                      int(*comp)(LData d1, LData d2)
LData형 인자를 두 개 전달받는,                                int(*comp)(LData d1, LData d2)
함수의 주소 값을 전달 해라                                       int(*comp)(LData d1, LData d2)

주소 값을 받는 함수는 아래와 같다.

int WhoIsPrecede(LData d1, LData d2)
{
    if(d1 < d2)
        return 0;         // d1이 정렬 순서상 앞선다.
    else
        return 1;         // d2가 정렬 순서상 앞서거나 같다.
}

 

 

---

2. 더미 노드(Dummy Node) 기반의 단순 연결 리스트

우리는 이전 연결리스트에서는 첫 번째 노드와 두 번째 노드 이후의 로직이 달랐다.

하지만 더미노드를 헤드 파일로 받게하는 첫 번째 노드로 설정한다면, 노드의 참조과정이 하나의 로직으로 이루어진다.

 

더미 노드 연결 리스트 구현

typedef struct _node
{
    LData data;            // typedef int LData
    struct_node* next;
} Node;

제공하는 구조체는 기존과 동일하게 사용한다.

 

또한 기존 코드를 사용하지만 바꿀 곳들이 존재한다.
노드의 추가과정과 메모리의 해제과정들이 바뀌어야한다. 그에 대한 구현은 아래와 같다.

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

/*
if(head == NULL)
	head = newNode;
else
	tail->next = newNode;
*/
tail->next = newNode;

tail = newNode;


/**** 입력 받은 데이터의 출력과정 ****/
printf("입력 받은 데이터의 전체출력! \n");
if(head == NULL) 
{
	printf("저장된 자연수가 존재하지 않습니다. \n");
}
else 
{
	cur = head; 
//	printf("%d  ", cur->data);   // 첫 번째 데이터 출력
		
	while(cur->next != NULL)    // 두 번째 이후의 데이터 출력
	{
		cur = cur->next;
		printf("%d  ", cur->data);
	}
}


/**** 메모리의 해제과정 ****/
if(head == NULL) 
{
	return 0;    // 해제할 노드가 존재하지 않는다.
}
else 
{
	Node * delNode = head;
	Node * delNextNode = head->next;

//	printf("%d을(를) 삭제합니다. \n", head->data);
//	free(delNode);    // 첫 번째 노드의 삭제
	
	while(delNextNode != NULL)    // 두 번째 이후의 노드 삭제 위한 반복문
	{
		delNode = delNextNode;
		delNextNode = delNextNode->next;

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

노드의 추가과정, 출력과정, 해제과정을 볼 수 있다.

여기에서는 헤드를 더미로 설정하고 더미의 next에 추가될 노드를 넣어 사용한다.

또한 해제도 마찬가지로 두번째 노드 이후로의 삭제를 진행한다.

 

---

3. 정렬 기능이 추가된 연결 리스트

기존 더미노드에서 정렬을 위한 포인터 함수가 추가되었다.

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

 

---

1. ListInit(List* plist) 함수

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

위의 그림과 같이 head를 동적으로 선언 후, 더미노드를 만드는 과정을 보여주고 있다.

 

---

2. LInsert(List* plist, LData* pdata) & FInsert(List* plist, LData data) 함수

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

노드 추가에 대한 로직이다.

 

Node * newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;

 

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

동적할당 newNode를 생성시키고 더미 뒤에 추가를 진행하는 모습을 볼 수 있다.

 

---

3. Lfirst(List* plist, LData* pdata) 함수

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

 

---

4. LNext(List* plist, LData* pdata) 함수

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

 

---

4. LRemove(List* plist) 함수

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 * rpos = plist->cur;
LData rdata = rpos->data;

 

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

 

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

 

위의 그림처럼 분석을 할 수 있다.