[자료구조] Ordered Linked List 구현하기

만약 아래 소스코드를 사용한다면(과제나 블로그) 댓글로 목적을 적어주시고 사용해주세요. 대학생분들이 사용하기 좋게 최대한 void ptr을 사용했으며 valgrind로 메모리 누수가 없음을 확인했습니다.

 

포인터에 대해 잘 모르신다면 아래 포스팅을 참고해주세요!

[자료구조] 포인터와 동적 할당, 자료구조 입문하기! (with c언어)

 

 

 

1. include header

#include <stdio.h>
#include <stdlib.h> // malloc
#include <string.h> // strdup, strcmp

 

 

 

2. Data Struct

typedef struct Student
{
	int rank;
	char *name;
}Student;

typedef struct Node
{
	void *dataPtr;
	struct Node *next;
}Node;

typedef struct List
{
	int count;
	Node *head;
}List;

 

 

3. 구현할 함수들..

List* create_list();
Node* create_node(void* dataIn);
Student* create_student(int rank, char* name);
int insert(List *list, Node *pPre, void* dataIn);
Student* create_student(int rank, char* name);
int search(List *list, Node **pPre, Node **pLoc, void* dataIn, int (*compare)(const void*, const void*));
int addData(List *list, void *dataIn, int (*compare)(const void*, const void*), void (*update)(void *));
int removeData(List *list, void *dataIn, void **dataOut, int (*compare)(const void*, const void*));
void destroyStudent(void *ptr);
void destroyList(List* list, void (*destroyChild)(void *));
void printList(List *list, void (*process)(void *));
int compare_by_rank(const void *s1, const void *s2);
int compare_by_name(const void *s1, const void *s2);
void update_student(void *ptr);
void Print(void *s);

 

 

 

4. 생성 함수

List* create_list()
{
	List* list = (List*)malloc(sizeof(List));
	if(!list) return NULL;
	
	list->head = NULL;
	list->count = 0;
	return list;
}

Node* create_node(void* dataIn)
{
	Node* node = (Node*)malloc(sizeof(Node));
	if(!node) return NULL;
	
	node->next = NULL;
	node->dataPtr = dataIn;
	return node;
}

Student* create_student(int rank, char* name)
{
	Student* student = (Student*)malloc(sizeof(Student));
	char *new_name = (char*)malloc(20); /// 실수 조심!
	if(!student) return NULL;
	
	strcpy(new_name, name);
	student->name = new_name;
	student->rank = rank;
	return student;
}

 

 주의할 점은 create_student 입니다. 처음 구현하시는 분들이 비슷한 실수를 하기 쉽습니다. new_name으로 할당하고 strcpy를 사용하여 '내용' 을 복사하지 않고 그냥 name 을 사용한다면, 매 입력마다 값이 계속 바뀔 것 입니다.

 

 왜냐하면 name은 main함수 있는 '입력용 변수'의 주소값을 가르키기 때문입니다. 따라서 인스턴스를 생성하고 내용만 복붙해줘야 합니다.

 

 

5. 기본 연산(insert, delete, search)

int insert(List *list, Node *pPre, void* dataIn)
{
	Node* node = create_node(dataIn);
	if(!node) return -1;
	if(pPre == NULL){
		node->next = list->head;
		list->head = node;
	}
	else{
		node->next = pPre->next;
		pPre->next = node;
	}
	list->count += 1;
	return 1;
}

void delete(List *list, Node *pPre, Node *pLoc, void **dataOut)
{
	Node *_next = pLoc->next; //pLoc = NULL 인 경우는 오지 않음
	*dataOut = pLoc->dataPtr;
	list->count -= 1;
	free(pLoc);
	
	if(pPre == NULL)
		list->head = _next;
	else
		pPre->next = _next;
}

