링크드리스트(LinkedList) 구현 (C언어) : Part.2 - insert_end, free_lsit
이 전 포스팅에서 초기 설정을 진행했다. 이제 본격 적으로 구현을 시작할 것이다. 시작에 앞서 아마 실행을 해 봤을 수. 있는데 실행하면 현재 테스트 코드에서 호출하고 있는 함수들이 실제 구현되지 않았다고 에러를 발생시킬 것이다. 그래서 우리가 구현을 끝냈거나 구현을 진행할 예정인 테스트 코드는 제외하고 나머지는 주석 처리를 해 두면 된다.
1. 구현 목표
우리가 이번에 구현할 기능은 아래와 같다.
- create_node : 링크드 리스트에 추가할 노드 생성
- insert_end : 링크드 리스트의 끝에 노드 추가
- free_list : 링크드 리스트 전체 삭제 및 동적 메모리 해제
링크드 리스트는 노드라고 하는 요소들을 연결해서 구현한다고 할 수 있고 그 말은 링크드 리스트를 구현하기 위해 먼저 노드를 만들 수 있어야 한다. 그리고 생성된 노드를 연결해 링크드 리스트를 만드는 것을 진행할 것이고 마지막으로 우리는 노드를 생성할 때 동적 메모리 할당 즉 malloc을 사용해 힙에 동적으로 메모리를 할당할 것인데 동적으로 할당한 메모리는 사용 후 필히 삭제를 해야 한다. 그래서 free_list라는 함수로 모든 노드의 동적 메모리를 해제하는 기능을 추가할 것이다.
2. 기능 구현
🔨 create_node 함수 구현
Node* create_node(int data) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) {
return NULL;
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}create_node 라는 함수는 data라는 int값을 이용해 새로운 노드를 만들어 반환하는 함수이다. 이때 malloc을 이용해 동적으로 메모리를 할당해서 생성된 Node를 반환하게 된다. 코드의 순서로 보면
- 새로운 노드를 생성한다.
- 노드가 정상적으로 생성됬는지 확인하고 그렇지 않으면 NULL을 반환한다.
- 노드가 정상적으로 생성되었다면 구조체 포인터를 활용해 Node의 data에 인자로 받았던 data 값을 설정한다.
- 노드는 현재 새로 생성된 상태이기 때문에 next 값을 NULL로 설정한다.
- 생성된 노드를 반환한다.
시작은 매우 간단하다.
🔨 insert_end 함수 구현
이제 insert_end 함수를 구현할 것이다.
void insert_end(Node** head, int data) {
}이 안에 내용을 추가할 예정이다.
구현의 핵심 아이디어는 다음과 같다.
- create_node() 함수를 이용해 새로운 노드를 생성한다.
- 새로 생성된 노드가 있는지 체크해서 없다면 return을 통해 반환한다.
- head 노드 즉 링크드 리스트의 시작점이 비어있는 경우 즉 리스트에 노드가 없는 경우에는 새로 만들어진 노드를 설정하고 즉시 반환한다.
- 노드가 비어있지 않은 상태 즉 연결된 노드들이 있는 경우 while을 통해 노드의 끝까지 이동한 뒤 가장 마지막 노드에 새로 만든 노드를 next에 등록한다.
void insert_end(Node** head, int data) {
Node* new_node = create_node(data);
if (new_node == NULL) {
return;
}
if (*head == NULL) {
*head = new_node;
return;
}
Node* cur = *head;
while (cur->next) {
cur = cur->next;
}
cur->next = new_node;
}이게 구현된 코드이다.
🔨 free_list 함수 구현
지금 까지 새로운 노드를 생성하고 생성된 노드를 링크드 리스트 마지막에 연결하는 함수를 작성했다. 하지만 여기서 끝낸다면 매우 큰 문제를 발생시킬 것이다. 우리는 지금 새로운 노드를 동적 메모리 할당으로 생성하고 있고 이를 제 때 해제 하지 않으면 매우 위험한 경우☢️가 발생할 수 있으니 필히 메모리 해제를 해야 한다.
void free_list(Node* head) {
}위 함수를 채워 넣겠다.
구현의 핵심 아이디어는 다음과 같다.
- temp 노드에 현재 노드를 담는다.
- 헤드를 현재 헤드의 다음 노드로 변경한다.
- temp 노드를 메모리 해제 한다.
이게 무슨 소리인가 할 수 있는데 C와 같은 프로그래밍 언어를 배울 때 아마 다들 A와 B의 값을 서로 변경하는 것을 해 봤을 것이다.
int a = 10;
int b = 1;
int temp;
temp = a;
a = b;
b = 1;이렇게 말이다. 즉 삭제하려는 노드 즉 링크드 리스트의 헤드 노드를 temp에 저장해 두고 head의 값을 head->next 즉 다음 노드로 설정해 두고 임시 저장된 노드는 해제한다는 것이다.
void free_list(Node* head) {
if (head == NULL) {
return;
}
Node* temp = NULL;
while (head) {
temp = head;
head = head->next;
free(temp);
}
}3. 기능 검증
이제 우리는 새로운 노드를 생성하고, 생성된 노드를 이용해 링크드 리스트를 만들고 링크드 리스트의 메모리를 해제하는 기능을 만들었다. 만들어진 기능을 검증하기 위해 테스트 코드를 실행할 것이다.
static char * test_insert_end() {
Node* head = NULL;
insert_end(&head, 10);
insert_end(&head, 20);
insert_end(&head, 30);
mu_assert("error: head->data != 10", head->data == 10);
mu_assert("error: head->next->data != 20", head->next->data == 20);
mu_assert("error: head->next->next->data != 30", head->next->next->data == 30);
free_list(head);
return 0;
}
static char * all_tests() {
mu_run_test(test_insert_end);
if (tests_failed > 0) {
return "Some tests failed.";
}
return 0;
}
int tests_run = 0;
int tests_failed = 0;
int main(void) {
char *result = all_tests();
printf("========================================\n");
printf("Tests run: %d\n", tests_run);
printf("Tests passed: %d\n", tests_run - tests_failed);
printf("Tests failed: %d\n", tests_failed);
if (result != 0) {
printf("❌ TESTS FAILED\n");
return 1;
}
printf("✅ ALL TESTS PASSED\n");
return 0;
}위 함수를 실행했을 때
✅ Passed test_insert_end (0.03 ms)
========================================
Tests run: 1
Tests passed: 1
Tests failed: 0
✅ ALL TESTS PASSED위와 같은 결과를 얻었다면 문제없이 구현을 완료한 것이다. 여기까지 구현이 되었으니 이제 더 발전된 기능들을 구현해 보는 것은 다음 포스팅에서 계속 진행하겠다.