연결 리스트(Linked List)는 여러 개의 노드가 서로 연결되어 있는 선형 자료구조입니다. 각 노드는 두 가지 필드로 구성되는데, 하나는 실제 값을 저장하는 데이터 필드이고, 다른 하나는 다음 노드의 주소를 가리키는 포인터입니다.
단일 연결 리스트(singly linked list)가 주어졌을 때, 이 리스트에서 첫 번째 노드를 삭제해야 하는 상황을 가정해 보겠습니다. 예를 들면 다음과 같습니다.
입력 1 − 4 → 3 → 2 → 1
출력 − 3 → 2 → 1 →
설명 − '4'는 주어진 단일 연결 리스트의 첫 번째 노드입니다. 첫 번째 노드를 삭제하면 연결 리스트는 3→2→1이 됩니다.
입력 2 − 1 → 2 → 3 →
출력 − 2 → 3 →
설명 − 첫 번째 노드 '1'을 삭제한 후에는 연결 리스트가 2 → 3이 됩니다.
문제 해결 접근 방식
처음에 우리는 여러 개의 노드로 구성된 연결 리스트를 가지고 있습니다. 각 노드는 데이터와 다음 노드의 주소를 담고 있습니다. 연결 리스트에 데이터를 삽입한 후, 첫 번째 노드를 삭제하는 함수를 작성합니다.
핵심 아이디어는 간단합니다. 먼저 head를 가리키는 임시 포인터(temp)를 만들고, head를 다음 노드로 이동시킨 뒤, 임시 노드를 메모리에서 삭제하고 연결 리스트를 반환하면 됩니다.
deleteAtFirst(node*&head) 함수는 head에 대한 참조 포인터를 받아 연결 리스트의 첫 번째 노드를 삭제합니다.
처음에 head를 가리키는 임시 포인터를 생성합니다.
head를 다음 노드로 이동시킵니다.
임시 포인터가 가리키던 노드를 삭제(delete)하여 메모리를 해제합니다.
삭제가 완료된 연결 리스트를 반환합니다.
예제 코드
#include<iostream>
using namespace std;
class node{
public:
int data;
node* next;
node(int d){
data = d;
next = NULL;
}
};
void insertAtFirstNode(node*&head, int data){
node*n = new node(data);
n->next = head;
head = n;
}
void print(node*head){
while(head != NULL){
cout<<head->data<<"->";
head = head->next;
}
cout<<endl;
}
void deleteAtFirst(node*&head){
if(head == NULL){
return;
}
node*temp = head;
head = head->next;
delete temp;
return;
}
int main(){
node*head = NULL;
insertAtFirstNode(head,1);
insertAtFirstNode(head,2);
insertAtFirstNode(head,3);
insertAtFirstNode(head,4);
deleteAtFirst(head);
print(head);
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
3 → 2 → 1 →
주어진 단일 연결 리스트가 4 → 3 → 2 → 1 →이므로, 첫 번째 노드인 4를 삭제하면 연결 리스트는 3 → 2 → 1 →이 됩니다.