개요
이 튜토리얼에서는 단일 연결 리스트(Singly Linked List)에서 헤드 포인터 없이 노드를 삭제하는 방법을 알아봅니다. 일반적으로 연결 리스트에서 노드를 삭제하려면 이전 노드에 접근할 수 있어야 하지만, 헤드 포인터가 주어지지 않은 상황에서는 전혀 다른 접근 방식이 필요합니다.
핵심 아이디어와 문제 해결 단계
여기서 핵심은 삭제하려는 노드 자체를 지우는 대신, 다음 노드의 데이터를 현재 노드로 복사한 뒤 다음 노드를 제거하는 것입니다. 그러면 결과적으로 해당 위치의 노드가 삭제된 것과 같은 효과를 얻을 수 있습니다. 문제를 해결하는 단계는 다음과 같습니다.
data필드와next포인터를 가진 구조체(struct)를 정의합니다.연결 리스트에 노드를 삽입하는 함수를 작성합니다.
더미(dummy) 데이터로 연결 리스트를 초기화합니다.
next포인터를 사용해 연결 리스트에서 삭제할 노드를 가져옵니다.다음 노드의 데이터를 복사한 후, 다음 노드를 메모리에서 해제(free)합니다.
예제 코드
전체 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void deleteNodeWithoutHead(struct Node* deletingNode) {
if (deletingNode == NULL) {
return;
}
else {
if (deletingNode->next == NULL) {
cout << "Can't delete last node without head" << endl;
return;
}
struct Node* temp = deletingNode->next;
deletingNode->data = temp->data;
deletingNode->next = temp->next;
free(temp);
}
}
void printLinkedList(Node* head) {
Node* temp = head;
while (temp) {
cout << temp->data << " -> ";
temp = temp->next;
}
}
void insertNode(struct Node** head_ref, int new_data) {
struct Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int main() {
struct 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);
Node* del = head->next;
deleteNodeWithoutHead(del);
cout << "\nLinked List after deletion:" << endl;
printLinkedList(head);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Linked List before deletion: 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> Linked List after deletion: 6 -> 4 -> 3 -> 2 -> 1 ->
출력 결과에서 5가 사라진 것을 확인할 수 있습니다. del 포인터가 가리키던 노드(값 5)의 데이터가 다음 노드의 값으로 덮어 쓰이고, 원래 값 5를 가졌던 다음 노드가 메모리에서 해제되었기 때문입니다.
동작 원리와 한계
이 기법은 추가적인 순회 없이 O(1) 시간 복잡도로 노드를 삭제할 수 있어 매우 효율적이며, 코딩 인터뷰에서 자주 등장하는 클래식한 문제이기도 합니다. 다만 몇 가지 한계가 있습니다. 첫째, 삭제하려는 노드가 마지막 노드인 경우에는 적용할 수 없습니다. 마지막 노드의 next는 NULL이므로 복사해 올 데이터가 없기 때문이며, 위 코드에서도 이 경우 안내 메시지를 출력하고 종료합니다. 둘째, 노드에 저장된 값이 아니라 노드 객체 자체가 외부에서 참조되고 있는 구조라면 데이터 복사 방식이 의도치 않은 부작용을 일으킬 수 있습니다.
마무리
지금까지 헤드 포인터 없이 연결 리스트의 노드를 삭제하는 방법을 알아보았습니다. 이 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.