단일 연결 리스트(singly linked list)가 주어졌을 때, 이 리스트에서 마지막 노드를 삭제하는 것이 우리의 과제입니다. 이 문제는 주어진 리스트를 처음부터 끝까지 순회하면서 마지막 노드를 찾아 제거하는 방식으로 간단하게 해결할 수 있습니다.
문제 해결 접근 방법
이 접근 방식에서는 리스트를 순회하면서 이전 노드(prev)와 현재 노드(curr)를 함께 추적합니다. 현재 노드가 마지막 노드에 도달하면, 이전 노드의 next 포인터를 NULL로 변경한 뒤 현재 노드의 메모리를 해제(delete)하면 됩니다.
예제 코드
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void push(struct Node** ref, int new_data) { // 노드를 삽입하는 함수
struct Node* new_n = new Node;
new_n->data = new_data;
new_n->next = (*ref);
(*ref) = new_n;
}
int main() {
Node* head = NULL;
push(&head, 12);
push(&head, 29);
push(&head, 11);
push(&head, 23);
push(&head, 8);
auto curr = head, prev = head;
if (!curr || !curr -> next) // 리스트가 비어 있거나 노드가 하나뿐인 경우
cout << "Empty\n";
else {
while (curr) { // curr != NULL인 동안 반복
if (!curr -> next) {
prev -> next = NULL;
delete(curr); // 메모리 해제
break;
}
prev = curr;
curr = curr -> next; // 다음 노드로 이동
}
}
for (Node* temp = head; temp != NULL; temp = temp->next) // 데이터 출력
cout << temp->data << " ";
return 0;
}
실행 결과
8 23 11 29
코드 설명
위 코드는 리스트를 순회하면서 현재 노드와 이전 노드를 계속 추적합니다. 현재 노드가 마지막 노드가 되는 순간, 이전 노드의 next를 NULL로 설정하고 현재 노드를 삭제합니다. 또한 리스트가 비어 있거나 노드가 하나뿐인 경우에는 별도로 처리하여 안정성을 높였습니다.
프로그램의 전체 시간 복잡도는 O(N)이며, 여기서 N은 연결 리스트의 크기(노드 개수)입니다.
시간 복잡도: O(N)
N: 연결 리스트의 크기
마무리
이번 글에서는 주어진 연결 리스트에서 마지막 노드를 삭제하는 방법을 알아보았습니다. C++ 구현 코드와 함께 전체 풀이 과정을 살펴보았으며, 동일한 로직은 C, Java, Python 등 다른 언어로도 손쉽게 작성할 수 있습니다. 이 글이 여러분의 학습에 도움이 되었기를 바랍니다.