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

C++에서 특정 위치의 연결 리스트 노드 삭제하는 방법

이 튜토리얼에서는 C++를 사용해 단일 연결 리스트(Singly Linked List)에서 주어진 위치의 노드를 삭제하는 방법을 알아봅니다. 먼저 문제 해결 과정을 단계별로 정리한 뒤, 실제로 동작하는 코드까지 함께 살펴보겠습니다.

문제 해결 단계

  • 구조체 정의 – 데이터(data)와 다음 노드를 가리키는 포인터(next)를 멤버로 갖는 구조체를 작성합니다.

  • 삽입 함수 작성 – 새 노드를 연결 리스트에 추가하는 함수를 구현합니다.

  • 연결 리스트 초기화 – 더미 데이터를 이용해 단일 연결 리스트를 만듭니다.

  • 삭제 위치 지정 – 삭제할 노드의 위치(position)를 정합니다.

  • 노드 탐색 – 연결 리스트를 처음부터 순회하며 해당 위치의 노드를 찾습니다.

  • 삭제 함수 작성 – 노드를 삭제할 때는 다음 세 가지 경우를 반드시 고려해야 합니다.

    • 헤드(첫 번째) 노드인 경우 – 헤드 포인터를 다음 노드로 이동시킵니다.

    • 중간 노드인 경우 – 삭제할 노드의 이전 노드를 그다음 노드와 연결합니다.

    • 마지막 노드인 경우 – 이전 노드의 링크를 제거합니다.

예제 코드

아래는 위 과정을 그대로 구현한 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;

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

void insertNode(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

void deleteNode(struct Node** head_ref, int position) {
    if (*head_ref == NULL) {
        return;
    }
    struct Node* temp = *head_ref;
    if (position == 1) {
        *head_ref = temp->next;
        free(temp);
        return;
    }
    for (int i = 1; temp != NULL && i < position - 1; i++) {
        temp = temp->next;
    }
    if (temp == NULL || temp->next == NULL) {
        return;
    }
    struct Node* next = temp->next->next;
    free(temp->next);
    temp->next = next;
}

void printLinkedList(struct Node* node) {
    while (node != NULL) {
        cout << node->data << "->";
        node = node->next;
    }
}

int main() {
    struct Node* head = NULL;
    insertNode(&head, 1);
    insertNode(&head, 2);
    insertNode(&head, 3);
    insertNode(&head, 4);
    insertNode(&head, 5);
    cout << "Linked list before deletion:" << endl;
    printLinkedList(head);
    deleteNode(&head, 1);
    cout << "\nLinked list after deletion:" << endl;
    printLinkedList(head);
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

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

코드 동작 원리

핵심 로직은 deleteNode 함수에 있습니다.

  • 연결 리스트가 비어 있으면(*head_ref == NULL) 아무 작업 없이 종료합니다.

  • 삭제할 위치가 1이면 헤드 노드를 가리키므로, 헤드를 다음 노드로 옮긴 뒤 기존 헤드의 메모리를 free()로 해제합니다.

  • 그 외의 경우에는 삭제할 노드의 바로 앞 노드까지 이동한 다음, 앞 노드의 next를 삭제 대상의 다음 노드로 건너뛰어 연결하고 대상 노드의 메모리를 해제합니다.

  • 요청한 위치가 리스트 길이를 벗어나면 temp 또는 temp->next가 NULL이 되어 안전하게 종료되므로 잘못된 접근이 발생하지 않습니다.

시간 복잡도

노드 삭제를 위해 최악의 경우 리스트 전체를 순회해야 하므로 시간 복잡도는 O(n)이며, 추가 메모리를 거의 사용하지 않으므로 공간 복잡도는 O(1)입니다.

마무리

이번 튜토리얼에서는 C++로 단일 연결 리스트에서 특정 위치의 노드를 삭제하는 방법을 배웠습니다. 헤드, 중간, 마지막 노드 세 가지 경우만 정확히 처리하면 어렵지 않게 구현할 수 있습니다. 내용 중 궁금한 점이 있다면 댓글로 남겨주세요!