C++ 연결 리스트에서 두 번째로 큰 요소 찾는 방법

개요

이번 글에서는 연결 리스트(Linked List)에서 두 번째로 큰 요소를 찾는 방법을 살펴보겠습니다. 서로 다른 숫자 값을 가진 n개의 노드가 있다고 가정해 봅시다. 예를 들어 리스트가 [12, 35, 1, 10, 34, 1]과 같다면, 두 번째로 큰 요소는 34입니다.

이 과정은 배열에서 두 번째로 큰 요소를 찾는 방식과 매우 유사합니다. 리스트를 한 번 순회하면서 값을 비교하여 최댓값(first_max)과 두 번째 최댓값(second_max)을 동시에 추적하면 효율적으로 해결할 수 있습니다.

알고리즘 동작 원리

두 개의 변수 first_max와 second_max를 각각 INT_MIN으로 초기화한 후, 노드를 하나씩 순회하며 다음 규칙에 따라 값을 갱신합니다.

1. 현재 노드의 값이 first_max보다 크면 → 기존 first_max 값을 second_max에 저장하고, 현재 값을 first_max로 갱신합니다.
2. 그 외의 경우, 현재 노드의 값이 second_max보다 크면 → second_max를 현재 값으로 갱신합니다.

이렇게 하면 리스트 전체를 단 한 번의 순회(O(n))만으로 두 번째로 큰 값을 구할 수 있습니다.

예제 코드

#include<iostream>
using namespace std;
class Node {
    public:
        int data;
        Node *next;
};
void prepend(Node** start, int new_data) {
    Node* new_node = new Node;
    new_node->data = new_data;
    new_node->next = NULL;
    if ((*start) != NULL){
        new_node->next = (*start);
        *start = new_node;
    }
    (*start) = new_node;
}
int secondLargestElement(Node *start) {
    int first_max = INT_MIN, second_max = INT_MIN;
    Node *p = start;
    while(p != NULL){
        if (p->data > first_max) {
            second_max = first_max;
            first_max = p->data;
        }else if (p->data > second_max)
            second_max = p->data;
        p = p->next;
    }
    return second_max;
}
int main() {
    Node* start = NULL;
    prepend(&start, 15);
    prepend(&start, 16);
    prepend(&start, 10);
    prepend(&start, 9);
    prepend(&start, 7);
    prepend(&start, 17);
    cout << "Second largest element is: " << secondLargestElement(start);
}

출력 결과

Second largest element is: 16

마무리

위 코드에서 prepend 함수는 새 노드를 리스트 맨 앞에 삽입하는 역할을 합니다. main 함수에서 15, 16, 10, 9, 7, 17을 차례로 추가했으므로 실제 리스트는 [17, 7, 9, 10, 16, 15] 순서가 되며, 이 중 두 번째로 큰 값은 16입니다.

이 알고리즘은 시간 복잡도 O(n), 공간 복잡도 O(1)로 매우 효율적이며, 배열뿐 아니라 연결 리스트 등 선형 자료구조 어디에서나 동일하게 적용할 수 있다는 장점이 있습니다.