링크드리스트(LinkedList) 구현 (C언어) : Part.5 - reverse_list, sort_list

지금까지 삽입, 삭제, 조회와 같은 기본 적인 구현을 진행했다. 아마 이번 포스팅 내용이 가장 어렵다고 느낄 수 있다. 바로 뒤집기와 정렬이다.

---

1. 구현 목표

• reverse_list : 링크드 리스트의 노드들의 순서를 뒤짚는다.
• sort_list : 링크드 리스트 내부의 값들의 순서를 정렬한다.

---

2. 기능 구현

🔨 reverse_list

링크드 리스트의 순서를 reverse 하기 위해 어떤 작업을 수행해야 할까?

구현 아이디어이다.

1. prev, cur, next라는 노드 포인터 변수를 만들고 각각 NULL, head, NULL로 초기화한다.
2. 현재 노드가 NULL 즉 가장 마지막까지 갈 때까지 while 반복을 진행한다.
3. next 값을 현재 cur 노드의 next 노드로 저장한다.
4. cur 노드의 다음 값을 prev 즉 이전 값으로 설정한다.
5. prev 값은 cur 값이 된다.
6. cur 값에 next 값을 사용한다.

이게 무슨 소리인가 싶을 수 있다. next는 현재 선택된 노드의 다음 값을 나타낸다. cur 값에 현재 노드의 이전 값으로 설정한다. next 는 반복문이 진행되며 원래 이동 방향의 다음 노드를 저장한다는 것이다. 먼저 원래 방향의 다음 값을 저장해 둔 상태에서 cur->next 값을 prev로 지정한다는 것은 cur의 방향을 cur->next 노드에서 prev 노드 즉 이전 노드로 설정한다는 것이다. 

이런 상태에서 prev 값에 cur 값을 cur에 next 값을 저장한다. 즉 링크드 리스트가 왼쪽에서 오른쪽으로 바뀌면서 cur의 next 방향을 하나씩 뒤집는 것이다.

마지막으로 *head 값을 prev로 선택하면 즉 while 반복이 종료되고 가장 마지막 노드에 head를 설정한다는 것이다.

void reverse_list(Node** head) {
    if (*head == NULL) return;

    Node *prev = NULL;
    Node *cur = *head;
    Node *next = NULL;

    while (cur != NULL) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    *head = prev;
}

코드로 보면 위와 같다.

🔨 sort_list

sort_list는 말 그대로 정렬을 하는 함수이다. 그렇다면 링크드리스트를 정렬할 때 어떻게 구현을 해야 할까? 물론 여러 방법이 있을 수 있지만 나는 병합 정렬을 사용하기로 했다.

구현 아이디어

1. slow, fast 노드를 선언한다. slow 노드는 1칸씩 fast 노드는 2칸씩 이동한다. 이는 투 포인터 개념이다. 즉 slow 노드가 1칸 이동할 때 fast노드는 2칸씩 움직인다. 그렇게 fast 노드가 링크드리스트의 끝에 도달했을 때 slow 노드는 링크드 리스트의 중간을 가리킬 것이다.
2. left, right 노드를 이용해 왼쪽과 오른쪽을 나눈다.
3. slow 노드의 다음 값을 NULL로 바꾼다. 즉 노드들 사이의 연결을 끊어 두어야 한다.
4. sort_list(&left), sort_list(&right)를 실행한다. 즉 재귀를 통해 왼쪽 오른쪽의 노드의 크기를 가장 작을 때까지 반복한다.

이 과정을 거치면 모든 노드들이 각각 1개의 노드들로 분해될 것이다. 

이 상태에서

• *head = merge(left, right); 를 이용해 재귀적으로 두 노드를 정렬하기 시작한다.

void sort_list(Node** head) {
    if (*head == NULL || (*head)->next == NULL) return;
    Node* slow = *head;
    Node* fast = *head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    Node* left = *head;
    Node* right = slow->next;
    slow->next = NULL;

    sort_list(&left);
    sort_list(&right);

    *head = merge(left, right);
}

위의 코드는 재귀적으로 노드들을 잘라낸 코드이다. 이제 merge 함수를 구현해 재귀가 끝나 반환되는 노드들을 연결해야 한다.

merge 함수의 구현 아이디어다.

1. 더미 노드를 만든다.
2. tail이라는 노드를 만들고 해당 노드에 더미 노드를 설정한다.
3. left와 right 노드가 사라질 때까지 while 반복을 한다.
4. 조건문 if를 이용해 left 노드의 데이터가 right 노드의 데이터 보다 작은 경우 tail 노드의 next 값으로 left 노드를 선택하고 left 노드를 다음 노드로 밀어낸다.
5. 반대라면 tail노드의 next 값으로 설정하고 right노드를 다음 노드로 밀어낸다.
6. tail 노드를 tail의 next 값으로 설정한다.
7. while 반복이 종료되었는데 left 혹은 right의 노드 값이 남은 경우 tail의 다음 값으로 남은 노드를 연결한다. - 왜 이런 것이냐면 우리는 이미 작은 단위에서부터 노드들을 정렬해 오며 병합하고 있기 때문에 남아 있는 노드는 현재까지 정렬한 노드들보다 큰 값이 있을 수밖에 없다. 그래서 그냥 tail노드의 끝에 연결한 것이다.
8. dumy의 next 값 즉 가짜로 만들었던 dummy 노드의 다음 값인 진짜 노드들만 반환한다.

