연결 리스트(Linked List)는 여러 개의 노드가 서로 연결되어 있는 선형 자료구조입니다. 각 노드는 데이터 필드(Data Field)와 다음 노드의 주소라는 두 가지 요소로 구성됩니다.
문제 정의
단일 연결 리스트(Singly Linked List)가 주어졌을 때, 이 리스트의 맨 앞(head)에 새로운 노드를 삽입하는 것이 과제입니다.
예를 들어 다음과 같은 경우를 살펴보겠습니다.
- 입력 − 1 → 2 → 3 → 4
- 주어진 연결 리스트의 맨 앞에 '5'를 삽입합니다.
출력 − 5 → 1 → 2 → 3 → 4
설명 − 연결 리스트의 시작 부분에 노드를 삽입하면 리스트는 5 → 1 → 2 → 3 → 4 순서로 출력됩니다.
해결 방법
처음에 주어진 연결 리스트는 여러 개의 노드로 구성되어 있으며, 각 노드는 데이터와 다음 노드의 주소를 담고 있습니다.
노드 구조체가 이미 정의되어 있으므로, 헤드 노드의 주소와 삽입할 데이터를 매개변수로 받아 리스트 맨 앞에 데이터를 추가하는 함수를 만들면 됩니다. 그런 다음 헤드 포인터가 새로 삽입된 노드를 가리키도록 변경합니다.
insertAtHead(node*&head, int data)함수는 헤드 노드의 주소(참조)와 삽입할 데이터를 인자로 받습니다.- 새로운 노드를 생성하고 데이터를 저장합니다.
- 새 노드의 next가 기존 헤드를 가리키도록 한 뒤, 헤드를 새 노드로 이동시킵니다.
- 연결 리스트를 출력하여 결과를 확인합니다.
예제 코드
#include<iostream>
using namespace std;
class node {
public:
int data;
node* next;
node(int d) {
data = d;
next = NULL;
}
};
void insertAtHead(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;
}
}
int main() {
node* head = NULL;
insertAtHead(head, 5);
insertAtHead(head, 2);
insertAtHead(head, 8);
insertAtHead(head, 3);
print(head);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
3→ 8→ 2→ 5→
노드 5, 2, 8, 3을 차례대로 연결 리스트의 맨 앞에 삽입했기 때문에, 마지막에 삽입된 3이 가장 앞에 위치한 3 → 8 → 2 → 5 순서의 리스트가 완성됩니다.
이 방식의 시간 복잡도는 O(1)로, 리스트의 길이와 관계없이 항상 일정한 시간 안에 노드를 삽입할 수 있다는 장점이 있습니다.