링크드리스트(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를 반환하게 된다. 코드의 순서로 보면

1. 새로운 노드를 생성한다.
2. 노드가 정상적으로 생성됬는지 확인하고 그렇지 않으면 NULL을 반환한다.
3. 노드가 정상적으로 생성되었다면 구조체 포인터를 활용해 Node의 data에 인자로 받았던 data 값을 설정한다.
4. 노드는 현재 새로 생성된 상태이기 때문에 next 값을 NULL로 설정한다.
5. 생성된 노드를 반환한다.

시작은 매우 간단하다.

🔨 insert_end 함수 구현

이제 insert_end 함수를 구현할 것이다.

void insert_end(Node** head, int data) {

}

이 안에 내용을 추가할 예정이다.

구현의 핵심 아이디어는 다음과 같다.

1. create_node() 함수를 이용해 새로운 노드를 생성한다.
2. 새로 생성된 노드가 있는지 체크해서 없다면 return을 통해 반환한다.
3. head 노드 즉 링크드 리스트의 시작점이 비어있는 경우 즉 리스트에 노드가 없는 경우에는 새로 만들어진 노드를 설정하고 즉시 반환한다.
4. 노드가 비어있지 않은 상태 즉 연결된 노드들이 있는 경우 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) {

}

위 함수를 채워 넣겠다.

구현의 핵심 아이디어는 다음과 같다.

1. temp 노드에 현재 노드를 담는다.
2. 헤드를 현재 헤드의 다음 노드로 변경한다.
3. 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

위와 같은 결과를 얻었다면 문제없이 구현을 완료한 것이다. 여기까지 구현이 되었으니 이제 더 발전된 기능들을 구현해 보는 것은 다음 포스팅에서 계속 진행하겠다.