연결 리스트(Linked List) 2

이 글은 윤성우 저 - "윤성우의 열혈 자료구조"를 공부하고 정리하여 작성하였습니다.

 

1. 연결 리스트의 개념적 이해

• 배열은 메모리 특성이 정적이어서 메모리의 길이를 변경하는 것이 불가능함.
• 그래서 필요로 하는 메모리 크기에 유연하게 대처하지 못함

1.1. 어떤 것을 연결하는 것인가

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

• 위 구조체 멤버 next는 Node형 구조체 변수의 주소값을 저장할 수 있는 포인터 변수
• 구조체의 첫번째 멤버 data에 값을 저장할 수 있음을 근거로 함
• next는 구조체 변수와 구조체 변수를 연결할 목적으로 선언되었고 next를 통해 모든 Node형 구조체 변수는 다른 Node형 구조체 변수를 가리킬 수 있음

 

1.2. 연결 리스트에서의 데이터 삽입

int main(void)
{
	Node * head = NULL;  // 리스트의 머리를 가리키는 포인터 변수
	Node * tail = NULL;  // 리스트의 꼬리를 가리키는 포인터 변수
	Node * cur = NULL;   // 저장된 데이터의 조회에 사용되는 포인터 변수
	
	Node * newNode = NULL;
	int readData;

	while(1)
	{
		printf("자연수 입력: ");
		scanf("%d", &readData);
		if(readData < 1)
			break;
		
		// 노드의 추가과정
		newNode = (Node*)malloc(sizeof(Node));   // 노드의 생성
		newNode->data = readData;   // 노드에 데이터 저장
		newNode->next = NULL;       // 노드의 next를 NULL로 초기화
		
		if(head == NULL)  // 첫번째 노드인 경우
			head = newNode; // 첫번째 노드를 head가 가리키게 함
		else    
			tail->next = newNode;
		tail = newNode  // 노드의 끝을 tail이 가리키게 함
	
	}

• 첫번째 노드 추가 완료 상태

• 두번째 노드 추가완료

• 다수의 노드를 추가한 결과

 

1.3. 연결 리스트에서의 데이터 조회

if(head == NULL)
{
	printf("저장된 자연수가 존재하지 않습니다. \n");
}
else
{
	cur = head;  // cur이 리스트의 첫번째 노드를 가리킨다
	printf("%d ", cur->data);  // 첫번째 데이터 출력
	
	while(cur->next != NULL)  // 연결된 노드가 존재한다면
	{
		cur = cur->next;  // cur이 다음 노드를 가리키게 한다.
		printf("%d ", cur->data); 
	}
}

 

1.4. 연결 리스트에서의 데이터 삭제

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

• delNextNode라는 포인터 변수를 둬 ‘삭제될 노드’를 가리키는 다음 노드 주소값을 저장하는 이유는 head가 가리키는 노드를 그냥 지우면 그 다음 노드 정보를 아는 노드가 없어져 갈 수가 없게 됨.

 

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

• 단순 연결 리스트: 연결의 형태가 한쪽 방향으로 전개되고 시작과 끝이 분명히 존재하는 리스트

2.1. 정렬 기능이 추가된 연결 리스트의 ADT 정의

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

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

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

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

int LCount(List *plist);
- 리스트에 저장된 데이터 수를 반환

void SetSortRule(List *plist, int (*comp)(LData d1, LData d2));
- 리스트에 정렬의 기준이 되는 함수를 등록
- 반환형이 int이고 LData형 인자 두 개를 전달받는 함수의 주소값을 두번째 인자로 전달!

• 새 노드를 추가하는 방식
  • 머리에 추가
    • 장점: 포인터 변수 tail이 불필요
    • 단점: 저장된 순서를 유지하지 않음
  • 꼬리에 추가
    • 장점: 저장된 순서가 유지됨
    • 단점: 포인터 변수 tail이 필요
• 리스트 자료구조는 저장된 순서를 유지하는 것이 그렇게 중요하지 않아 머리에 추가하는 방식도 좋음
• int (*comp)(LData d1, LData d2) 의 값은 다음과 같이 정의된 함수의 주소 값

int WhoIsPrecede(LData d1, LData d2)
{
	if(d1 < d2)
		return 0; // d1이 정렬상 앞서면
	else
		return 1; // d2가 정렬상 앞서면
}

 

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

• 첫번째 노드는 포인터 변수 head가 가리킨다는 점에서 다른 노드들과 차이가 있음
• 이로 인해 노드를 추가, 삭제, 조회하는 방법에 있어 첫번째 노드와 두번째 이후의 노드에 차이가 생김

• 포인터 변수 tail이 사라졌고 리스트 맨 앞에 더미 노드를 넣음
• 이렇게 되면 처음 추가되는 노드가 구조상 두번째노드가 되므로 추가, 삭제, 조회 시 일관된 형태로 구성할 수 있음

 

2.3. 정렬 기능이 추가된 연결 리스트 구조체와 헤더파일 정의

• 노드를 표현한 구조체 정의

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

• 연결 리스트 구현이 필요한 다음 유형의 변수들은 구조체로 묶지 않고 main 함수의 지역변수로 선언하거나 전역변수로 선언함

Node *head;  // 연결 리스트의 머리를 가리키는 포인터 변수
Node *cur;   // 참조를 위한 포인터 변수

• 그렇지만 배열을 하나만 사용할 건 아니지 않는가. 그렇기 때문에 프로그램을 구현할 때에는 typedef struct_node 안에 다 넣어서 선언해야 한다.

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

 

2.4. 더미 노드 기반의 단순 연결 리스트 구현 1: 리스트 초기화 및 노드 삽입

• 연결 리스트 초기화

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 *plis, LData data)
{
	Node * newNode = (Node*)malloc(sizeof(Node)); // 새노드 생성
	newNode->data = data;    // 새 노드에 데이터 저장
	
	newNode->next = plist->head->next; // 1. 새 노드가 다른 노드를 가리키게 함
	plist->head->next = newNode; // 2. 더미 노드가 새 노드를 가리키게 함
	
	(plist->numOfData)++;
}

 

