개요
이 튜토리얼에서는 C++로 구현된 이중 연결 리스트(doubly linked list)에서 주어진 위치에 있는 노드를 삭제하는 방법을 알아봅니다.
문제 해결 접근 방식
문제를 해결하기 위한 단계는 다음과 같습니다.
구조체 정의: 데이터(
data)와 이전·다음 노드를 가리키는 포인터(prev,next)를 멤버로 가지는 구조체(struct)를 작성합니다.삽입 함수 작성: 이중 연결 리스트에 새 노드를 삽입하는 함수를 작성합니다.
리스트 초기화: 더미(dummy) 데이터로 이중 연결 리스트를 초기화합니다.
삭제할 위치 지정: 삭제할 노드의 위치(position)를 설정합니다.
노드 탐색: 연결 리스트를 순회하면서 주어진 위치에 해당하는 노드를 찾습니다.
삭제 함수 작성: 노드를 삭제하는 함수를 작성합니다. 삭제 시에는 아래 세 가지 경우를 반드시 고려해야 합니다.
헤드(첫 번째) 노드인 경우: 헤드 포인터를 다음 노드로 이동시킵니다.
중간 노드인 경우: 다음 노드를 이전 노드에 연결하여 리스트를 재구성합니다.
마지막 노드인 경우: 이전 노드의 링크를 제거합니다.
예제 코드
전체 코드는 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *prev, *next;
};
void deleteNode(struct Node** head_ref, struct 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);
}
void deleteNodeAtGivenPosition(struct Node** head_ref, int n) {
if (*head_ref == NULL || n <= 0) {
return;
}
struct Node* current = *head_ref;
for (int i = 1; current != NULL && i < n; i++) {
current = current->next;
}
if (current == NULL) {
return;
}
deleteNode(head_ref, current);
}
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->prev = NULL;
new_node->next = (*head_ref);
if ((*head_ref) != NULL) {
(*head_ref)->prev = new_node;
}
(*head_ref) = new_node;
}
void printLinkedList(struct Node* head) {
while (head != NULL) {
cout << head->data << "->";
head = head->next;
}
}
int main() {
struct Node* head = NULL;
insertNode(&head, 5);
insertNode(&head, 2);
insertNode(&head, 4);
insertNode(&head, 8);
insertNode(&head, 10);
cout << "Doubly linked list before deletion" << endl;
printLinkedList(head);
int n = 2;
deleteNodeAtGivenPosition(&head, n);
cout << "\nDoubly linked list after deletion" << endl;
printLinkedList(head);
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
Doubly linked list before deletion
10->8->4->2->5->
Doubly linked list after deletion
10->4->2->5->
마무리
이번 튜토리얼에서는 이중 연결 리스트에서 특정 위치의 노드를 삭제하는 방법을 살펴보았습니다. 핵심은 삭제 대상 노드가 헤드, 중간, 마지막 중 어느 위치에 있느냐에 따라 prev와 next 포인터 연결을 적절히 조정하는 것입니다. 또한 유효하지 않은 위치나 빈 리스트에 대한 예외 처리도 함께 구현하면 더욱 견고한 코드가 됩니다. 궁금한 점이 있다면 댓글로 남겨주세요!