정수 값들이 주어지고, 이 값들을 이용해 연결 리스트(Linked List)를 구성한다고 가정해 봅시다. 이번 글에서는 재귀(Recursion) 기법을 활용해 단일 연결 리스트(Singly Linked List)에 노드를 삽입하고, 이어서 전체 리스트를 순회하며 값을 출력하는 방법을 단계별로 살펴보겠습니다.
리스트 끝에 노드를 재귀적으로 추가하기
- head가 NULL이면 → 새 노드를 생성해 head로 설정합니다.
- 그렇지 않으면 → head->next를 인자로 넘기며 자기 자신을 재귀 호출합니다.
노드를 재귀적으로 순회하기
- head가 NULL이면 → 함수 실행을 종료합니다.
- 그렇지 않으면 → 현재 노드의 데이터를 출력한 뒤 head->next로 재귀 호출을 이어갑니다.
예시
입력 − 1, 2, 7, 9, 10
출력 − 연결 리스트 : 1 → 2 → 7 → 9 → 10 → NULL
입력 − 12, 21, 17, 94, 18
출력 − 연결 리스트 : 12 → 21 → 17 → 94 → 18 → NULL
프로그램의 접근 방식
이 접근 방식에서는 노드를 추가하는 함수와 리스트를 순회하는 함수를 각각 정의하고, 다음 노드를 처리할 때 스스로를 재귀 호출하는 구조로 문제를 해결합니다. 전체 흐름은 다음과 같습니다.
- 정수형 data 멤버와 다음 노드를 가리키는 SLLNode* next 포인터를 갖는 구조체 SLLNode를 정의합니다.
- addtoEnd(SLLNode* head, int data) 함수는 리스트의 head 포인터와 저장할 데이터를 매개변수로 받아 연결 리스트의 맨 끝에 새 노드를 추가합니다.
- head 포인터가 NULL이면 리스트가 비어 있는 상태입니다. 이 경우 새 노드를 생성해 head로 지정하고, 새 노드의 next를 NULL로 설정한 뒤 해당 노드의 포인터를 반환합니다.
- head가 NULL이 아니라면 head->next = addtoEnd(head->next, data) 형태로 재귀 호출하여 다음 위치에 노드를 추가합니다.
- traverseList(SLLNode* head) 함수는 head부터 시작해 각 노드의 값을 차례대로 출력하며 리스트를 순회합니다.
- head가 NULL이면 "NULL"을 출력하고 함수를 종료합니다.
- 그렇지 않으면 현재 노드의 데이터를 출력한 뒤 traverseList(head->next)를 호출해 다음 노드를 계속 순회합니다.
- main 함수 안에서는 addtoEnd()로 리스트를 구성하고, traverseList()로 리스트 전체를 출력합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
struct SLLNode {
int data;
SLLNode* next;
};
SLLNode* addtoEnd(SLLNode* head, int data){
if (head == NULL){
SLLNode *nodex = new SLLNode;
nodex->data = data;
nodex->next = NULL;
return nodex;
}
else{
head->next = addtoEnd(head->next, data);
}
return head;
}
void traverseList(SLLNode* head){
if (head == NULL){
cout <<"NULL";
return;
}
cout << head->data << " -> ";
traverseList(head->next);
}
int main(){
SLLNode* head1 = NULL;
head1 = addtoEnd(head1, 1);
head1 = addtoEnd(head1, 8);
head1 = addtoEnd(head1, 56);
head1 = addtoEnd(head1, 12);
head1 = addtoEnd(head1, 34);
cout<<"Linked List is :"<<endl;
traverseList(head1);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Linked List is : 1 -> 8 -> 56 -> 12 -> 34 -> NULL
복잡도 및 참고 사항
삽입과 순회 모두 리스트의 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 다만 재귀 호출이 진행될 때마다 스택 프레임이 쌓이기 때문에 공간 복잡도 역시 O(n)이 되며, 리스트가 매우 길어질 경우 스택 오버플로우가 발생할 수 있다는 점을 유의해야 합니다. 따라서 실무에서는 리스트의 크기가 크다면 반복문 기반 구현을 고려하는 것이 좋습니다.