Node* merge(Node *left, Node *right) {
    Node dummy;
    dummy.next = NULL;
    Node* tail = &dummy;

    while (left && right) {
        if (left->data < right->data) {
            tail->next = left;
            left = left->next;
        }else {
            tail->next = right;
            right = right->next;
        }
        tail = tail->next;
    }
    if (left != NULL) tail->next = left;
    if (right != NULL) tail->next = right;
    return dummy.next;
}

dummy라는 가짜 노드를 사용하고 dummy 노드는 free를 하지 않아도 되는가? 이런 의문이 들 수 있다. 처음 merge 함수를 구현할 때 나 또한 어떻게 구현해야 할지 막막했다. dummy 노드는 createnode를 이용해 진짜 메모리를 할당받은 노드가 아니라 함수 내에서 생성된 지역변수라고 보면 된다. 그래서 이 dummy는 merge 함수가 끝나면 그냥 사라지는 변수가 되는 것이다. 그래서 free를 하지 않아도 된다. 하지만 dummy의 next에 연결된 노드들은 동적 메모리 할당이 된 노드들이다. 그래서 그 노드들은 반환을 해주어야 한다.

---

3. 기능 검증

이제 마지막으로 기능 검증을 하겠다. 이제 주석으로 설정했던 모든 코드들을 해제한다. 그리고 실행하면 된다.

static char * test_reverse_list() {
    Node* head = NULL;
    insert_end(&head, 1);
    insert_end(&head, 2);
    insert_end(&head, 3);
    reverse_list(&head);  // 3 -> 2 -> 1

    mu_assert("reverse_list failed at 1", head->data == 3);
    mu_assert("reverse_list failed at 2", head->next->data == 2);
    mu_assert("reverse_list failed at 3", head->next->next->data == 1);
    free_list(head);
    return 0;
}


static char * test_reverse_single_node() {
    Node* head = NULL;
    insert_end(&head, 42);
    reverse_list(&head);
    mu_assert("reverse single node failed", head != NULL && head->data == 42 && head->next == NULL);
    free_list(head);
    return 0;
}


static char * test_reverse_empty_list() {
    Node* head = NULL;
    reverse_list(&head);  // 아무 문제 없어야 함
    mu_assert("reverse_list on empty list should keep head NULL", head == NULL);
    return 0;
}

static char * test_sort_list() {
    Node* head = NULL;
    insert_end(&head, 30);
    insert_end(&head, 10);
    insert_end(&head, 20);
    sort_list(&head);  // 10 -> 20 -> 30

    mu_assert("sort_list failed at 1", head->data == 10);
    mu_assert("sort_list failed at 2", head->next->data == 20);
    mu_assert("sort_list failed at 3", head->next->next->data == 30);
    mu_assert("sort_list failed: list too long", head->next->next->next == NULL);

    free_list(head);
    return 0;
}


static char * test_sort_empty_list() {
    Node* head = NULL;
    sort_list(&head);  // 아무 문제 없어야 함
    mu_assert("sort_list on empty list should keep head NULL", head == NULL);
    return 0;
}

static char * all_tests() {
    mu_run_test(test_insert_end);
    mu_run_test(test_insert_front);
    mu_run_test(test_delete_node);
    mu_run_test(test_find_node);
    mu_run_test(test_insert_at);
    mu_run_test(test_reverse_list);
    mu_run_test(test_sort_list);
    mu_run_test(test_delete_from_empty_list);
    mu_run_test(test_find_in_empty_list);
    mu_run_test(test_insert_at_out_of_bounds);
    mu_run_test(test_reverse_single_node);
    mu_run_test(test_reverse_empty_list);
    mu_run_test(test_sort_empty_list);

    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;
}

▶ Running test_insert_end...
10 20 30 NULL
✅ Passed test_insert_end (0.02 ms)

▶ Running test_insert_front...
30 20 10 NULL
✅ Passed test_insert_front (0.00 ms)

▶ Running test_delete_node...
✅ Passed test_delete_node (0.00 ms)

▶ Running test_find_node...
✅ Passed test_find_node (0.00 ms)

▶ Running test_insert_at...
✅ Passed test_insert_at (0.01 ms)

▶ Running test_reverse_list...
✅ Passed test_reverse_list (0.00 ms)

▶ Running test_sort_list...
✅ Passed test_sort_list (0.00 ms)

▶ Running test_delete_from_empty_list...
✅ Passed test_delete_from_empty_list (0.00 ms)

▶ Running test_find_in_empty_list...
✅ Passed test_find_in_empty_list (0.00 ms)

▶ Running test_insert_at_out_of_bounds...
[insert_at] Invalid index 3: out of bounds.
✅ Passed test_insert_at_out_of_bounds (0.00 ms)

▶ Running test_reverse_single_node...
✅ Passed test_reverse_single_node (0.00 ms)

▶ Running test_reverse_empty_list...
✅ Passed test_reverse_empty_list (0.00 ms)

▶ Running test_sort_empty_list...
✅ Passed test_sort_empty_list (0.00 ms)

========================================
Tests run: 13
Tests passed: 13
Tests failed: 0
✅ ALL TESTS PASSED

지금까지 구현했던 모든 코드들이 테스트에 통과했다. 다음 포스팅에는 부족했던 부분은 어떤 것이 있는지 어떻게 변경이 되었으면 하는지 일종의 회고 혹은 기능 수정에 대한 내용을 담을 예정이다.