개요
이 튜토리얼에서는 C++를 사용하여 단일 연결 리스트(Singly Linked List)에서 값이 x보다 큰 모든 노드를 삭제하는 방법을 알아봅니다.
리스트를 처음부터 끝까지 한 번만 순회하며 조건에 맞는 노드를 제거하면 되므로, 시간 복잡도는 O(n), 공간 복잡도는 O(1)입니다. 그럼 문제 해결 과정을 단계별로 살펴보겠습니다.
문제 해결 단계
노드 구조체 정의: 데이터(data)와 다음 노드를 가리키는 포인터(next)를 멤버로 갖는 구조체를 작성합니다.
노드 삽입 함수 작성: 새 노드를 생성해 단일 연결 리스트에 삽입하는 함수를 작성합니다.
리스트 초기화: 더미 데이터를 사용해 단일 연결 리스트를 초기화합니다.
순회 및 조건 검사: 연결 리스트를 순회하면서 현재 노드의 데이터가 x보다 큰지 확인합니다.
노드 삭제: 현재 데이터가 x보다 크면 해당 노드를 삭제합니다.
삭제 함수 구현: 노드를 삭제할 때는 아래 세 가지 경우를 반드시 고려해야 합니다.
헤드(첫 번째) 노드인 경우: 헤드 포인터를 다음 노드로 이동시킨 뒤 기존 헤드 노드를 제거합니다.
중간 노드인 경우: 이전 노드의 next 포인터를 다음 노드에 연결합니다.
마지막 노드인 경우: 이전 노드의 링크(next 포인터)를 정리하여 리스트의 끝을 유지합니다.
예제 코드
위의 단계를 구현한 전체 코드입니다.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* getNewNode(int data) {
Node* newNode = new Node;
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void deleteGreaterNodes(Node** head_ref, int x) {
Node *temp = *head_ref, *prev;
if (temp != NULL && temp->data > x) {
*head_ref = temp->next;
free(temp);
temp = *head_ref;
}
while (temp != NULL) {
while (temp != NULL && temp->data <= x) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) {
return;
}
prev->next = temp->next;
delete temp;
temp = prev->next;
}
}
void printLinkedList(Node* head) {
while (head) {
cout << head->data << " -> ";
head = head->next;
}
}
int main() {
Node* head = getNewNode(1);
head->next = getNewNode(2);
head->next->next = getNewNode(3);
head->next->next->next = getNewNode(4);
head->next->next->next->next = getNewNode(5);
head->next->next->next->next->next = getNewNode(6);
int x = 3;
cout << "Linked List before deletion:" << endl;
printLinkedList(head);
deleteGreaterNodes(&head, x);
cout << "\nLinked List after deletion:" << endl;
printLinkedList(head);
return 0;
}
코드 동작 원리
deleteGreaterNodes 함수는 먼저 헤드 노드가 x보다 큰지 검사하여, 크다면 헤드를 다음 노드로 옮기고 기존 노드의 메모리를 해제합니다. 이후 리스트를 순회하면서 데이터가 x보다 큰 노드를 만나면, 이전 노드(prev)의 next 포인터를 삭제 대상 노드의 다음 노드에 연결한 뒤 메모리를 해제합니다. 이렇게 하면 헤드, 중간, 마지막 노드 등 모든 위치의 노드를 안전하게 처리할 수 있습니다.
실행 결과
위 프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다.
Linked List before deletion: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> Linked List after deletion: 1 -> 2 -> 3 ->
x의 값이 3이므로, 3보다 큰 값(4, 5, 6)을 가진 노드들이 모두 제거되고 나머지 노드만 남은 것을 확인할 수 있습니다.
마무리
이번 튜토리얼에서는 단일 연결 리스트를 한 번의 순회만으로 특정 값보다 큰 노드들을 효율적으로 삭제하는 방법을 배웠습니다. 헤드 노드, 중간 노드, 마지막 노드라는 세 가지 경우만 꼼꼼히 처리하면 어떤 위치의 노드든 안전하게 제거할 수 있습니다. 내용에 대해 궁금한 점이 있다면 댓글로 남겨 주세요.