int search(List *list, Node **pPre, Node **pLoc, 
	void* dataIn, int (*compare)(const void*, const void*))
{
	
	while(*pLoc != NULL){
		int res = compare(dataIn, (*pLoc)->dataPtr);
		Node *_next = (*pLoc)->next;
		if(res <= 0){
			if(res < 0) return 0;
			return 1;
		}
		*pPre = *pLoc, *pLoc = _next;
	}
	return 0;
}

 

 여기서 보아야할 것은 2가지 입니다. 바로 'List의 Head에 접근하는 과정'과 '노드를 연결하는 과정'입니다. 설명하기 앞서 pPre = Previous Pointer(이전 포인터), pLoc = Location Pointer(현재 포인터)를 나타내며 void 포인터를 사용한 이유는 Generic DS 를 만들기 위함입니다.

 

 일단 원리를 설명하기 앞서, compare함수를 통해 '졍렬된' 상태를 유지하며 insert 할 부분을 찾거나 '정렬된'상태이기에 존재 여부를 간단히 따질 수 있습니다. 

 

 

 중요한 사실은 List의 Meta 데이터(Count, Head) 와 Node 데이터는 엄연히 다르다는 점입니다. List의 Head는 '시작 노드' 를 가르킵니다. 따라서 List의 맨 앞을 수정하기 위해선 List->head 에 접근해줘야 합니다. 

 

 하지만 '맨 앞' 을 어떻게 구분해줄 수 있을까요? 그것은 바로 pPre == NULL 로 확인할 수 있습니다. pLoc은 맨 앞의 노드이지만, 그 앞에 어떤 작업을 해야할 때도 있습니다. 따라서 초기 pPre = NULL, pLoc = list->head 로 시작합니다. 만약 pPre == NULL이 아니라면 '그 앞에' 다른 노드가 존재한다는 사실을 알 수 있습니다.

 

 예를 들어 0x002만 있는 상황에서 0x001 를 삽입한다면 pPre 는 NULL 입니다. 따라서 pPre(이전 노드) 에 접근하는 것이 아니라 head합니다. 그리고 '그 이전 노드'가 가르키는 다음(0x002)을 0x001의 다음으로 지정해주고 '그 이전 노드' 의 next를 0x001 로 지정해주면 됩니다. 삭제도 비슷하게 해주면 됩니다.

 

 참고로 이중 포인터를 사용한 까닭은 addData, removeData 등에서 해당 값들을 사용할 필요가 있기 때문입니다. 정확히 말하자면 다른 함수에서 ~주소를 얻기 위해서 입니다.

 

 

6. 연산 ( 기본 연산을 활용 )

int addData(List *list, void *dataIn, int (*compare)(const void*, const void*),
	void (*update)(void *))
{
	Node* pPre = NULL;
	Node* pLoc = list->head;

	if(search(list, &pPre, &pLoc, dataIn, compare)){
		update(pLoc->dataPtr);
		return 2; /// 이미 있었다.
	}
	else
		return insert(list, pPre, dataIn); /// 메모리 할당 여부
	
}

int removeData(List *list, void *dataIn, void **dataOut, int (*compare)(const void*, const void*))
{
	Node* pPre = NULL;
	Node* pLoc = list->head;
	
	if(search(list, &pPre, &pLoc, dataIn, compare)){
		delete(list, pPre, pLoc, dataOut);
		return 1;
	}
	return 0;
}

 

insert나 delete 는 '주소'를 알아야 했습니다. 하지만 addData나 removeData는 주소가 아닌 '대상' 의 주소를 찾은 후 insert, delete 연산으로 사용자가 쉽게 사용할 수 있게끔 도와줍니다. 

 

 

7. 삭제

void destroyStudent(void *ptr)
{
	Student* s = (Student*)ptr;
	free(s->name);
	free(s);
}

void destroyList(List *list, void (*destroyChild)(void *))
{
	Node *ptr = list->head;
	Node *ret;
	while(ptr){
		ret = ptr->next;
		destroyChild(ptr->dataPtr);
		free(ptr);
		ptr = ret;
		printf("삭제!");
	}
	free(list);
}

 

 malloc 을 어디서 했는지 곰곰히 생각해보면... List에는 Node들이 동적 할당되어있고 Node들엔 dataPtr(Student) 가 할당되어 있습니다. Student 에는 name 을 따로 할당해주신 것도 잊으면 안됩니다!! 사용했던 list도 free해줍시다! 햇갈리지 않게 Container와 Property 들을 free 해줘야한다고 기억해주시면 좋을 것 같습니다. 

 

 주의할 점은 free를 하면 '메모리만 해제' 하기 때문에 해당 포인터가 NULL을 가르키는 것은 아닙니다. 또한 해제된 메모리를 역참조할 수 없기에 ret을 통해 다음 주소를 미리 기록해놔야 합니다.

 

