Chap 04. 연결 리스트(Linked List) 2 [윤성우의 열혈 자료구조]

*본 내용은 [윤성우의 열혈 자료구조] 책과 강의를 보고 공부하면서 요점 정리한 내용입니다.

Chap 04-1: 연결 리스트의 개념적인 이해

🔳 Linked! 무엇을 연결하겠다는 뜻인가!

✔ 노드 구조체

typedef struct _node
{
	int data; // 데이터를 담을 공간
    struct _node * next; //연결의 도구
}Node;

• 노드 연결의 방향(좌/우)과 head, tail의 존재 유무는 상황에 따라서 변경 가능하다.

🔳 LinkedRead.c

✔ 초기화

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

int main(void)
{
	Node * head = NULL;
    Node * tail = NULL;
    Node * cur = NULL;
    
    Node * newNode = NULL;
    int readData;
    ....
}

• head, tail. cur이 연결 리스트의 핵심!
  ∙ head: 메모리의 첫 부분을 가리키기 위한 것
  ∙ tail: 메모리의 끝 부분을 가리키기 위한 것
  ∙ cur: 순차접근을 위해 사용

✔ 노드 삽입

while(1)
{
	printf("자연수 입력: ");
    scanf("%d", &readData);
    if(readData < 1) // 데이터가 1보다 작으면 노드 추가 중지
    break;

	// 노드의 추가 과정
    newNode = (Node*)malloc(sizeof(Node));
    newNode->data = readData; // 데이터 저장
    newNode->next = NULL;
    
    if(head==NULL) // 첫 번째 노드를 삽입했을 때
    	head = newNode;
    else // 두 번째 이후 부터
    	tail->next = newNode;
    
    tail = newNode;
}

• 첫 번째 노드 삽입 그림
  

• 두 번째 노드 삽입 그림
  

• 다수의 노드를 저장한 결과
  

✔ 데이터 조회 (== 순차적 접근)

전체 데이터의 출력 과정

if(head == NULL)
{
	printf("저장된 자연수가 존재하지 않습니다. \n");
}
else
{
	cur = head;
    printf("%d ", cur->data);
    while(cur->next != NULL
    {
    	cur = cur->next;
        printf("%d", cur->data);
    }
}

✔ 데이터 삭제

전체 노드의 삭제 과정
(연결 리스트의 전통적인 삭제 방법은 아니다.)

• 노드를 삭제 한 후 dN을 이동하는 것, dN을 이동한 후 노드를 삭제를 하는 것 모두 불가능하다. 따라서 포인터 변수가 최소 2개(dN, dNN) 필요하다.

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); // 삭제
    }
}

• 단점: 첫 번째 노드와 그 이후 노드의 삭제 방법이 구분된다.
  구분이 안되는 모델을 구현하기 위해 '더미 노드'를 사용해보자

Chap 04-2: 단순 연결 리스트의 ADT와 구현

🔳 정렬 기능 추가된 연결 리스트의 ADT

void ListInit(List * plist);
∙ 초기화할 리스트의 주소 값을 인자로 전달한다.
∙ 리스트 생성 후 제일 먼저 호출되어야 하는 함수이다.

void LInsert(List * plist, LData data);
∙ 리스트에 데이터를 저장한다. 매개변수 data에 전달된 값을 저장한다.

void LFirst(List * plist, LData * pdata);
∙ 첫 번째 데이터가 pdata가 가리키는 메모리에 저장된다.
∙ 데이터의 참조를 위한 초기화가 진행된다.
∙ 참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환

int LNext(List * plist, LData * pdata);
∙ 참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장된다.
∙ 순차적인 참조를 위해서 반복 호출이 가능하다.
∙ 참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야 한다.
∙ 참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환

LData LRemove(List * plist);
∙ LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제한다.
∙ 삭제된 데이터는 반환된다.
∙ 마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다.

int LCount(List * plist);
∙ 리스트에 저장되어 있는 데이터의 수를 반환한다.

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

🔳 더미 노드 기반 연결 리스트

※ 새 노드의 추가 위치에 따른 장단점

• 새 노드를 연결 리스트의 머리에 추가하는 경우
  ∙ 장점: 포인터 변수 tail이 불필요하다.
  ∙ 단점: 저장된 순서를 유지하지 않는다.

• 새 노드를 연결 리스트의 꼬리에 추가하는 경우
  ∙ 장점: 저장된 순서가 유지된다.
  ∙ 단점: 포인터 변수 tail이 필요하다.