2.5. 더미 노드 기반의 단순 연결 리스트 구현 2: 데이터 조회

• LFirst

int LFirst(List *plist, LData *pdata)
{
	if(plist->head->next == NULL) // 더미 노드가 NULL을 가리키면
		return FALSE; // 반환할 데이터 없음
	
	plist->before = plist->head;  // before은 더미 노드를 가리키게 함
	plist->cur = plist->head->next; // cur은 첫번째 노드를 가리키게 함
	
	*pdata = plist->cur->data; // 첫번째 노드의 데이터를 전달
	return TRUE; // 데이터 반환 성공	
}

• LNext

int LNext(List *plist, LData *pdata)
{
	if(plist->cur->next == NULL)  // cur이 NULL을 가리킨다면,
		return FALSE;   // 반환할 데이터 없음
		
	plist->before = plist->cur;  // cur이 가리키던 것을 before가 가리킴
	plist->cur = plist->cur->next;  // cur은 그 다음 노드를 가리킴
	
	*pdata = plist->cur->data;  // cur이 가리키는 노드의 데이터 전달
	return TRUE;  // 데이터 반환 성공
}

 

2.6. 더미 노드 기반의 단순 연결 리스트 구현 3: 노드의 삭제

• 바로 이전에 호출된 LFirst 혹은 LNext 함수가 반환한 데이터를 삭제

LData LRemove(List *plist)
{
	Node *rpos = plist->cur;  // 소멸 대상의 주소 값을 rpos에 저장
	LData rdata = rpos->data; // 소멸 대상의 데이터를 rdata에 저장
	
	plist->before->next = plist->cur->next; // 1. 소멸 대상을 리스트에서 제거
	plist->cur = plist->before;  // 2. cur이 가리키는 위치를 재조정
	
	free(rpos);  // 리스트에서 제거된 노드 소멸
	(plist->numOfData)--;  // 저장된 데이터 수 하나 감소
	return rdata;  // 제거된 노드의 데이터 반환
}

 

3. 연결 리스트의 정렬 삽입 구현

3.1. 연결 리스트에서의 정렬기준 설정

• 정렬기준 설정과 관련 있는 부분
  • 연결 리스트의 정렬기준이 되는 함수 등록하는 SetSortRule 함수
  • SetSortRule 함수를 통해서 전달된 함수정보를 저장하기 위한 LinkedList의 멤버 comp
  • comp에 등록된 정렬기준을 근거로 데이터를 저장하는 SInsert 함수
  → “SetSortRule 함수가 호출되면서 정령의 기준이 리스트의 멤버 comp에 등록되면, SInsert 함수 내에서는 comp에 등록된 정렬의 기준을 근거로 데이터를 정렬하여 저장”
• 코드

void SetSortRule(List * plist, int (*comp)(LData d1, LData d2))
{
	plist->comp = comp;
}

void SInsert(List * plist, LData data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));   // 새 노드 생성
	Node * pred = plist->head;  // pred는 더미 노드를 가리킴
	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)++;  // 저장된 데이터 수 하나 증가
}

 

3.2. 정렬의 핵심 - while 반복문

• 반복 조건 1 : pred->next != NULL
  • pred가 리스트의 마지막 노드를 가리키는지 묻기 위한 연산
• 반복 조건 2: plist->comp(data, pred->next->data) != 0
  • 새 데이터와 pred의 다음 노드에 저장된 데이터의 우선순위 비교를 위한 함수 호출
  • comp가 0을 반환
    • 첫 번째 인자인 data가 정렬 순서상 앞서서 head에 더 가까워야 하는 경우
  • comp가 1을 반환
    • 두 번째 인자인 pred->next->data가 정렬 순서상 앞서서 head에 더 가까워야 하는 경우

 

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

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

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

 

자료

• 윤성우의 열혈 자료구조 (윤성우 저, 2023.10)