연결 리스트(Linked List)에서 재귀 방식을 사용하지 않고 특정 요소를 검색해야 하는 경우가 있습니다. 이를 구현하기 위해서는 연결 리스트에 값을 추가하는 메서드와 리스트에 저장된 요소를 출력하는 메서드가 필요합니다.
또한 검색하려는 요소가 리스트의 몇 번째 위치(인덱스)에 있는지 찾아주는 메서드도 함께 구현합니다. 재귀 호출 대신 while 반복문으로 노드를 하나씩 순회하기 때문에, 리스트가 길어져도 스택 오버플로우 없이 안정적으로 동작하며 시간 복잡도는 O(n)입니다.
아래는 전체 예제 코드와 실행 결과입니다.
예제 코드
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 is not None:
print(curr.data)
curr = curr.next
def find_index_val(self, my_key):
curr = self.head
index_val = 0
while curr:
if curr.data == my_key:
return index_val
curr = curr.next
index_val = index_val + 1
return -1
my_instance = my_linked_list()
my_list = [67, 4, 78, 98, 32, 0, 11, 8]
for data in my_list:
my_instance.add_value(data)
print('The linked list is : ')
my_instance.print_it()
print()
my_key = int(input('What value would you search for? '))
index_val = my_instance.find_index_val(my_key)
if index_val == -1:
print(str(my_key) + ' was not found.')
else:
print('Element was found at index ' + str(index_val) + '.')
n = int(input('How many elements would you wish to add ? '))
for i in range(n):
data = int(input('Enter data : '))
my_instance.add_value(data)
print('The linked list is : ')
my_instance.print_it()
실행 결과
The linked list is : 67 4 78 98 32 0 11 8 What value would you search for? 11 Element was found at index 6. How many elements would you wish to add ? 2 Enter data : 111 Enter data : 56 The linked list is : 67 4 78 98 32 0 11 8 111 56
코드 설명
'Node' 클래스를 생성합니다. 각 노드는 데이터(data)와 다음 노드를 가리키는 포인터(next)로 구성됩니다.
필요한 속성을 가진 'my_linked_list' 클래스를 생성합니다.
'__init__' 함수는 첫 번째 요소인 'head'와 마지막 노드인 'last_node'를 'None'으로 초기화합니다.
'add_value' 메서드는 연결 리스트의 끝에 새로운 데이터를 추가합니다.
'print_it' 메서드는 연결 리스트의 데이터를 콘솔에 순서대로 출력합니다.
'find_index_val' 메서드는 사용자가 입력한 요소의 인덱스를 찾아 반환하며, 요소가 존재하지 않으면 -1을 반환합니다.
'my_linked_list' 클래스의 객체를 생성합니다.
정수 리스트를 정의한 뒤, 리스트를 순회하면서 'add_value' 메서드를 호출해 데이터를 연결 리스트에 추가합니다.
'print_it' 메서드를 사용해 연결 리스트 전체를 콘솔에 출력합니다.
사용자로부터 검색할 값을 입력받은 뒤 'find_index_val' 메서드를 호출하고, 그 결과를 콘솔에 출력합니다.
마지막으로 사용자가 원하는 개수만큼 새 데이터를 추가로 입력받아 연결 리스트에 추가한 후, 갱신된 리스트를 다시 출력합니다.
핵심 포인트
이 예제의 검색 로직은 head 노드부터 시작해 각 노드의 data가 찾고자 하는 키와 일치하는지 확인하고, 일치하면 해당 인덱스를 즉시 반환합니다. 끝까지 일치하는 노드가 없으면 -1을 반환해 "찾지 못함"을 알립니다. 재귀를 사용하지 않는 반복 방식은 함수 호출 오버헤드가 없고, 리스트가 아무리 길어도 호출 스택이 쌓이지 않아 대용량 데이터에서도 안전하게 동작한다는 장점이 있습니다.