연결 리스트(Linked List)에서 가장 중간에 위치한 요소를 출력해야 하는 경우가 있습니다. 이럴 때 print_middle_val이라는 메서드를 정의하면 손쉽게 해결할 수 있습니다. 이 메서드는 연결 리스트 전체를 매개변수로 받아 중간에 있는 요소를 찾아 화면에 출력합니다.
리스트 길이가 홀수이면 중간 요소 하나를, 짝수이면 중앙에 인접한 두 개의 요소를 함께 출력하도록 처리합니다.
예제 코드
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList_structure:
def __init__(self):
self.head = None
self.last_node = None
def add_vals(self, data):
if self.last_node is None:
self.head = Node(data)
self.last_node = self.head
else:
self.last_node.next = Node(data)
self.last_node = self.last_node.next
def print_middle_val(my_list):
curr = my_list.head
my_len = 0
while curr:
curr = curr.next
my_len = my_len + 1
curr = my_list.head
for i in range((my_len - 1)//2):
curr = curr.next
if curr:
if my_len % 2 == 0:
print('The two middle elements are {} and {}'.format(curr.data, curr.next.data))
else:
print('The middle-most element is {}.'.format(curr.data))
else:
print('The list is empty')
my_instance = LinkedList_structure()
my_list = input('Enter the elements of the linked list... ').split()
for elem in my_list:
my_instance.add_vals(int(elem))
print_middle_val(my_instance)
실행 결과
Enter the elements of the linked list... 56 23 78 99 34 11
The two middle elements are 78 and 99
코드 설명
'Node' 클래스 생성: 데이터(data)와 다음 노드를 가리키는 포인터(next)를 저장하는 기본 노드 구조체입니다.
'LinkedList_structure' 클래스 생성: 연결 리스트 자료구조를 관리하는 클래스로, 필요한 속성들을 함께 정의합니다.
'init' 함수: 리스트의 첫 번째 요소인 'head'를 'None'으로 초기화하는 역할을 합니다.
'add_vals' 메서드: 리스트 끝에 새로운 값을 추가하는 기능을 담당합니다.
'print_middle_val' 메서드: 연결 리스트의 중간 값을 계산하여 콘솔에 출력하는 기능을 담당합니다.
인스턴스 생성 및 데이터 입력: 'LinkedList_structure'의 인스턴스를 만들고, 사용자로부터 입력받은 요소들을 연결 리스트에 차례대로 추가합니다.
메서드 호출 및 결과 출력: 완성된 연결 리스트에 대해 'print_middle_val' 메서드를 호출하고, 그 결과를 콘솔에 표시합니다.
동작 원리
이 프로그램은 두 단계로 중간 노드를 찾습니다. 먼저 리스트를 한 번 순회하면서 전체 노드의 개수(my_len)를 센 뒤, 다시 처음부터 (my_len - 1) // 2번째 노드까지 이동하여 중간 지점에 도달합니다.
노드 개수가 짝수라면 중앙에 두 개의 노드가 존재하므로 현재 노드와 다음 노드의 값을 함께 출력하고, 홀수라면 정확히 중앙에 있는 하나의 노드만 출력합니다. 만약 리스트가 비어 있다면 "The list is empty"라는 안내 문구를 출력합니다.
이 방식은 리스트를 두 번 순회하지만 각 순회가 O(n)이므로 전체 시간 복잡도는 O(n)으로 효율적입니다. 참고로, 느린 포인터와 빠른 포인터를 활용한 '토끼와 거북이' 기법을 사용하면 한 번의 순회만으로도 중간 노드를 찾을 수 있습니다.