특정 자료구조를 100% 이해하기 가장 좋은 방법은 그것을 코드로 구현해보는 것이고 그럴 때 가장 좋은 방법은 C를 사용하는 것이라고 생각한다.
나는 연결리스트를 C로 구현해보았다. 먼저 직접 코드를 작성해본 뒤에 아래 코드를 참고해보면 좋을 것 같다. 많은 언어 중에 Java나 C++이 아닌 low level 언어인 C를 사용하면 좋다고 한 이유는 가장 제약이 많이 따르는 만큼 자료구조에 대한 이해를 하기 좋기 때문이다. 또한 익숙한 class가 아닌 구조체를 사용하면서 코드 연습을 가장 잘 할 수 있는 언어이기도 하다.
주로 C에서 연결리스트를 구현할 때에는 node라는 struct를 하나 만들어주고 그 안에 몇 번째인지를 알려주는 index, 해당 node가 들고 있는 값을 알려주는 data, 그리고 다음 node와 연결해주기 위한 struct node * 형식의 next를 가진다. 이 세 가지 구성을 잘 사용하면 우리가 원하는 방식의 linked list를 구현할 수 있다.
먼저 위에 언급한 것처럼 node struct부터 만들어주겠다.
typedef struct node {
int index;
int data;
struct node* next;
}NODE;
다음으로 만든 구조체를 활용하여 초기 세팅을 해주자.
NODE* head = NULL;
NODE* init(int data) {
NODE* tmp = (NODE*)malloc(sizeof(NODE));
tmp->data = data;
tmp->next = NULL;
return tmp;
}
맨 처음에는 node의 head가 가리키고 있는 것이 없으므로 NULL로 세팅을 해준 뒤 하나의 노드를 만들기 위해 init이라는 함수를 사용해주자. 우리는 사용자가 원하는 값으로 node를 세팅해줄 것이므로 인자로 data라는 parameter를 받아와서 node의 data를 해당 값으로, 그리고 다음 node는 NULL 값으로 연결해주자. 처음에 malloc의 과정이 필요하다. C를 사용하기 때문에 이러한 과정이 다소 귀찮게 느껴질 수는 있으나 이런 과정을 계속 해보다 보면 코딩 실력도 늘고 자료구조에 대한 이해도도 올라간다.
다음으로는 원하는 data가 있는 node를 찾는 과정이다. search 함수를 만들어 사용하겠다.
NODE* search(int data) {
//data 노드 찾기
//있으면 해당 노드의 주소를 return
//없으면 NULL return 하기
NODE* tmp = head;
while (tmp) {
if (tmp->data == data) {
return tmp;
}
tmp = tmp->next;
}
return NULL;
}
처음 head node부터 시작하여 쭉 노드를 순회하다가, 원하는 data 값과 노드의 데이터 값이 일치하면 해당 노드를 반환해주는 형식이다. 만약 일치하지 않는다면 계속 다음 노드를 순회하면서 찾을 때까지 순회하고 결국 찾지 못하면 NULL을 반환해준다.
다음으로 새로운 node를 추가하는 과정이다.
void add(int prev, int data) {
//prev 노드 앞에 data 추가 (삽입)
//예 10-20-30
//add(20,100); 10-100-20-30
//prev가 -1이면 맨 뒤에 추가
//최초 노드 생성인 경우 (head 로 등록)
//2. 맨 앞에 삽입하는 경우
//3. 중간/맨 뒤에 삽입하는 경우
NODE* new_node = init(data);
NODE* tmp = head;
NODE* find = NULL;
if (!head) {
head = new_node; return;
}
else if (prev != -1 ) {
find = search(prev);
if (!find) {
printf("해당 노드가 없습니다.\n");
return;
}
if (find == head) {
new_node->next = find;
head = new_node;
return;
}
else {
NODE* prev = tmp;
while (prev) {
if (prev->next == find) {
break;
}
prev = prev->next;
}
prev->next =new_node;
new_node->next = find;
return;
}
}
if (prev == -1) {
while (tmp->next) {
tmp = tmp->next;
}
tmp->next = new_node;
}
}
가장 마지막 노드에 추가하는 것이 아니라 원하는 prev 노드를 받아와 추가를 하는 것이기 때문에 조건을 나누어서 작성했다.
노드를 추가했다면 삭제하는 것 또한 필요하다.
void remove(int data) {
//index번 위치에 노드를 삭제하는것
//삭제 실패(미등록 노드를 삭제할 경우) 시 "미등록 노드"를 출력
//해당 data node 삭제
NODE* tmp = head;
NODE* find = search(data);
if (!head) {
printf("제거할 노드가 없습니다.");
return;
}
if (!find) {
printf("미등록 노드입니다");
return;
}
if (find == head) {
head = head->next;
free(tmp);
return;
}
NODE* prev = tmp;
while (prev) {
if (prev->next == find) {
break;
}
prev = prev->next;
}
prev->next = find->next;
free(find);
}
이 또한 어떠한 노드를 삭제하냐에 따라서 경우가 달라질 수 있기 때문에 경우를 나누어서 처리했다. (만약 읽어보면서 이해되지 않는 부분이 있다면 댓글을 남겨주시면 답변해드릴게요! )
다음으로는 모든 node들을 순회하면서 값을 print 해주는 함수이다.
void print_all() {
//모든 노드를 출력하세요
NODE* tmp = head;
while (tmp) {
printf("%d ", tmp->data);
tmp = tmp->next;
}
}
마찬가지로 head부터 시작하여 해당 node의 data를 출력하고 다음 노드로 넘겨주는 과정을 반복한다.
남의 코드를 읽어보는 과정과 자신이 직접 짜본 코드는 매우 다르다. 아래 전체 코드를 첨부하였고 직접 해보면서 자료구조에 대한 이해를 늘려보는 것을 매우매우 추천한다!
#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>
typedef struct node {
int index;
int data;
struct node* next;
}NODE;
NODE* head = NULL;
//가장 앞 노드 삭제하는 경우 생각
NODE* init(int data) {
NODE* tmp = (NODE*)malloc(sizeof(NODE));
tmp->data = data;
tmp->next = NULL;
return tmp;
}
NODE* search(int data) {
//data 노드 찾기
//있으면 해당 노드의 주소를 return
//없으면 NULL return 하기
NODE* tmp = head;
while (tmp) {
if (tmp->data == data) {
return tmp;
}
tmp = tmp->next;
}
return NULL;
}
void add(int prev, int data) {
//prev 노드 앞에 data 추가 (삽입)
//예 10-20-30
//add(20,100); 10-100-20-30
//prev가 -1이면 맨 뒤에 추가
//최초 노드 생성인 경우 (head 로 등록)
//2. 맨 앞에 삽입하는 경우
//3. 중간/맨 뒤에 삽입하는 경우
NODE* new_node = init(data);
NODE* tmp = head;
NODE* find = NULL;
if (!head) {
head = new_node; return;
}
else if (prev != -1 ) {
find = search(prev);
if (!find) {
printf("해당 노드가 없습니다.\n");
return;
}
if (find == head) {
new_node->next = find;
head = new_node;
return;
}
else {
NODE* prev = tmp;
while (prev) {
if (prev->next == find) {
break;
}
prev = prev->next;
}
prev->next =new_node;
new_node->next = find;
return;
}
}
if (prev == -1) {
while (tmp->next) {
tmp = tmp->next;
}
tmp->next = new_node;
}
}
void remove(int data) {
//index번 위치에 노드를 삭제하는것
//삭제 실패(미등록 노드를 삭제할 경우) 시 "미등록 노드"를 출력
//해당 data node 삭제
NODE* tmp = head;
NODE* find = search(data);
if (!head) {
printf("제거할 노드가 없습니다.");
return;
}
if (!find) {
printf("미등록 노드입니다");
return;
}
if (find == head) {
head = head->next;
free(tmp);
return;
}
NODE* prev = tmp;
while (prev) {
if (prev->next == find) {
break;
}
prev = prev->next;
}
prev->next = find->next;
free(find);
}
void print_all() {
//모든 노드를 출력하세요
NODE* tmp = head;
while (tmp) {
printf("%d ", tmp->data);
tmp = tmp->next;
}
}
void main() {
int data, select, prev;
NODE* result = NULL;
while (1) {
print_all();
printf("1. 추가 \n2. 삭제 \n3. 검색 \n0.종료 \n입력: ");
scanf_s("%d", &select);
switch (select) {
case 1:
printf("새정수: ");
scanf_s("%d", &data);
printf("어느 노드 앞에 추가?(마지막은 -1) : ");
scanf_s("%d", &prev);
add(prev, data);
break;
case 2:
printf("삭제할 정수를 입력하세요...\n");
scanf_s("%d", &data);
remove(data);
break;
case 3:
printf("검색할 정수의 입력하세요...\n");
scanf_s("%d", &data);
result = search(data);
if (result) {
printf("%d(은)는 있습니다. \n", data);
}
else {
printf("%d(은)는 미등록 노드입니다. \n", data);
}
break;
case 0:
exit(0);
}
system("pause");
system("cls");
}
}