C++로 이중 연결 리스트에서 가장 큰 노드 찾는 방법

이 문제에서는 하나의 이중 연결 리스트(Doubly Linked List) LL이 주어지며, 우리의 목표는 리스트 전체를 탐색하여 가장 큰 값을 가진 노드를 찾는 것입니다.

문제 이해를 돕기 위한 예시를 살펴보겠습니다.

입력 : linked-list = 5 -> 2 -> 9 -> 8 -> 1 -> 3
출력 : 9

위 예시에서 리스트에 포함된 값 중 가장 큰 값은 9이므로, 정답으로 9를 반환하게 됩니다.

해결 접근 방법

이 문제를 해결하는 가장 직관적인 방법은 다음과 같습니다.

연결 리스트를 머리(head) 노드부터 끝까지 한 번 순회하면서, 현재 노드의 데이터 값이 지금까지 발견한 최댓값(maxVal)보다 크면 maxVal 포인터를 현재 노드로 갱신합니다. 모든 노드의 순회가 완료되면 maxVal이 가리키는 노드의 데이터, 즉 리스트 전체의 최댓값을 반환하면 됩니다.

알고리즘 단계

1. maxVal과 curr 두 개의 포인터를 선언하고, 둘 다 헤드 노드로 초기화합니다.
2. curr이 NULL이 될 때까지 반복문을 실행합니다.
3. 각 반복에서 curr->data가 maxVal->data보다 크면 maxVal = curr로 갱신합니다.
4. curr을 다음 노드(curr->next)로 이동시킵니다.
5. 반복이 종료되면 maxVal->data를 반환합니다.

복잡도 분석

시간 복잡도: O(n) — 리스트의 모든 노드를 정확히 한 번씩 방문합니다.
공간 복잡도: O(1) — 추가 메모리 없이 포인터 두 개만 사용합니다.

예제 코드

아래 프로그램은 위에서 설명한 솔루션의 실제 동작 과정을 보여줍니다.

#include <iostream>
using namespace std;
struct Node{
    int data;
    struct Node* next;
    struct Node* prev;
};
void push(struct Node** head_ref, int new_data){
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->prev = NULL;
    new_node->next = (*head_ref);
    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;
    (*head_ref) = new_node;
}
int findLargestNodeInDLL(struct Node** head_ref){
   struct Node *maxVal, *curr;
   maxVal = curr = *head_ref;
   while (curr != NULL){
      if (curr->data > maxVal->data)
         maxVal = curr;
      curr = curr->next;
   }
   return maxVal->data;
}
int main(){
   struct Node* head = NULL;
   push(&head, 5);
   push(&head, 2);
   push(&head, 9);
   push(&head, 1);
   push(&head, 3);
   cout<<"The largest node in doubly linked-list is "<<findLargestNodeInDLL(&head);
   return 0;
}

실행 결과

The largest node in doubly linked-list is 9

위 코드에서 push 함수는 새 노드를 리스트의 맨 앞에 삽입하는 역할을 하며, findLargestNodeInDLL 함수는 앞서 설명한 알고리즘대로 리스트를 순회하며 최댓값 노드를 찾아 그 값을 반환합니다. 실행 결과 5개의 노드 중 가장 큰 값인 9가 정상적으로 출력되는 것을 확인할 수 있습니다.