8. 기타 함수들

void printList(List *list, void (*process)(void *))
{
	Node *ptr = list->head;
	while(ptr){
		Node *ret = ptr->next;
		process(ptr->dataPtr);
		ptr = ret;
	}
}

int compare_by_rank(const void *v1, const void *v2)
{
	Student *s1 = (Student*)v1, *s2 = (Student*)v2;
	if(s1->rank == s2->rank) return compare_by_name(s1, s2);
	return s1->rank - s2->rank;
}


int compare_by_name(const void *v1, const void *v2)
{
	Student *s1 = (Student*)v1, *s2 = (Student*)v2;
	return strcmp(s1->name, s2->name);
}

void update_student(void *ptr)
{
	printf("%s 학생은 이미 존재함. \n", ((Student*)ptr)->name);
	/// 원하는 작업을 상황에 맞게 추가해주시면 됩니다.
}

void Print(void *v)
{
	Student* s = (Student*)v;
	printf("%s학생 %dth\n", s->name, s->rank);
}

 

printList와 destroyList 는 비슷하게 작동합니다. 

 

 

9. 메인함수

int main()
{
	int cmp, rank;
	int (*compare)(const void *, const void *);

	char cmd[20], name[20];
	List* list = create_list();
	if(!list) return 0;
	
	//printf("정렬 기준 1) Rank 2) Name : ");
	//scanf("%d", &cmp);
	cmp = 2;
	
	
	if(cmp == 1) compare = compare_by_rank;
	else compare = compare_by_name;
	
	while(1)
	{
		printf("push (rank) (name), delete (name), size, print, exit\n");
		scanf("%s", cmd);
		if(!strcmp(cmd, "push")){
			scanf("%d %s",&rank, name);
			Student* student = create_student(rank, name);
			if(addData(list, student, compare, update_student) == 2){
				destroyStudent(student);
			}
			else printf("%s학생을 추가했습니다\n",name);
			/// ERROR 나는 경우는 그냥 무시하고 작성했습니다.
		}
		else if(!strcmp(cmd, "delete")){
			scanf("%s",name);
			Student* student = create_student(0, name);
			void* dataOut;
			
			if(removeData(list, student, &dataOut, compare_by_name)){
				printf("%s학생을 삭제했습니다. 랭크는 %d였습니다.\n",name, ((Student*)dataOut)->rank);
				destroyStudent(dataOut);
			}
			else{
				printf("존재하지 않습니다.\n");
			}
			destroyStudent(student);
		}
		else if(!strcmp(cmd, "size")){
			printf("크기는 : %d입니다\n",list->count);
		}
		else if(!strcmp(cmd, "print")){
			printList(list, Print);
		}
		else if(!strcmp(cmd, "exit")){
			break;
		}
	}
	destroyList(list, destroyStudent);
	
}

 

 

---

 

일단 저는 Student(name, rank) 로 작성했는데요.. 다시 생각해보니 좋지 않은 예시인 것 같습니다. 그리고 이름순이 아니라 성적순으로 정렬하고 싶다면 그냥 처음에는 이름순으로 다 넣어놓고 마지막에 성적순으로 List를 한 개 더 만들어주시는 게 좋다고 생각합니다.  ((main)에 주석을 보시면 지운 흔적이 있으며.. 일단 name정렬만 구현한 상태입니다. )

 

아무튼.. 좋지 않은 예시였지만,, void pointer 로 작성했으니 마음대로 바꿔서 쓰시면 됩니다! Linked_List 만 잘 이해하면 Queue, Stack 과 같은 Linear DS 는 쉽게 이해하실 겁니다. 

과제할 때 그냥 가져가세요 :D