Chapter 03~05. 연결리스트(Linked List)

자료구조의 첫 번째 파트인 연결 리스트에 대해 정리해보겠습니다.

연결 리스트를 알기 전에 먼저 리스트에는 2가지 종류가 있는데

• 순차리스트 - 배열을 기반으로 구현된 리스트
• 연결리스트 - 메모리의 동적 할당을 기반으로 구현된 리스트

리스트의 ADT(리스트 자료구조가 제공해야할 기능)에 대해 정의해보자!

• void ListInit(List * plist);
  • 초기화할 리스트의 주소 값을 인자로 전달한다.
  • 리스트 생성 후 제일 먼저 호출되어야 하는 함수이다.
• void LInsert(List * plist, LData data);
  • 리스트에 데이터를 저장한다. 매개변수 data에 전달된 값을 저장한다.
• int 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);
  • 리스트에 정렬의 기준이 되는 함수를 등록한다.

#include <stdio.h>
#include "ArrayList.h"

// 리스트를 생성 후 바로 호출해야하는 함수로 초기화할 리스트의 주소 값을 인자로 전달해주는 코드이다.
void ListInit(List * plist)
{
	(plist->numOfData) = 0; // data의 수를 알려주기 위해 numOfData라는 변수를 0으로 초기화해준다.
	(plist->curPosition) = -1; // 현재 위치를 알려주는 변수로 -1로 초기화해준다.
}

// 리스트에 데이터를 저장하는 코드로, 파라미터 data에 전달된 값을 plist에 저장한다.
void LInsert(List * plist, LData data)
{
	if(plist->numOfData > LIST_LEN) 
	{
		puts("리스트에 변수가 들어감");
		return;
	}

	plist->arr[plist->numOfData] = data; // 맨 처음에 numOfData가 0으로 초기화 되어있으므로 arr[0]에 data를 넣어준다는 의미이다.
	(plist->numOfData)++; // 배열에 data가 들어갔으므로 numOfData를 1씩 증가시킨다.
}

// 리스트에 첫번째 데이터인 pdata가 가리키는 메모리에 저장된다.
int LFirst(List * plist, LData * pdata)
{
	if(plist->numOfData == 0)
		return FALSE;

	(plist->curPosition) = 0; // 가장 처음 데이터에 접근하므로 curPosition을 0으로 초기화한다.
	*pdata = plist->arr[0]; // 배열의 가장 처음 인자를 pdata 값 안에 넣는다.
	return TRUE;
}

// 리스트의 다음 데이터를 지정해준다. 
int LNext(List * plist, LData * pdata)
{
	if(plist->curPosition >= (plist->numOfData)-1)
		return FALSE;

	(plist->curPosition)++; // curPosition을 1씩 증가시켜주면서 다음 데이터를 가리킨다.
	*pdata = plist->arr[plist->curPosition]; // 배열의 숫자를 1씩 증가시켜주면서 배열에 들어있는 데이터를 가져온다.
	return TRUE;
}

// LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제하고 삭제된 데이터를 반환한다.
LData LRemove(List * plist)
{
	int rpos = plist->curPosition;
	int num = plist->numOfData;
	int i;
	LData rdata = plist->arr[rpos]; // 임시변수 하나를 생성해 삭제할 데이터를 저장해준다.

	for(i=rpos; i<num-1; i++)
		plist->arr[i] = plist->arr[i+1]; // 삭제된 데이터에 해당하는 메모리가 비워졌으므로 다음 배열의 데이터를 하나씩 앞으로 땡겨준다.

	(plist->numOfData)--; // 데이터 하나를 지웠으므로 numOfData를 1 감소시킨다.
	(plist->curPosition)--; // 데이터 하나를 지웠으므로 curPosition를 1 감소시킨다.
	return rdata; // 삭제할 데이터를 저장한 임시변수를 반환해준다.
}

// 배열의 크기를 알려주는 함수이다.
int LCount(List * plist)
{
	return plist->numOfData;
}

위의 코드는 ArrayList.c 의 코드로 위에서 설명한 리스트의 기능들을 정리한 코드이다.

