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

C++ 이중 연결 리스트에서 노드 삭제하는 방법

이 튜토리얼에서는 C++를 사용하여 이중 연결 리스트(doubly linked list)에서 노드를 삭제하는 방법을 알아보겠습니다.

문제 해결 단계

  • 데이터(data)와 prev, next 포인터를 가지는 구조체(struct)를 정의합니다.

  • 새로운 노드를 이중 연결 리스트에 삽입하는 함수를 작성합니다.

  • 더미(dummy) 데이터를 사용해 이중 연결 리스트를 초기화합니다.

  • 삭제할 노드를 지정합니다.

  • 노드를 삭제하는 함수를 작성합니다. 삭제 시에는 아래의 세 가지 경우를 반드시 고려해야 합니다.

    • 헤드(head) 노드인 경우: 헤드 포인터를 다음 노드로 이동시킵니다.
    • 중간 노드인 경우: 다음 노드를 이전 노드에 연결하여 리스트의 흐름을 유지합니다.
    • 마지막(end) 노드인 경우: 이전 노드의 next 링크만 제거하면 됩니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node *prev, *next;
};
void deleteNode(Node** head_ref, Node* del) {
    if (*head_ref == NULL || del == NULL) {
        return;
    }
    if (*head_ref == del) {
        *head_ref = del->next;
    }
    if (del->next != NULL) {
        del->next->prev = del->prev;
    }
    if (del->prev != NULL) {
        del->prev->next = del->next;
    }
    free(del);
    return;
}
void insertNode(Node** head_ref, int new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->prev = NULL;
    new_node->next = (*head_ref);
    if ((*head_ref) != NULL) {
        (*head_ref)->prev = new_node;
    }
    (*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);
    cout << "Linked List before deletion:" << endl;
    printLinkedList(head);
    deleteNode(&head, head->next);
    cout << "\nLinked List after deletion:" << endl;
    printLinkedList(head);
    return 0;
}

코드 설명

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

  1. 유효성 검사: 리스트가 비어 있거나(*head_ref == NULL) 삭제 대상이 없으면(del == NULL) 즉시 함수를 종료합니다.
  2. 헤드 처리: 삭제할 노드가 헤드 노드라면 헤드 포인터를 다음 노드로 변경합니다.
  3. 연결 재구성: 삭제 노드의 앞 노드와 뒤 노드가 서로를 직접 가리키도록 prev, next 포인터를 갱신합니다. 이 과정은 노드가 중간에 있든 끝에 있든 자동으로 처리됩니다.
  4. 메모리 해제: free()를 호출하여 삭제된 노드가 차지하던 메모리를 반환합니다.

출력 결과

위 프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다. 두 번째 노드(값 4)가 삭제되어 리스트에서 제거된 것을 확인할 수 있습니다.

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

마무리

이번 글에서는 이중 연결 리스트에서 노드를 삭제하는 세 가지 경우(헤드, 중간, 끝)를 모두 하나의 함수로 처리하는 방법을 살펴보았습니다. 이 로직은 실무에서도 자주 활용되는 기본 패턴이므로 직접 코드를 작성해 보며 익혀두는 것을 추천합니다. 튜토리얼 내용에 대해 궁금한 점이 있다면 댓글로 남겨주세요.