C++로 구현하는 연결 리스트: M개 노드 이후 N개 노드 삭제하기

이 튜토리얼에서는 연결 리스트(Linked List)에서 M개 노드를 건너뛴 후 이어지는 N개 노드를 삭제하는 방법을 알아보겠습니다. 문제 해결 절차를 단계별로 살펴본 뒤, 실제 동작하는 C++ 코드와 실행 결과까지 확인해 보겠습니다.

문제 해결 접근 방식

• 연결 리스트의 노드를 나타내는 Node 구조체(struct)를 정의합니다.
• 더미 데이터로 연결 리스트를 초기화합니다.
• M개 노드 이후에 N개 노드를 삭제하는 함수를 작성합니다.
  • 헤드(head) 포인터로 현재 위치 포인터를 초기화합니다.
  • 연결 리스트의 끝에 도달할 때까지 반복문을 수행합니다.
  • M개 노드만큼 포인터를 앞으로 이동시킵니다.
  • 이어지는 N개 노드를 삭제하고 메모리를 해제합니다.
  • 포인터를 다음 노드로 이동하여 과정을 반복합니다.
• 삭제 후 결과를 출력하여 확인합니다.

예제 코드

전체 소스 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node *next;
};
void insertNode(Node ** head_ref, int new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = (*head_ref);
    *head_ref = new_node;
}
void printLinkedList(Node *head) {
    Node *temp = head;
    while (temp != NULL) {
        cout<< temp->data << " -> ";
        temp = temp->next;
    }
    cout << "Null" << endl;
}
void deleteNNodesAfterMNodes(Node *head, int M, int N) {
    Node *current = head, *temp;
    int count;
    while (current) {
        // M개 노드 건너뛰기
        for (count = 1; count < M && current!= NULL; count++) {
            current = current->next;
        }
        // 연결 리스트의 끝에 도달한 경우
        if (current == NULL) {
            return;
        }
        // M개 노드 이후의 N개 노드 삭제
        temp = current->next;
        for (count = 1; count <= N && temp != NULL; count++) {
            Node *deletingNode = temp;
            temp = temp->next;
            free(deletingNode);
        }
        current->next = temp;
        current = temp;
    }
}
int main() {
    Node* head = NULL;
    int M = 1, N = 2;
    insertNode(&head, 1);
    insertNode(&head, 2);
    insertNode(&head, 3);
    insertNode(&head, 4);
    insertNode(&head, 5);
    insertNode(&head, 6);
    insertNode(&head, 7);
    insertNode(&head, 8);
    insertNode(&head, 9);
    cout << "Linked list before deletion: ";
    printLinkedList(head);
    deleteNNodesAfterMNodes(head, M, N);
    cout << "Linked list after deletion: ";
    printLinkedList(head);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다. M=1, N=2 조건에서는 노드 하나를 남긴 뒤 두 개씩 삭제하는 패턴이 적용됩니다.

Linked list before deletion: 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> Null
Linked list after deletion: 9 -> 6 -> 3 -> Null

동작 원리 정리

핵심 로직은 크게 두 부분으로 나눌 수 있습니다. 첫째, 유지 단계에서는 현재 노드부터 M-1번 다음 노드로 이동하여 유지할 구간을 확보합니다. 둘째, 삭제 단계에서는 임시 포인터(temp)를 활용해 N개 노드를 순회하면서 각 노드의 메모리를 free()로 해제한 후, 마지막에 유지된 노드의 next 포인터를 삭제되지 않은 노드에 연결합니다. 이 과정을 리스트 끝까지 반복하면 원하는 패턴대로 노드가 제거됩니다.

마무리

이 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨 주세요. 연결 리스트의 다양한 변형 문제(예: 홀수·짝수 위치 재배열, 중간 노드 삭제 등)도 함께 학습하면 자료구조 실력을 더욱 탄탄히 다질 수 있습니다.