연결 리스트(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 reverse_display(self):
self.helper_reverse_display(self.head)
def helper_reverse_display(self, curr):
if curr is None:
return
self.helper_reverse_display(curr.next)
print(curr.data)
my_instance = my_linked_list()
n = int(input('추가할 요소의 개수는? '))
for i in range(n):
data = int(input('데이터 입력 : '))
my_instance.add_value(data)
print('역순으로 출력된 연결 리스트:')
my_instance.reverse_display()실행 결과
추가할 요소의 개수는? 4 데이터 입력 : 21 데이터 입력 : 34 데이터 입력 : 56 데이터 입력 : 68 역순으로 출력된 연결 리스트: 68 56 34 21
코드 설명
먼저 'Node' 클래스를 생성합니다. 각 노드는 데이터(data)와 다음 노드를 가리키는 포인터(next)를 가집니다.
필요한 속성을 갖춘 'my_linked_list' 클래스를 정의합니다.
'__init__' 생성자에서 첫 번째 노드인 'head'와 마지막 노드인 'last_node'를 모두 'None'으로 초기화합니다.
'add_value' 메서드는 연결 리스트에 새로운 데이터를 추가하는 역할을 합니다. 리스트가 비어 있으면 head에 노드를 생성하고, 그렇지 않으면 마지막 노드 뒤에 이어 붙입니다.
'reverse_display' 메서드는 연결 리스트의 데이터를 콘솔에 역순으로 출력하는 진입점 역할을 합니다.
재귀 호출이 필요하기 때문에 실제 로직을 수행하는 헬퍼 함수 'helper_reverse_display'를 별도로 정의합니다.
헬퍼 함수는 먼저 다음 노드(next)에 대해 재귀 호출을 수행한 뒤, 현재 노드의 데이터를 출력합니다. 이렇게 하면 리스트 끝부터 거꾸로 값이 출력됩니다.
'my_linked_list' 클래스의 객체를 하나 생성합니다.
사용자로부터 연결 리스트에 넣을 요소의 개수를 입력받습니다.
입력받은 개수만큼 반복문을 돌며 데이터를 입력받고, 'add_value' 메서드를 호출해 리스트에 차례대로 추가합니다.
마지막으로 'reverse_display' 메서드를 호출하면, 재귀에 의해 입력된 순서와 반대로 68 → 56 → 34 → 21 순서로 출력됩니다.
동작 원리 요약
이 코드의 핵심은 재귀 호출의 순서입니다. 헬퍼 함수가 현재 노드의 데이터를 출력하기 전에 다음 노드에 대한 재귀 호출을 먼저 실행하기 때문에, 가장 깊은 곳(리스트의 마지막 노드)부터 차례대로 되돌아오면서 값이 출력됩니다. 따라서 별도의 스택이나 리스트 뒤집기 없이도 역순 출력이 가능하며, 시간 복잡도는 O(n)입니다. 다만 재귀 깊이 제한이 있으므로 매우 긴 리스트에는 주의가 필요합니다.