이 튜토리얼에서는 주어진 배열을 활용하여 연결 리스트(Linked List)를 생성하는 방법을 배워보겠습니다. 배열의 각 요소를 하나씩 읽어 들여 새로운 노드를 만들고, 이를 리스트 끝에 차례대로 연결하는 방식으로 구현합니다.
문제 해결 접근 방식
문제를 해결하기 위한 전체적인 흐름은 다음과 같습니다.
- 더미(dummy) 데이터로 배열을 초기화합니다.
- 노드를 표현할 구조체(struct)를 정의합니다.
- 배열을 순회하면서 다음 작업을 반복합니다.
- 배열의 데이터를 담은 새 노드를 생성합니다.
- 생성한 노드를 연결 리스트의 끝에 삽입합니다.
- 완성된 연결 리스트를 출력합니다.
예제 코드
위의 접근 방식을 실제 코드로 구현해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
};
struct Node* newNode(int data) {
Node* node = new Node;
node->data = data;
node->next = NULL;
return node;
}
void insertNewNode(Node** root, int data) {
Node* node = newNode(data);
Node* ptr;
if (*root == NULL) {
*root = node;
}
else {
ptr = *root;
while (ptr->next != NULL) {
ptr = ptr->next;
}
ptr->next = node;
}
}
void printLinkedList(Node* root) {
while (root != NULL) {
cout << root->data << " -> ";
root = root->next;
}
cout << "NULL" << endl;
}
Node* createLinkedList(int arr[], int n) {
Node *root = NULL;
for (int i = 0; i < n; i++) {
insertNewNode(&root, arr[i]);
}
return root;
}
int main() {
int arr[] = { 1, 2, 3, 4, 5 }, n = 5;
Node* root = createLinkedList(arr, n);
printLinkedList(root);
return 0;
}코드 설명
- newNode 함수: 전달받은 데이터를 저장할 새로운 노드를 동적으로 할당하고 초기화합니다.
- insertNewNode 함수: 리스트가 비어 있으면 새 노드를 루트로 설정하고, 그렇지 않으면 마지막 노드까지 이동한 뒤 새 노드를 연결합니다.
- printLinkedList 함수: 헤드 노드부터 시작해 각 노드의 데이터를 순서대로 출력하고, 마지막에 NULL을 표시합니다.
- createLinkedList 함수: 배열의 모든 요소에 대해 insertNewNode를 호출하여 전체 연결 리스트를 구성합니다.
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
1 -> 2 -> 3 -> 4 -> 5 -> NULL
마무리
지금까지 C++에서 배열을 연결 리스트로 변환하는 기본적인 방법을 살펴보았습니다. 이 방식은 매번 마지막 노드를 찾기 위해 처음부터 순회하므로 시간 복잡도는 O(n²)입니다. 성능을 개선하려면 마지막 노드를 가리키는 포인터(tail pointer)를 함께 유지하면 O(n)으로 최적화할 수 있습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.