원형 연결 리스트(circular linked list)에서 최댓값과 최솟값을 가진 노드를 찾아야 할 때는 먼저 'Node' 클래스를 정의해야 합니다. 이 클래스에는 두 가지 속성이 있는데, 하나는 노드에 저장된 data이고, 다른 하나는 연결 리스트의 다음 노드를 가리키는 next 참조입니다.
원형 연결 리스트에서는 헤드(head)와 꼬리(tail)가 서로 인접해 있습니다. 즉, 마지막 노드가 다시 첫 번째 노드와 연결되어 하나의 원을 이루며, 일반 연결 리스트와 달리 마지막 노드에 'NULL' 값이 존재하지 않습니다.
다음으로, 초기화 함수를 포함하는 또 다른 클래스를 생성하고 노드의 head를 'None'으로 초기화합니다.
이후 사용자가 직접 여러 메서드를 정의하여 연결 리스트에 노드를 추가하고, 노드들 중 최솟값과 최댓값을 찾은 뒤 그 결과를 출력할 수 있습니다.
아래는 이를 구현한 예제입니다.
예제 코드
class Node:
def __init__(self,data):
self.data = data
self.next = None
class list_creation:
def __init__(self):
self.head = Node(None)
self.tail = Node(None)
self.head.next = self.tail
self.tail.next = self.head
def add_data(self,my_data):
new_node = Node(my_data)
if self.head.data is None:
self.head = new_node
self.tail = new_node
new_node.next = self.head
else:
self.tail.next = new_node
self.tail = new_node
self.tail.next = self.head
def find_min_node(self):
curr = self.head;
min_val = self.head.data;
if(self.head == None):
print("The list is empty");
else:
while(True):
if(min_val > curr.data):
min_val = curr.data;
curr= curr.next;
if(curr == self.head):
break;
print("Minimum value node in the list: "+ str(min_val));
def find_max_node(self):
curr = self.head;
max_val = self.head.data;
if(self.head == None):
print("List is empty");
else:
while(True):
if(max_val < curr.data):
max_val = curr.data;
curr= curr.next;
if(curr == self.head):
break;
print("The maximum valueed node is : "+ str(max_val));
class circular_linked_list:
my_cl = list_creation()
print("Values have been added to the list")
my_cl.add_data(11)
my_cl.add_data(52)
my_cl.add_data(36)
my_cl.add_data(74)
my_cl.find_max_node()
my_cl.find_min_node()실행 결과
Values have been added to the list The maximum valueed node is : 74 Minimum value node in the list: 11
코드 설명
- 'Node' 클래스가 생성됩니다. 각 노드는 데이터(data)와 다음 노드를 가리키는 참조(next)를 가집니다.
- 필요한 속성들을 담고 있는 또 다른 클래스가 생성됩니다.
- 원형 연결 리스트에 데이터를 추가하는 데 사용되는 'add_data' 메서드가 정의됩니다. 리스트가 비어 있으면 새 노드가 head이자 tail이 되고, 그렇지 않으면 tail 뒤에 노드를 추가한 후 tail이 다시 head를 가리키도록 합니다.
- 리스트를 한 바퀴 순회하며 노드의 최댓값을 구하는 'find_max_node' 메서드가 정의됩니다.
- 같은 방식으로 리스트를 순회하며 최솟값을 구하는 'find_min_node' 메서드가 정의됩니다.
- 'list_creation' 클래스의 객체가 생성되고, 이 객체의 메서드를 호출하여 값(11, 52, 36, 74)을 리스트에 추가합니다.
- '__init__' 메서드가 정의되어 원형 연결 리스트의 첫 번째 노드와 마지막 노드를 None으로 초기화합니다.
- 'find_max_node' 메서드와 'find_min_node' 메서드가 차례로 호출됩니다.
- 두 메서드는 현재 노드(curr)가 다시 head로 돌아올 때까지 노드를 순회하며 리스트 전체의 최댓값과 최솟값을 구합니다.
- 최종 결과가 콘솔에 출력됩니다.
참고로 이 방식은 리스트의 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 원형 연결 리스트는 종료 조건이 NULL이 아닌 head로 돌아오는 것임을 기억하면, 일반 연결 리스트의 탐색 로직을 쉽게 확장해 활용할 수 있습니다.