연결 리스트(Linked List)의 노드를 재귀(recursion)를 사용하지 않고 역순으로 출력해야 하는 경우가 있습니다. 이럴 때는 연결 리스트에 요소를 추가하는 메서드와 요소를 역순으로 출력하는 메서드를 각각 정의하여 해결할 수 있습니다.
아래 예제를 통해 자세히 살펴보겠습니다.
예제 코드
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):
end_node = None
while end_node != self.head:
curr = self.head
while curr.next != end_node:
curr = curr.next
print(curr.data)
end_node = curr
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()실행 결과
추가할 요소의 개수는? 5 데이터 입력 : 43 데이터 입력 : 67 데이터 입력 : 87 데이터 입력 : 12 데이터 입력 : 34 역순으로 정렬된 연결 리스트 : 34 12 87 67 43
코드 설명
'Node' 클래스를 생성합니다. 이 클래스는 데이터와 다음 노드를 가리키는 포인터를 저장합니다.
필요한 속성을 가진 'my_linked_list' 클래스를 생성합니다.
'__init__' 함수는 첫 번째 요소인 'head'와 마지막 노드인 'last_node'를 'None'으로 초기화하는 역할을 합니다.
'add_value'라는 메서드를 정의하여 연결 리스트에 데이터를 추가합니다. 리스트가 비어 있으면 새 노드가 head가 되고, 그렇지 않으면 마지막 노드 뒤에 새 노드를 연결합니다.
'reverse_display'라는 메서드를 정의하여 연결 리스트의 데이터를 콘솔에 역순으로 출력합니다. 이 메서드는 매번 head부터 시작해 끝 노드 바로 앞까지 이동한 뒤 해당 노드의 값을 출력하는 방식으로 동작하므로, 재귀 호출이 전혀 필요하지 않습니다.
'my_linked_list' 클래스의 객체를 생성합니다.
사용자로부터 연결 리스트에 넣을 요소의 개수를 입력받습니다.
입력받은 개수만큼 반복하면서 'add_value' 메서드를 호출해 데이터를 추가합니다.
'reverse_display' 메서드를 사용해 요소들을 역순으로 변환하고 콘솔에 출력합니다.
참고로 이 방식은 구현이 간단하지만, 각 노드를 출력할 때마다 처음부터 순회하므로 시간 복잡도가 O(n²)입니다. 더 효율적인 방법으로는 노드들을 스택에 담았다가 꺼내며 출력하거나, 리스트에 저장한 후 reversed() 함수를 활용하는 방법(O(n))이 있습니다.