재귀 호출 없이 연결 리스트(Linked List)의 길이를 구해야 할 때는, 리스트에 요소를 추가하는 메서드와 전체 길이를 계산하는 메서드를 각각 정의한 클래스를 만들면 됩니다. 핵심은 while 반복문을 사용해 head부터 마지막 노드까지 한 칸씩 이동하면서 개수를 세는 것입니다.
연결 리스트는 각 노드가 데이터와 다음 노드를 가리키는 참조로 구성된 자료구조입니다. 아래 예제에서는 반복문으로 노드를 순차적으로 탐색하며 길이를 계산합니다.
예제 코드
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 calculate_length(self):
curr = self.head
length_val = 0
while curr:
length_val = length_val + 1
curr = curr.next
return length_val
my_instance = my_linked_list()
my_data = input('Enter elements of the linked list ').split()
for elem in my_data:
my_instance.add_value(int(elem))
print('The length of the linked list is ' + str(my_instance.calculate_length()))
실행 결과
Enter elements of the linked list 34 12 56 86 32 99 0 6 The length of the linked list is 8
코드 동작 원리
'Node' 클래스 생성 – 노드 하나는 실제 데이터(data)와 다음 노드를 가리키는 참조(next)로 구성됩니다.
'my_linked_list' 클래스 생성 – 연결 리스트 자체를 표현하며, 시작 노드(head)와 마지막 노드(last_node)를 속성으로 가집니다.
__init__ 초기화 – 객체가 생성될 때 head와 last_node를 모두 None으로 설정해 빈 리스트 상태로 만듭니다.
add_value 메서드 – 새 데이터를 리스트 끝에 추가합니다. 리스트가 비어 있으면 새 노드가 head가 되고, 그렇지 않으면 마지막 노드의 next에 새 노드를 연결한 뒤 last_node를 갱신합니다.
calculate_length 메서드 – head부터 시작해 curr가 None이 될 때까지 next로 이동하며 카운트를 1씩 증가시켜 총 길이를 반환합니다.
객체 생성 및 입력 처리 – my_linked_list 인스턴스를 만들고, 사용자에게 공백으로 구분된 숫자들을 입력받아 split()으로 나눕니다.
데이터 추가 – 입력된 각 요소를 정수로 변환해 add_value 메서드로 리스트에 차례대로 추가합니다.
길이 계산 및 출력 – calculate_length 메서드를 호출해 길이를 구하고, 그 결과를 콘솔에 출력합니다.
시간 복잡도
이 방식은 리스트의 모든 노드를 한 번씩만 방문하므로 시간 복잡도는 O(n)이며, 추가적인 저장 공간을 거의 사용하지 않아 공간 복잡도는 O(1)입니다. 재귀를 사용하는 방법과 달리 노드 수가 매우 많은 리스트에서도 스택 오버플로우(stack overflow) 위험 없이 안정적으로 동작한다는 장점이 있습니다.