파이썬으로 이중 연결 리스트에서 가장 큰 요소 찾는 방법

이중 연결 리스트(Doubly Linked List)에서 가장 큰 요소를 찾아야 하는 경우, 리스트에 요소를 추가하는 메서드와 전체 리스트를 순회하며 최댓값을 구하는 메서드를 정의하면 됩니다. 이 글에서는 파이썬으로 이를 구현하는 과정을 단계별로 살펴봅니다.

예제 코드

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList_structure:
    def __init__(self):
        self.first = None
        self.last = None

    def add_vals(self, data):
        self.insert_at_end(Node(data))

    def insert_at_end(self, newNode):
        if self.last is None:
            self.last = newNode
            self.first = newNode
        else:
            newNode.prev = self.last
            self.last.next = newNode
            self.last = newNode

def find_largest_val(my_list):
    if my_list.first is None:
        return None
    largest_val = my_list.first.data
    curr = my_list.first.next
    while curr:
        if curr.data > largest_val:
            largest_val = curr.data
        curr = curr.next
    return largest_val

my_instance = DoublyLinkedList_structure()

my_list = input('Enter the elements in the doubly linked list ').split()
for elem in my_list:
    my_instance.add_vals(int(elem))

largest_val = find_largest_val(my_instance)
if largest_val:
    print('The largest element is {}.'.format(largest_val))
else:
    print('The list is empty.')

실행 결과

Enter the elements in the doubly linked list 45 12 67 89 234 567 888 44 999
The largest element is 999.

코드 설명

'Node' 클래스를 정의합니다. 각 노드는 데이터(data), 다음 노드를 가리키는 next, 이전 노드를 가리키는 prev 세 가지 속성을 가집니다.
필요한 속성을 갖춘 'DoublyLinkedList_structure' 클래스를 정의합니다.
'__init__' 함수는 첫 번째 요소인 first(헤드)와 마지막 요소인 last를 None으로 초기화합니다.
'add_vals' 메서드는 리스트에 새로운 값을 추가하는 역할을 담당합니다.
'insert_at_end' 메서드는 이중 연결 리스트의 맨 끝에 노드를 삽입합니다. 리스트가 비어 있는 경우에는 first와 last가 모두 새 노드를 가리키도록 설정됩니다.
'find_largest_val' 함수는 리스트 전체를 순회하며 가장 큰 값을 찾습니다. 첫 번째 노드의 값을 초기 최댓값으로 설정한 뒤, 다음 노드들을 하나씩 비교하여 더 큰 값이 발견되면 최댓값을 갱신합니다.
'DoublyLinkedList_structure' 클래스의 인스턴스를 생성합니다.
사용자가 입력한 값들을 정수로 변환하여 연결 리스트에 순서대로 추가합니다.
'find_largest_val' 메서드를 호출하여 리스트의 최댓값을 구합니다.
결과가 콘솔에 출력됩니다. 만약 리스트가 비어 있다면 함수가 None을 반환하므로 "리스트가 비어 있습니다."라는 안내 메시지가 출력됩니다.

이 알고리즘은 리스트를 한 번만 순회하면 되기 때문에 시간 복잡도는 O(n)이며, 별도의 추가 저장 공간이 거의 필요하지 않아 공간 복잡도는 O(1)입니다. 따라서 요소 개수가 많아져도 효율적으로 최댓값을 찾을 수 있습니다.