--> 두 가지 다 가능한 방법이다. 다만 tail의 관리를 생략하기 위해 머리에 추가하는 것을 원칙으로 하자.

✔ 머리에 새 노드를 추가하되 더미 노드 없는 경우

첫 번째 노드와 두 번째 이후의 노드 추가 및 삭제 방식이 다를 수 있다. (코드가 일관되지 않음)

✔ 머리에 새 노드를 추가하되 더미 노드 있는 경우

노드의 추가 및 삭제 방식이 항상 일정하다.
(연결리스트의 표준 모델이라고 생각하자)

🔳 정렬 기능 추가된 연결 리스트의 구조체

✔ 노드의 구조체 표현

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

✔ 연결 리스트의 구조체 표현

head에 새 노드 추가하고자 하므로 tail은 없음

typedef struct _linkedList
{
	Node * head;						// 더미 노드를 가리키는 멤버
    Node * cur;							// 참조 및 삭제를 돕는 멤버
    Node * before;						// 삭제를 돕는 멤버
    int numOfData;						//저장된 데이터의 수를 기록하기 위한 멤버
    int (*comp)(LData d1, LData d2);	// 정렬의 기준을 등록하기 위한 멤버
}LinkedList;

🔳 정렬 기능 추가된 연결 리스트

✔ 헤더파일

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

[더미 노드 연결 리스트 구현]

✔ 초기화

void ListInit(List * plist)
{
	plist->head = (Node*)malloc(sizeof(Node)); // 더미 노드의 생성
	plist->head->next = NULL;
	plist->comp = NULL;
	plist->numOfData = 0;
}

✔ 삽입

• 모든 경우에 있어서 동일한 삽입과정을 거친다는 것이 더미 노드 기반 연결 리스트의 장점!

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)++;							// 저장된 노드의 수를 하나 증가시킴
}

✔ 참조

• before은 cur의 왼쪽에 있는 노드 가리킴

int LFirst(List * plist, LData * pdata) // 첫 번째 데이터 참조
{
	if(plist->head->next == NULL)		// 더미 노드가 NULL을 가리킨다면,
		return FALSE;					// 반환할 데이터가 없다!

	/*** LNext와 차이점 ***/
	plist->before = plist->head;		// before은 더미 노드를 가리키게 함
	plist->cur = plist->head->next;		// cur은 첫 번째 노드를 가리키게 함

	*pdata = plist->cur->data;			// 첫 번째 노드의 데이터를 전달
	return TRUE;						// 데이터 반환 성공!
}

int LNext(List * plist, LData * pdata) 	// 다음 데이터 참조
{
	if(plist->cur->next == NULL)		// 더미 노드가 NULL을 가리킨다면,
		return FALSE;					// 반환할 데이터가 없다!
	
    /*** LFirst와 차이점 ***/
	plist->before = plist->cur;			// cur이 가리키던 것을 before가 가리킴
	plist->cur = plist->cur->next;		// cur은 그 다음 노드를 가리킴

	*pdata = plist->cur->data;			// cur이 가리키는 노드의 데이터 전달
	return TRUE;						// 데이터 반환 성공!
}

✔ 삭제

• 삭제 전
  ∙ cur이 있는 위치가 삭제할 대상이다.
  

• 삭제 후
  ∙ 단방향 리스트이므로 왼쪽 주소는 얻을 수 없기 때문에 cur을 왼쪽으로 한 칸 옮기기 위해 before이 필요하다.
  ∙ cur을 오른쪽이 아닌 왼쪽으로 이동하는 이유는 최근에 참조한 위치를 가리키기 위해서이다.
  ∙ before은 cur 한 칸 전에 있어야 하는데 같은 위치를 가리키고 있다. 하지만 LRemove 함수는 연속으로 호출 할 수 없으므로 before을 한 칸 전으로 옮길 필요는 없다. (단방향이므로 옮기는게 불가능하기도 함.) LFirst 또는 LNext 함수 호출 시 before은 재설정된다.
  

• 구현

LData LRemove(List * plist)
{
    //cur을 왼쪽으로 옮기면 free해야하는 노드 주소 잃어버리므로 cur이 가지고 있는 주소값을 rpos에 백업한다. 
	Node * rpos = plist->cur; 
	LData rdata = rpos->data;

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

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

Chap 04-3: 연결 리스트의 정렬 삽입의 구현

🔳 단순 연결 리스트의 정렬 관련 요소 세 가지

• 정렬기준이 되는 함수를 등록하는 SetSortRule 함수
• SetSortRule 함수 통해 전달된 함수정보 저장을 위한 LinkedList의 멤버 comp
• comp에 등록된 정렬기준을 근거로 데이터를 저장하는 SInsert 함수

--> 정리) SetSortRule 함수가 호출되면서 정렬의 기준이 리스트의 멤버 comp에 등록되면, SInsert 함수 내에서는 comp에 등록된 정렬의 기준을 근거로 데이터를 정렬하여 저장한다.

