연결 리스트(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 print_it(self):
curr = self.head
while curr:
print(curr.data)
curr = curr.next
def count_val(self, key):
return self.count_helper_fun(self.head, key)
def count_helper_fun(self, curr, key):
if curr is None:
return 0
if curr.data == key:
return 1 + self.count_helper_fun(curr.next, key)
else:
return self.count_helper_fun(curr.next, key)
my_instance = my_linked_list()
my_list = [56, 43, 70, 67, 89, 91, 70, 23, 46, 70]
for elem in my_list:
my_instance.add_value(elem)
print("The linked list contains the below elements:")
my_instance.print_it()
key_val = int(input('Enter the data item: '))
count_val = my_instance.count_val(key_val)
print('{0} occurs {1} time(s) in the list.'.format(key_val, count_val))
실행 결과
The linked list contains the below elements: 56 43 70 67 89 91 70 23 46 70 Enter the data item: 70 70 occurs 3 time(s) in the list.
코드 설명
‘Node’ 클래스를 생성합니다. 각 노드는 저장할 데이터(data)와 다음 노드를 가리키는 참조(next)를 가집니다.
필요한 속성을 갖춘 ‘my_linked_list’ 클래스를 생성합니다.
‘__init__’ 함수는 첫 번째 요소인 ‘head’와 마지막 노드인 ‘last_node’를 ‘None’으로 초기화합니다.
‘add_value’ 메서드는 연결 리스트 끝에 새로운 데이터를 추가하는 역할을 합니다.
‘print_it’ 메서드는 리스트를 처음부터 끝까지 순회하며 모든 요소를 출력합니다.
‘count_val’ 메서드는 헬퍼 함수를 호출하기 위한 진입점 역할을 합니다.
‘count_helper_fun’ 헬퍼 함수는 재귀 호출을 통해 연결 리스트 내 특정 요소의 등장 빈도를 계산합니다.
‘my_linked_list’ 클래스의 객체를 생성하고, 샘플 데이터를 차례대로 추가합니다.
‘count_val’ 메서드를 호출하여 사용자가 입력한 값의 등장 횟수를 구합니다.
최종 결과가 콘솔에 출력됩니다.
재귀 로직의 동작 원리
위 코드의 핵심은 기저 조건(base case)과 재귀 조건(recursive case)으로 나뉩니다. 현재 노드가 None, 즉 리스트의 끝에 도달하면 0을 반환하여 재귀를 종료합니다. 현재 노드의 값이 찾고자 하는 키 값과 일치하면 1을 더하고 다음 노드로 재귀 호출을 이어가며, 일치하지 않으면 그대로 다음 노드로 넘어갑니다. 이렇게 각 노드를 한 번씩 방문하면서 일치 횟수를 누적하므로, 시간 복잡도는 O(n)입니다.