연결 리스트(Linked List)를 다루다 보면 재귀 호출 없이 특정 요소가 몇 번 등장하는지 계산해야 하는 경우가 있습니다. 이를 위해 연결 리스트에 요소를 추가하는 메서드, 리스트의 모든 요소를 출력하는 메서드, 그리고 특정 값의 등장 횟수를 세는 메서드를 각각 정의하여 문제를 해결할 수 있습니다.
아래에서 전체 예제 코드와 실행 결과, 그리고 코드의 동작 원리를 단계별로 살펴보겠습니다.
예제 코드
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):
curr = self.head
my_count = 0
while curr:
if curr.data == key:
my_count = my_count + 1
curr = curr.next
return my_count
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' 메서드: 새로운 데이터를 연결 리스트의 끝에 추가합니다. 리스트가 비어 있으면 새 노드를 head로 지정하고, 그렇지 않으면 마지막 노드 뒤에 이어 붙입니다.
'print_it' 메서드: head부터 시작해 리스트 전체를 순회하면서 각 노드의 데이터를 순서대로 출력합니다.
'count_val' 메서드: head부터 끝까지 한 번씩 순회하면서 현재 노드의 데이터가 찾고자 하는 값(key)과 일치하면 카운트를 1씩 증가시킵니다. 반복이 끝나면 최종 카운트를 반환합니다.
객체 생성 및 사용: 'my_linked_list' 클래스의 인스턴스를 만들고, 미리 정의된 리스트의 값을 하나씩 추가한 뒤 전체 요소를 출력합니다.
결과 확인: 사용자로부터 찾고자 하는 값을 입력받아 'count_val' 메서드를 호출하고, 해당 값이 리스트에 몇 번 등장했는지 콘솔에 출력합니다.
동작 방식 요약
이 프로그램은 재귀 대신 while 반복문을 사용해 리스트를 순회하기 때문에, 리스트 길이가 길어져도 스택 오버플로우(stack overflow) 걱정 없이 안전하게 동작합니다. 순회 기반 탐색이므로 시간 복잡도는 O(n)이며, 여기서 n은 연결 리스트의 노드 개수입니다.