🔳 SetSortRule 함수

✔ SetSortRule 함수 선언에 대한 이해

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

• ※ 함수 포인터
  왼쪽 반환형, 오른쪽 매개변수 선언을 갖고 있는 함수의 주소값을 저장할 수 있는 포인터 변수
  (위 함수에선 comp가 함수 포인터 변수이다.)

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

• 인자로 전달이 가능한 함수의 예

int WhoIsPrecede(LData d1, LData d2)	// typedef int LData;
{
	if(d1 < d2)
    	return 0;
    else
    	return 1;
}

✔ 정렬의 기준을 결정하는 함수에 대한 약속

• 약속에 근거한 함수 정의의 예
  다음 함수는 오름차순을 정렬 기준으로 했다.

int WhoIsPrecede(LData d1, LData d2)
{
	if(d1 < d2) // 오름차순에 대한 함수(내림차순이라면 d1 > d2)
    	return 0;	// d1이 정렬 순서상 앞서면 0 반환
    else
    	return 1;	// d2가 정렬 순서상 앞서거나 같으면 1 반환
}

• 이렇듯 결정된 약속을 근거로 함수가 정의되어야 하며, 연결 리스트 또한 이를 근거로 구현되어야 한다.
• 

✔ 정렬의 기준을 설정하기 위한 함수의 정의 기준

• 두 개의 인자를 전달받도록 함수를 정의한다.
• 첫 번째 인자의 정렬 우선순위가 높으면 0을, 그렇지 않으면 1을 반환한다.

🔳 SetSortRule 함수와 멤버 comp

1. SetSortRule 함수의 호출을 통해서...

void SetSortRule(List * plist, int (*comp)(LData d1, LData d2))
{
	plist->comp = comp;	// NULL이었던 (plist->comp)값에 comp 삽입됨
}

2. 멤버 comp가 초기화 되면...

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

3. 정렬 관련 SInsert 함수가 호출된다.

void LInsert(List * plist, LData data)
{
	if(plist->comp == NULL)
		FInsert(plist, data);
	else // plist->comp != NULL 이므로
		SInsert(plist, data); // 호출
}

🔳 SInsert 함수

• 
• 위의 전제 조건

1. LInsert 함수가 호출 되었었음
2. SetSortRule 함수를 통해 comp가 초기화 됨

• 구현

void SInsert(List * plist, LData data)
{
	/*** 1. 초기화 ***/
	Node * newNode = (Node*)malloc(sizeof(Node));
	Node * pred = plist->head; // pred가 더미노드 가리키게 함.
	newNode->data = data;

	/*** 2. 새 노드가 들어갈 위치를 찾기 위한 반복문 ***/
	while(pred->next != NULL && plist->comp(data, pred->next->data) != 0)
	{
		pred = pred->next; // 다음 노드로 이동
	}
	
    /*** 3. 노드 추가 ***/
	newNode->next = pred->next;
	pred->next = newNode;

	(plist->numOfData)++;
}

• 1. 초기화
     pred가 첫 번째 노드(2를 가진 노드)를 가리킨다면 2 앞에 노드를 추가해야 하는 경우 앞 노드의 주소를 알지 못해서 추가하지 못한다.
     
• 2. 새 노드가 들어갈 위치를 찾기 위한 반복문
     ∙ pred->next != NULL
     pred->next == NULL은 pred가 마지막 노드를 가리킬 때를 말한다. pred가 리스트의 마지막 노드를 가리키는지 묻기 위한 연산이다.
     ∙ plist->comp(data, pred->next->data) != 0
     [새 데이터] 와 [pred 다음 노드에 저장된 데이터] 의 우선순위 비교를 위한 함수를 호출한다.
     이때 comp가 0을 반환한다는 것은 첫 번째 인자인 data가 정렬 순서상 앞서기 때문에 head에 가까워야 한다는 의미이다.
     ∙ (5와 2), (5와 4) 그리고 (5와 6)을 비교 후 comp가 0을 반환해 while문을 빠져나가는 순간 pred는 4를 가진 노드를 가리키고 있다.

• 3. 노드 추가