개요
연결 리스트(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 alternate_nodes(self):
curr = self.head
while curr:
print(curr.data)
if curr.next is not None:
curr = curr.next.next
else:
break
my_instance = my_linked_list()
my_list = input("Enter the elements of the linked list :").split()
for elem in my_list:
my_instance.add_value(elem)
print("The alternate elements in the linked list are :")
my_instance.alternate_nodes()
실행 결과
Enter the elements of the linked list :56 78 43 51 23 89 0 6
The alternate elements in the linked list are :
56
43
23
0
코드 설명
'Node' 클래스 생성: 연결 리스트의 개별 노드를 나타내는 클래스로, 저장할 데이터(
data)와 다음 노드를 가리키는 포인터(next)를 속성으로 가집니다.'my_linked_list' 클래스 생성: 연결 리스트 자체를 관리하는 클래스로, 필요한 속성과 메서드들을 포함합니다.
초기화(__init__): 리스트의 첫 번째 요소인
head와 마지막 노드인last_node를 모두None으로 초기화합니다.add_value 메서드: 새로운 데이터를 연결 리스트의 끝에 추가합니다. 리스트가 비어 있으면 새 노드를 head로 지정하고, 그렇지 않으면 마지막 노드 뒤에 연결합니다.
print_it 메서드: head부터 시작해 리스트 전체를 순회하며 모든 요소를 순서대로 출력합니다.
alternate_nodes 메서드: 핵심 로직입니다. 현재 노드의 값을 출력한 뒤, 포인터를 두 칸씩(
curr.next.next) 앞으로 이동시켜 대체 위치의 노드만 방문합니다. 다음 노드가 더 이상 없으면 반복을 종료합니다.객체 생성 및 실행: 'my_linked_list' 클래스의 인스턴스를 만들고, 사용자 입력값을 리스트에 추가한 후
alternate_nodes메서드를 호출하여 대체 인덱스의 요소들을 찾아냅니다.결과 출력: 최종적으로 선택된 대체 노드들의 값이 콘솔에 표시됩니다.
핵심 포인트
이 알고리즘은 재귀 대신 반복문과 두 칸씩 점프하는 포인터를 활용하기 때문에 스택 오버플로우 걱정 없이 긴 리스트도 안전하게 처리할 수 있습니다. 시간 복잡도는 O(n)으로, 리스트를 한 번만 순회하면 되므로 매우 효율적입니다.