---

이제 “연결”을 기반으로 하는 다른 리스트의 구현 방법에 대해 설명을 하겠다.

처음 공부할 내용은 연결의 형태가 한쪽 방향으로 전개되고 시작과 끝이 분명히 존재하는 ‘단순 연결 리스트’ 이다.

새 노드를 추가할 때 리스트의 머리와 꼬리 중 어디에 저장할 할 것인지 저장을 해야한다.

• 머리에 추가할 경우 장점 : 포인터 변수 tail 이 불필요하다. 단점 : 저장된 순서를 유지하지 않는다.
  
• 꼬리에 추가할 경우 장점 : 저장된 순서가 유지된다. 단점 : 포인터 변수 tail 이 필요하다.
  

#include <stdio.h>
#include <stdlib.h>
#include "DLinkedList.h"

// 리스트 초기화를 위한 코드
void ListInit(List * plist)
{
	plist->head = (Node*)malloc(sizeof(Node)); // 더미 노드의 생성
	plist->head->next = NULL;
	plist->comp = NULL; 
	plist->numOfData = 0; //Data의 수를 알려주는 변수를 0으로 초기화
}

// comp가 NULL 일때 호출되는 함수
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)++; // 저장된 노드의 수를 하나 증가시킴
}

//SetSortRule 함수가 호출되면서 정렬의 기준이 리스트의 멤버 comp에 등록되면, 
//SInsert 함수 내에서는 comp에 등록된 정렬의 기준을 근거로 데이터를 정렬하여 저장한다.
void SInsert(List * plist, LData data)
{
	Node * newNode = (Node*)malloc(sizeof(Node)); // 새 노드의 생성
	Node * pred = plist->head; // pred는 더미 노드를 가리킴
	newNode->data = data; // 새 노드에 데이터 저장

	// 새 노드가 들어갈 위치를 찾기 위한 반복문!
	// 반복의 조건 1 : pred가 리스트의 마지막 노드를 가리키는지 묻기 위한 연산
	// 반복의 조건 2 : 새 데이터와 pred의 다음 노드에 저장된 데이터의 우선순위 비교를 위한 함수호출
	while(pred->next != NULL &&
		plist->comp(data, pred->next->data) != 0) 
	{
		pred = pred->next; // 다음 노드로 이동
	}

	newNode->next = pred->next; // 새 노드의 오른쪽을 연결
	pred->next = newNode; // 새 노드의 왼쪽을 연결

	(plist->numOfData)++; // 저장된 데이터의 수 하나 증가
}

// 노드의 추가는 리스트의 멤버 comp에 무엇이 저장되어 있느냐에 따라 방법이 다름
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) // 더미노드가 NULL을 가리킨다면,
		return FALSE; // 반환할 데이터가 없다.

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

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

// 더미 노드를 만들면서 생기는 이점(LFirst와 코드가 거의 유사함 head가 cur로 바뀌는거 말고 차이점 없음)
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 * rpos = plist->cur; // 소멸 대상의 주소 값을 rpos에 저장
	LData rdata = rpos->data; // 소멸 대상의 데이터를 rdata에 저장

	// cur의 위치를 한칸 왼쪽으로 옮겨주기 위해 before 사용
	plist->before->next = plist->cur->next; // 소멸 대상을 리스트에서 제거
	plist->cur = plist->before; // cur이 가리키는 위치를 제조정

	free(rpos); // 리스트에서 제거된 노드 소멸
	(plist->numOfData)--; // 저장된 데이터의 수 하나 감소
	return rdata; // 제거된 노드의 데이터 반환
}

// 리스트에 들어있는 데이터의 개수를 반환해주는 함수
int LCount(List * plist)
{
	return plist->numOfData;
}

// 리스트가 오름차순인지, 내림차순인지 결정하는 함수를 파라미터로 받아와 comp의 규칙을 정해주는 함수
void SetSortRule(List * plist, int (*comp)(LData d1, LData d2))
{
	plist->comp = comp;
}

위의 코드는 DLinkedList.c의 코드로 “연결”을 기반으로 한 리스트 코드이다.