이 글에서는 연결 리스트(Linked List)와 인덱스 값이 주어졌을 때, 해당 위치에 있는 N번째 노드의 데이터를 반환하는 함수를 C++로 작성하는 방법을 알아보겠습니다.
먼저 예시를 통해 문제를 이해해 보겠습니다.
입력 예시
linked list = 34 -> 4 -> 9 -> 1 , n = 2
출력 결과
9
위 예시에서 인덱스 2에 해당하는 노드의 값은 9입니다. 인덱스는 0부터 시작한다는 점에 유의하세요.
접근 방법
n번째 노드에 도달하려면 다음과 같은 단계로 진행합니다.
1. 헤드(head) 노드에서 시작하여 현재 노드를 가리키는 포인터를 설정합니다.
2. 인덱스 카운트(count)를 0으로 초기화합니다.
3. 연결 리스트를 한 노드씩 순회하면서 카운트를 증가시킵니다.
4. 카운트가 원하는 인덱스 n과 일치하면 해당 노드의 데이터를 반환합니다.
이 알고리즘의 시간 복잡도는 O(n)이며, 여기서 n은 리스트의 길이입니다. 공간 복잡도는 O(1)로 추가 메모리가 거의 필요하지 않습니다.
C++ 구현 코드
#include <iostream>
using namespace std;
class Node{
public:
int data;
Node* next;
};
void insertNode(Node** head_ref, int new_data) {
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int findNodeAt(Node* head, int index) {
Node* current = head;
int count = 0;
while (current != NULL){
if (count == index)
return(current->data);
count++;
current = current->next;
}
}
int main(){
Node* head = NULL;
insertNode(&head, 8);
insertNode(&head, 2);
insertNode(&head, 9);
insertNode(&head, 1);
insertNode(&head, 4);
int n = 2;
cout<<"Element at index "<<n<<" is "<<findNodeAt(head, 2);
return 0;
}실행 결과
Element at index 2 is 9
코드 설명
insertNode 함수는 새 노드를 생성하여 리스트의 맨 앞에 삽입합니다. 따라서 삽입한 순서(8, 2, 9, 1, 4)와 실제 리스트의 순서(4 → 1 → 9 → 2 → 8)는 반대가 됩니다.
findNodeAt 함수는 핵심 로직을 담당합니다. current 포인터를 이용해 리스트를 처음부터 끝까지 순회하며, count 변수가 목표 인덱스와 같아지는 순간 그 노드의 data 값을 반환합니다.
만약 인덱스가 리스트의 범위를 벗어나면 while 루프가 종료되고 함수가 명시적인 값을 반환하지 않으므로, 실무에서는 유효성 검사 후 -1과 같은 오류 값을 반환하거나 예외 처리를 추가하는 것이 좋습니다.