C++에서 연결 리스트의 M개 노드 다음에 N개 노드 삭제하는 방법

문제 소개

연결 리스트(Linked List)는 각 노드가 데이터와 다음 노드를 가리키는 포인터로 구성된 자료구조입니다. 이 글에서는 리스트를 순회하면서 M개의 노드를 지난 직후, 이어지는 N개의 노드를 반복적으로 삭제하는 방법을 C++ 코드와 함께 단계별로 살펴보겠습니다.

1단계: 연결 리스트 구조 정의

먼저 데이터(int data)와 다음 노드를 가리키는 포인터(next)를 멤버로 가지는 노드 구조체를 정의합니다.

struct Node {
    int data;
    struct Node* next;
};

2단계: 노드 추가 함수 작성

createList(Node **headPtr, int new_data) 함수는 노드를 가리키는 이중 포인터와 정수 값을 매개변수로 받습니다. 함수 내부에서는 새로 생성된 노드의 next 포인터가 기존 헤드를 가리키도록 설정한 뒤, headPtr이 새 노드를 가리키도록 갱신하여 리스트 맨 앞에 노드를 삽입합니다.

void createList(Node ** headPtr, int new_data){
    Node* newNode = new Node();
    newNode->data = new_data;
    newNode->next = (*headPtr);
    (*headPtr) = newNode;
}

3단계: N개 노드 삭제 함수 구현

deleteNnodesAfterM(Node *head, int M, int N) 메서드는 헤드 노드와 M, N 값을 인자로 받습니다. 함수 내부에서는 Node* current에 헤드를 저장하고, 임시 포인터로 사용할 Node *t를 함께 선언합니다.

void deleteNnodesAfterM(Node *head, int M, int N){
    Node *current = head, *t;
    int nodeCount;

이어서 current가 NULL을 가리키지 않는 동안 반복 실행되는 while 루프가 등장합니다. 첫 번째 for 루프는 M번 반복되며, 루프가 종료되면 current 포인터는 리스트에서 M번째 노드 위치에 머무르게 됩니다. 이후 Node *t에는 current->next 값이 할당되는데, 이것이 바로 삭제 대상이 되는 첫 번째 노드입니다.

while (current){
    for (nodeCount = 1; nodeCount < M && current!= NULL; nodeCount++)
    current = current->next;
    if (current == NULL)
        return;
    t = current->next;

두 번째 for 루프는 N번 반복되면서 해당 지점부터 N개의 노드를 차례로 메모리에서 해제(free)합니다. 삭제가 모두 끝나면 current->next에 t를 연결하고, current를 t로 옮겨 다음 구간에 대해 같은 과정을 반복합니다.

for (nodeCount = 1; nodeCount<=N && t!= NULL; nodeCount++){
    Node *temp = t;
    t = t->next;
    free(temp);
}
current->next = t;
current = t;

4단계: 리스트 출력 함수

마지막으로 헤드 포인터를 받아 전체 연결 리스트를 화면에 출력하는 printList(Node *head) 함수를 작성합니다.

void printList(Node *head){
    Node *temp = head;
    while (temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
    cout<<endl;
}

전체 구현 예제

지금까지 설명한 내용을 바탕으로, 연결 리스트에서 M개 노드 다음의 N개 노드를 삭제하는 전체 프로그램은 아래와 같습니다.

#include <iostream>
using namespace std;
struct Node{
    int data;
    Node *next;
};
void createList(Node ** headPtr, int new_data){
    Node* newNode = new Node();
    newNode->data = new_data;
    newNode->next = (*headPtr);
    (*headPtr) = newNode;
}
void printList(Node *head){
    Node *temp = head;
    while (temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
    cout<<endl;
}
void deleteNnodesAfterM(Node *head, int M, int N){
    Node *current = head, *t;
    int nodeCount;
    while (current){
        for (nodeCount = 1; nodeCount < M && current!= NULL; nodeCount++)
        current = current->next;
        if (current == NULL)
        return;
        t = current->next;
        for (nodeCount = 1; nodeCount<=N && t!= NULL; nodeCount++){
            Node *temp = t;
            t = t->next;
            free(temp);
        }
        current->next = t;
        current = t;
    }
}
int main(){
    Node* head = NULL;
    int M=2, N=2;
    createList(&head, 2);
    createList(&head, 4);
    createList(&head, 6);
    createList(&head, 8);
    createList(&head, 10);
    createList(&head, 12);
    createList(&head, 14);
    cout << "M = " << M<< " N = " << N<<endl;
    cout<< "Original linked list :"<<endl;
    printList(head);
    deleteNnodesAfterM(head, M, N);
    cout<<"Linked list after deletion :"<<endl;
    printList(head);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

M = 2 N = 2

Original linked list :
14 12 10 8 6 4 2

Linked list after deletion :
14 12 6 4

정리 및 복잡도 분석

이 알고리즘은 리스트를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 별도의 추가 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다. 또한 M 또는 N이 실제 리스트 길이보다 큰 경우에도 NULL 검사를 통해 프로그램이 안전하게 종료되도록 처리했다는 점이 특징입니다.