연결 리스트가 주어졌을 때, 리스트의 첫 번째 요소를 제거하고 새로운 리스트의 헤드(head) 포인터를 반환하는 것이 이번 문제의 목표입니다.
입력 : 1 -> 2 -> 3 -> 4 -> 5 -> NULL
출력 : 2 -> 3 -> 4 -> 5 -> NULL
입력 : 2 -> 4 -> 6 -> 8 -> 33 -> 67 -> NULL
출력 : 4 -> 6 -> 8 -> 33 -> 67 -> NULL
즉, 리스트의 첫 번째 노드를 제거한 뒤, 헤드를 두 번째 요소로 이동시키고 그 헤드를 반환해야 합니다.
문제 해결 접근 방식
이 문제는 매우 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
헤드를 다음 노드로 이동시킨 후, 기존의 첫 번째 노드를 메모리에서 해제(delete)하면 됩니다.
이때 주의할 점은, 헤드를 옮기기 전에 반드시 임시 포인터에 기존 헤드를 저장해 두어야 한다는 것입니다. 그렇지 않으면 첫 번째 노드의 주소를 잃어버려 메모리 누수(memory leak)가 발생할 수 있습니다.
예제 코드
#include <iostream>
using namespace std;
/* 연결 리스트 노드 구조체 */
struct Node {
int data;
struct Node* next;
};
void push(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() {
Node* head = NULL;
push(&head, 12);
push(&head, 29);
push(&head, 11);
push(&head, 23);
push(&head, 8);
auto temp = head; // temp가 현재 헤드(첫 번째 노드)를 가리킴
head = head -> next; // 헤드를 다음 요소로 이동
delete temp; // temp, 즉 첫 번째 노드를 삭제
for (temp = head; temp != NULL; temp = temp->next) // 새 리스트 출력
cout << temp->data << " ";
return 0;
}
실행 결과
23 11 29 12
코드 설명
이 프로그램의 동작 순서는 다음과 같습니다.
먼저 push 함수를 통해 리스트 앞쪽에 데이터를 차례로 삽입합니다. 그다음 임시 포인터 temp가 현재 헤드(첫 번째 노드)를 가리키도록 하고, 헤드를 다음 노드로 이동시킵니다. 마지막으로 delete를 통해 기존의 첫 번째 노드를 메모리에서 해제한 뒤, 새로운 리스트를 출력합니다.
이 프로그램의 전체 시간 복잡도는 O(1)입니다. 즉, 실행 시간이 입력 크기에 전혀 의존하지 않으며, 단일 노드 삭제 작업으로 달성할 수 있는 최적의 성능입니다.
참고: 빈 리스트 처리
실제 구현에서는 리스트가 비어 있는 경우(head == NULL)를 먼저 확인하는 것이 안전합니다. 빈 리스트에 대해 head->next에 접근하면 런타임 오류가 발생할 수 있기 때문입니다.
마무리
이번 글에서는 연결 리스트의 첫 번째 노드를 제거하는 문제를 다루었습니다. C++로 작성된 예제 코드와 함께, 헤드 포인터를 활용한 문제 해결 과정을 단계별로 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분의 학습에 도움이 되기를 바랍니다.