단일 연결 리스트란?
연결 리스트(Linked List)는 선형 자료구조로, 여러 개의 노드로 구성됩니다. 각 노드는 두 개의 필드를 가지는데, 하나는 리스트에 저장할 값(데이터)이고, 다른 하나는 다음 노드의 주소를 저장하는 포인터입니다.
문제 정의
이번에 다룰 과제는 연결 리스트의 마지막 노드(꼬리 노드)를 삭제하는 것입니다. 만약 연결 리스트가 비어 있다면 NULL을 반환해야 합니다.
예시를 통해 살펴보겠습니다.
입력 1 − 1 → 2 → 3 → 4 → 5
출력 − 1 → 2 → 3 → 4 →
설명 − 주어진 단일 연결 리스트의 마지막 노드는 '5'입니다. 마지막 노드를 삭제하면 결과는 1 → 2 → 3 → 4 →가 됩니다.
입력 2 − 5 → 8 → 3
출력 − 5 → 8 →
설명 − 주어진 단일 연결 리스트의 마지막 노드는 '3'입니다. 마지막 노드를 삭제하면 결과는 5 → 8 →가 됩니다.
문제 해결 접근 방식
이 문제를 해결하는 가장 간단한 방법은 이전(prev) 노드 포인터를 활용하는 것입니다. 현재(current) 포인터가 연결 리스트의 마지막 노드에 도달했을 때, 그 앞 노드(이전 노드)의 next를 NULL로 설정하면 마지막 노드가 리스트에서 제거됩니다.
리스트의 모든 노드를 순회하면서 현재 노드가 마지막 노드인지 확인하고, 삭제가 완료되면 연결 리스트를 반환합니다.
- 노드를 삽입하여 연결 리스트를 초기화합니다.
- insertAtFirst(node*&head, int data) 함수가 리스트의 맨 앞에 새 노드를 삽입합니다.
- deleteAtTail(node*head) 함수는 head를 가리키는 포인터를 매개변수로 받습니다.
- 이전 노드 포인터(prev)를 생성하고 NULL로 초기화합니다.
- head를 가리키는 임시 포인터(temp)를 생성합니다.
- 임시 포인터가 리스트의 끝에 도달할 때까지 순회하며, 이동할 때마다 현재 값을 prev에 저장합니다.
- 마지막 노드(temp)를 메모리에서 삭제(delete)합니다.
- prev->next를 NULL로 설정하여 새로운 꼬리 노드를 지정합니다.
- 연결 리스트를 반환하거나 출력합니다.
C++ 구현 예제
#include <iostream>
using namespace std;
class node {
public:
int data;
node* next;
node(int d){
data = d;
next = NULL;
}
};
void insertAtFirst(node*& head, int data){
node* n = new node(data);
n->next = head;
head = n;
}
void printNode(node* head){
while(head != NULL){
cout << head->data << "->";
head = head->next;
}
cout << endl;
}
void deleteAtTail(node* head){
node* prev = NULL;
node* temp = head;
while(temp->next != NULL){
prev = temp;
temp = temp->next;
}
delete temp;
prev->next = NULL;
}
int main(){
node* head = NULL;
insertAtFirst(head, 5);
insertAtFirst(head, 4);
insertAtFirst(head, 3);
insertAtFirst(head, 2);
insertAtFirst(head, 1);
deleteAtTail(head);
printNode(head);
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
1→2→3→4→
주어진 입력 단일 연결 리스트 1 → 2 → 3 → 4 → 5에서 마지막 노드는 '5'입니다. 따라서 마지막 노드를 삭제한 후 연결 리스트는 1 → 2 → 3 → 4 →가 됩니다.
주의 사항
위 구현은 리스트에 노드가 두 개 이상 있는 경우를 가정합니다. 노드가 하나뿐이거나 리스트가 비어 있는 경우에는 prev 포인터가 NULL이 되어 오류가 발생할 수 있으므로, 실제 코드에서는 이러한 경계 조건(edge case)에 대한 예외 처리를 추가하는 것이 좋습니다.