연결 리스트(Linked List)의 길이를 재귀(Recursion)를 이용해 구하려면, 먼저 리스트에 요소를 추가하는 메서드와 전체 길이를 계산하는 메서드를 각각 정의해야 합니다. 그리고 실제 재귀 호출을 담당하는 헬퍼(helper) 함수를 별도로 만든 뒤, 길이 계산 메서드가 이 헬퍼 함수를 호출하도록 구성하는 것이 일반적입니다.
아래 예제를 통해 구체적인 동작 방식을 살펴보겠습니다.
예제 코드
class Node:
def __init__(self, data):
self.data = data
self.next = None
class my_linked_list:
def __init__(self):
self.head = None
self.last_node = None
def add_value(self, my_data):
if self.last_node is None:
self.head = Node(my_data)
self.last_node = self.head
else:
self.last_node.next = Node(my_data)
self.last_node = self.last_node.next
def calculate_length(self):
return self.length_helper_fun(self.head)
def length_helper_fun(self, curr):
if curr is None:
return 0
return 1 + self.length_helper_fun(curr.next)
my_instance = my_linked_list()
my_data = input('연결 리스트에 넣을 요소들을 입력하세요: ').split()
for elem in my_data:
my_instance.add_value(int(elem))
print('연결 리스트의 길이는', str(my_instance.calculate_length()))
실행 결과
연결 리스트에 넣을 요소들을 입력하세요: 12 45 32 67 88 0 99
연결 리스트의 길이는 7
코드 설명
먼저 노드 하나를 표현하는 'Node' 클래스를 생성합니다.
필요한 속성과 메서드를 담고 있는 'my_linked_list' 클래스를 정의합니다.
생성자(__init__) 함수는 첫 번째 노드를 가리키는 head와 마지막 노드를 가리키는 last_node를 None으로 초기화합니다.
add_value 메서드는 입력받은 데이터를 연결 리스트 끝에 순차적으로 추가하는 역할을 합니다.
calculate_length 메서드는 헬퍼 함수를 호출해 리스트의 전체 길이를 구합니다.
length_helper_fun이라는 헬퍼 함수가 별도로 정의되는데, 이는 재귀 호출 로직을 분리하기 위함입니다.
헬퍼 함수는 현재 노드가 None(리스트의 끝)인지 확인하고, 그렇지 않으면 다음 노드를 대상으로 자기 자신을 다시 호출하며 길이를 하나씩 누적해 반환합니다.
이후 my_linked_list 클래스의 객체(인스턴스)를 생성합니다.
사용자로부터 공백으로 구분된 여러 개의 값을 입력받아 연결 리스트에 저장합니다.
마지막으로 calculate_length 메서드를 호출한 결과를 콘솔에 출력합니다.
참고: 재귀 vs 반복문
위 예제처럼 재귀를 사용하면 코드가 직관적이지만, 리스트가 매우 길어질 경우 파이썬의 기본 재귀 깊이 제한(보통 1,000회)에 도달할 수 있습니다. 따라서 실무에서는 반복문(while)을 사용해 길이를 세는 방법도 함께 고려하는 것이 좋습니다.