이중 연결 리스트(Doubly Linked List)에서 최댓값과 최솟값을 가진 노드를 찾으려면 먼저 'Node' 클래스를 정의해야 합니다. 이 클래스에는 세 가지 속성이 필요합니다. 현재 노드에 저장된 데이터(data), 다음 노드를 가리키는 참조(next), 그리고 이전 노드를 가리키는 참조(prev)입니다.
아래에서 전체 구현 과정과 실행 결과를 확인할 수 있습니다.
예제 코드
class Node:
def __init__(self, my_data):
self.prev = None
self.data = my_data
self.next = None
class double_list:
def __init__(self):
self.head = None
self.tail = None
def add_data(self, my_data):
new_node = Node(my_data)
if self.head is None:
self.head = self.tail = new_node
self.head.prev = None
self.tail.next = None
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.tail.next = None
def min_node(self):
curr = self.head
if self.head is None:
print("리스트가 비어 있습니다")
return 0
else:
minimum = self.head.data
while curr is not None:
if minimum > curr.data:
minimum = curr.data
curr = curr.next
return minimum
def max_node(self):
curr = self.head
if self.head is None:
print("리스트가 비어 있습니다")
return 0
else:
maximum = self.head.data
while curr is not None:
if curr.data > maximum:
maximum = curr.data
curr = curr.next
return maximum
def print_it(self):
curr = self.head
if self.head is None:
print("리스트가 비어 있습니다")
return
print("이중 연결 리스트의 노드들:")
while curr is not None:
print(curr.data)
curr = curr.next
my_instance = double_list()
print("이중 연결 리스트에 요소를 추가합니다")
my_instance.add_data(10)
my_instance.add_data(24)
my_instance.add_data(54)
my_instance.add_data(77)
my_instance.add_data(92)
my_instance.print_it()
print("최댓값을 가진 노드는 : ")
print(my_instance.max_node())
print("최솟값을 가진 노드는 : ")
print(my_instance.min_node())실행 결과
이중 연결 리스트에 요소를 추가합니다 이중 연결 리스트의 노드들: 10 24 54 77 92 최댓값을 가진 노드는 : 92 최솟값을 가진 노드는 : 10
코드 설명
- 'Node' 클래스를 생성합니다. 각 노드는 데이터(data), 이전 노드 참조(prev), 다음 노드 참조(next)를 가집니다.
- 연결 리스트 자체를 관리하는 'double_list' 클래스를 생성하며, 내부에 head(첫 번째 노드)와 tail(마지막 노드) 포인터를 둡니다.
- 'add_data' 메서드는 새로운 데이터를 리스트 끝(tail)에 추가하는 역할을 합니다.
- 'print_it' 메서드는 head부터 순회하며 리스트의 모든 노드 값을 화면에 출력합니다.
- 'max_node' 메서드는 첫 번째 노드의 값을 초기 최댓값으로 설정한 뒤, 전체 노드를 순회하며 더 큰 값이 있으면 갱신하여 최댓값을 반환합니다.
- 'min_node' 메서드도 같은 방식으로 초기 최솟값을 설정하고 순회하며 더 작은 값이 나오면 갱신하여 최솟값을 반환합니다.
- 'double_list' 객체를 생성한 후, 데이터를 추가하고 각 메서드를 호출하여 최댓값과 최솟값을 구합니다.
시간 복잡도
두 메서드 모두 리스트의 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 여기서 n은 연결 리스트에 저장된 노드의 개수입니다. 추가 공간 없이 포인터만 이동하며 탐색하므로 공간 복잡도는 O(1)로 효율적입니다.