Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 연결 리스트에서 교대 노드 삭제하기

이 튜토리얼에서는 C++를 사용하여 단일 연결 리스트(singly linked list)에서 교대 노드(alternate node), 즉 두 번째, 네 번째처럼 한 칸씩 건너뛰며 위치한 노드들을 삭제하는 방법을 배워보겠습니다.

문제 해결 접근 방식

문제를 해결하기 위한 단계는 다음과 같습니다.

  • 데이터(data)와 다음 노드 포인터(next)를 멤버로 갖는 구조체(struct)를 정의합니다.
  • 단일 연결 리스트에 새 노드를 삽입하는 함수를 작성합니다.
  • 테스트용 더미 데이터로 연결 리스트를 초기화합니다.
  • 연결 리스트를 순회하면서 이전 노드(prev)를 추적합니다.
  • 이전 노드 정보를 활용해 교대 노드를 삭제합니다.
  • 노드를 삭제하는 전용 함수를 작성합니다. 노드를 삭제할 때는 아래 세 가지 경우를 반드시 고려해야 합니다.
    • 헤드(첫 번째) 노드인 경우: 헤드 포인터를 다음 노드로 이동시킵니다.
    • 중간 노드인 경우: 이전 노드와 다음 노드를 서로 연결합니다.
    • 마지막 노드인 경우: 이전 노드의 링크(next 포인터)를 제거합니다.

구현 코드

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node *next;
};
void deleteAlternateNodes(Node *head) {
    if (head == NULL)
        return;
    Node *prev = head;
    Node *node = head->next;
    while (prev != NULL && node != NULL) {
        prev->next = node->next;
        free(node);
        prev = prev->next;
        if (prev != NULL) {
            node = prev->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 *node) {
    while (node != NULL) {
        cout << node->data << " -> ";
        node = node->next;
    }
}
int main() {
    Node* head = NULL;
    insertNode(&head, 1);
    insertNode(&head, 2);
    insertNode(&head, 3);
    insertNode(&head, 4);
    insertNode(&head, 5);
    insertNode(&head, 6);
    cout << "Linked List before deletion:" << endl;
    printLinkedList(head);
    deleteAlternateNodes(head);
    cout << "\nLinked List after deletion:" << endl;
    printLinkedList(head);
    return 0;
}

동작 원리

deleteAlternateNodes 함수의 핵심 로직은 다음과 같습니다.

  1. prev 포인터가 헤드 노드를, node 포인터가 그다음 노드를 가리키도록 초기화합니다.
  2. prev->next = node->next;를 통해 현재 검사 중인 노드를 리스트에서 분리합니다.
  3. free(node);로 분리된 노드의 메모리를 해제하여 메모리 누수를 방지합니다.
  4. prev를 다음 남은 노드로 이동시키고, 해당 노드의 다음 노드를 다시 node로 설정한 뒤 과정을 반복합니다.

이렇게 하면 첫 번째, 세 번째, 다섯 번째 노드만 남고 나머지 노드들이 순서대로 제거됩니다.

실행 결과

위 프로그램을 실행하면 다음과 같은 결과를 확인할 수 있습니다.

Linked List before deletion:
6 -> 5 -> 4 -> 3 -> 2 -> 1 ->
Linked List after deletion:
6 -> 4 -> 2 ->

마무리

이번 튜토리얼에서는 C++로 단일 연결 리스트의 교대 노드를 삭제하는 방법을 살펴보았습니다. 시간 복잡도는 O(n)으로 리스트를 한 번만 순회하면 되기 때문에 매우 효율적입니다. 튜토리얼 내용에 대해 궁금한 점이 있다면 댓글로 남겨주세요.