C++ 연결 리스트 길이 구하기: 반복문 vs 재귀
연결 리스트(Linked List)의 길이는 리스트에 포함된 노드의 개수를 의미합니다. 이 글에서는 헤드(head) 포인터가 주어졌을 때 반복(iteration)과 재귀(recursion), 두 가지 방식으로 리스트의 길이를 구하는 방법을 소개합니다.
1. 반복문 방식
반복문 방식은 포인터를 한 노드씩 이동시키며 직접 개수를 세는 가장 직관적인 방법입니다.
- 리스트의 헤드 노드에서 탐색을 시작합니다.
- 현재 포인터가 NULL이 아닌 동안 카운트를 1씩 증가시키고 다음 노드로 이동합니다.
- 포인터가 NULL에 도달하면, 그때까지 센 카운트 값이 곧 리스트의 길이입니다.
2. 재귀 방식
재귀 방식은 전체 문제를 더 작은 하위 문제로 나누어 해결하는 방식입니다.
- 헤드 포인터를 함수의 인자로 전달합니다.
- 기저 조건(base case): 인자가 NULL이면 0을 반환합니다.
- 그 외의 경우에는 현재 노드의 다음 노드를 인자로 재귀 호출한 뒤, 1 + 하위 리스트의 길이를 반환합니다.
예제 코드
아래 예제는 위 두 방식을 모두 구현한 C++ 코드입니다. 참고로 append() 함수는 새 노드를 항상 리스트의 맨 앞에 추가하므로, 최종 리스트는 1 → 2 → 1 → 3 → 1 순서가 되며 총 5개의 노드를 가집니다.
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
};
void append(struct Node** start, int data) {
struct Node* new_node = new Node;
new_node->data = data;
new_node->next = (*start);
(*start) = new_node;
}
int count_recursive(Node* start) {
if (start == NULL)
return 0;
return 1 + count_recursive(start->next);
}
int count_iterative(Node* start) {
int count = 0;
Node* current = start;
while (current != NULL) {
count++;
current = current->next;
}
return count;
}
int main() {
Node* start = NULL;
append(&start, 1);
append(&start, 3);
append(&start, 1);
append(&start, 2);
append(&start, 1);
cout << "반복문 방식으로 센 노드 개수: " << count_iterative(start) << endl;
cout << "재귀 방식으로 센 노드 개수: " << count_recursive(start);
}
실행 결과
반복문 방식으로 센 노드 개수: 5 재귀 방식으로 센 노드 개수: 5
시간·공간 복잡도 비교
- 반복문 방식: 시간 복잡도 O(n), 공간 복잡도 O(1)
- 재귀 방식: 시간 복잡도 O(n), 공간 복잡도 O(n) — 함수 호출 스택 사용
두 방식 모두 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(n)으로 동일합니다. 다만 재귀 방식은 함수 호출 스택을 사용하기 때문에 리스트가 매우 길 경우 스택 오버플로(stack overflow)가 발생할 수 있습니다. 따라서 실무 환경에서는 메모리 사용량이 적고 안정적인 반복문 방식이 일반적으로 더 권장됩니다.