링크드리스트(LinkedList) 구현 (C언어) : Part.4 - delete_node, insert_at

4번째 포스팅이다. 이번 포스팅에서는 노드를 삭제하는 delete_node와 특정 인덱스 위치에 노드를 삽입하는 insert_at 기능을 구현해 보려고 한다.

---

1. 구현 목표

• insert_at : 링크드 리스트의 중간 원하는 인덱스에 데이터를 추가한다.
• delete_node : 원하는 값이 있는 노드를 링크드리스트에서 삭제한다.

이번 구현은 이전과 비교해 조금 복잡하게 느껴질 수 있다.

---

2. 기능 구현

🔨 insert_at

링크드 리스트의 특정 index 위치에 data를 가지는 node를 추가해야 한다.

구현 아이디어

1. 새로운 노드를 먼저 생성해 둔다.
2. 만약 index 값이 0 이라면 이 전에 구현했던 insert_front와 같이 추가를 하면 된다.
3. 현재 노드를 지정할 cur 변수를 만들고 head로 지정한다.
4. count라는 int 변수를 생성한다. 이 변수는 원하는 index 위치까지 반복하도록 도와준다.
5. while 문을 이용해 반복하면서 count 값이 index - 1 값보다 작은 즉 index - 1 위치에 도달할 때까지 반복한다. 추가로 cur 이 NULL 이 되면 반복문을 종료하는 코드를 추가한다.
6. cur이 NULL이 되었다는 것인 링크드 리스트 내부를 전부 돌았는데도 원하는 인덱스 위치를 얻지 못했다는 것이니 반환을 한다. 이때 처음에 생성했던 노드를 ‼️ free로 해제해야 한다. ‼️
7. 이 모든 조건을 넘어갔다면 즉 원하는 index 위치를 찾았을 경우 새로 만든 노드의 다음 값을 cur-> next 값으로 설정한다. 즉 cur 노드와 cur->next 노드 사이에 새로운 노드를 연결한다는 것이다.

void insert_at(Node** head, int index, int data) {
    Node* newNode = create_node(data);
    if (newNode == NULL) {
        return;
    }
    if (index == 0){
        newNode->next = *head;
        *head = newNode;
        return;
    }
    int count = 0;
    Node* cur = *head;

    while (cur != NULL && count < index - 1) {
        cur = cur->next;
        count++;
    }

    // index가 리스트 길이보다 클 경우 처리
    if (cur == NULL) {
    	printf("[insert_at] Invalid index %d: out of bounds.\n", index);
        free(newNode);  // 사용 안 하므로 메모리 해제
        return;
    }

    newNode->next = cur->next;
    cur->next = newNode;
}

🔨 delete_node

노드를 삭제하는 함수를 구현할 것이다.

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

1. 노드 삭제에는 cur 외에도 prev 라는 Node 타입의 포인터 변수를 사용한다.
2. cur 값을 이용해 while 반복을 한다.
3. 반복문 안에 조건문 if를 사용해 현재 노드의 data 값이 삭제하려는 data값과 같은지 검사한다.
4. prev 값은 이전 노드를 지정하는 변수이다.
5. 조건 문 내에 원하는 값을 찾았는데 prev 값이 NULL이라면 링크드 리스트의 가장 처음에서 발견된 것이니 링크드 리스트의 head를 cur->next로 설정한다.
6. prev 가 NULL이 아니라는 것은 발견된 노드가 링크드 리스트 시작 이후에 발견된 것이니 이전 노드의 다음 값을 현재 노드의 다음 값으로 설정해 현재 노드를 가리키는 노드를 제거한다.
7. 삭제 과정은 free_list 함수와 같이 temp를 이용해 진행한다.;
8. free를 통해 노드의 메모리를 해제한다.
9. prev의 값을 현재 노드로
10. cur 노드의 값을 cur->next으로 설정한다.

void delete_node(Node** head, int data) {
    if (*head == NULL) return;
    Node* cur = *head;
    Node* prev = NULL;

    while (cur != NULL) {
        if (cur->data == data) {
            if (prev == NULL) {
                *head = cur->next;
            }else {
                prev->next = cur->next;
            }
            Node* temp = cur;
            cur->next = NULL;
            free(temp);
            return;
        }
        prev = cur;
        cur = cur->next;
    }
}

---

3. 기능 검증

이제 구현한 기능들을 검증할 시간이다. 이 전처럼 해당되는 테스트 코드의 주석을 해제하고 테스트를 하면 된다.

static char * test_delete_node() {
    Node* head = NULL;
    insert_end(&head, 10);
    insert_end(&head, 20);
    insert_end(&head, 30);
    delete_node(&head, 20);
    // 리스트: 10 -> 30

    mu_assert("delete_node failed at head", head->data == 10);
    mu_assert("delete_node failed at 2nd", head->next->data == 30);
    mu_assert("delete_node failed: list too long", head->next->next == NULL);
    free_list(head);
    return 0;
}

static char * test_delete_from_empty_list() {
    Node* head = NULL;
    delete_node(&head, 10);  // 아무 일도 없어야 함
    mu_assert("delete_node on empty list should keep head NULL", head == NULL);
    return 0;
}

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

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


static char * test_insert_at_out_of_bounds() {
    Node* head = NULL;
    insert_at(&head, 3, 100);  // 인덱스 3은 잘못된 위치, 아무 일도 없어야 함
    mu_assert("insert_at out of bounds should not modify list", 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_delete_from_empty_list);
    mu_run_test(test_find_in_empty_list);
    mu_run_test(test_insert_at_out_of_bounds);

    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.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)

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

위와 같은 결과가 나오면 정상적으로 구현이 된 것이다.