C++ 단일 순환 연결 리스트에서 최솟값과 최댓값 찾는 방법

이 글에서는 C++로 구현된 단일 순환 연결 리스트(singly circular linked list)에서 최솟값과 최댓값을 찾는 방법을 알아보겠습니다.

순환 연결 리스트의 기본 개념

단일 순환 연결 리스트는 마지막 노드의 next 포인터가 첫 번째 노드를 가리키는 구조입니다. 또한 시작 노드는 별도의 start 포인터로 관리됩니다. 새로운 요소를 삽입할 때는 마지막 노드 뒤에 추가하며, 이때 새로 삽입된 노드의 next 부분이 start 노드의 주소로 갱신되어 순환 구조가 유지됩니다.

최솟값과 최댓값을 찾는 알고리즘

알고리즘 자체는 매우 간단합니다.

먼저 min 변수에는 양의 무한대(INT_MAX)를, max 변수에는 음의 무한대(INT_MIN)를 초기값으로 할당합니다. 그다음 리스트를 처음부터 끝까지 한 번 순회하면서 다음 작업을 수행합니다.

현재 노드의 값이 min보다 작으면 min을 현재 값으로 갱신
현재 노드의 값이 max보다 크면 max를 현재 값으로 갱신

순회가 끝나면 min과 max에 각각 리스트 전체의 최솟값과 최댓값이 저장되어 있습니다.

C++ 구현 예제

#include<iostream>
using namespace std;
class Node{
    public:
    int data;
    Node *next;
};
Node* getNode(int key){
    Node *newNode = new Node();
    newNode->data = key;
    newNode->next = NULL;
    return newNode;
}
void insert(Node **start, int data){
    Node *current = *start;
    Node *newNode = getNode(data);
    if(*start == NULL){
        newNode->next = newNode;
        *start = newNode;
        return;
    }
    while (current->next != *start) {
        current = current->next;
    }
    newNode->next = *start;
    current->next = newNode;
}
void displayList(Node *start){
    Node* current = start;
    if (start == NULL) {
        cout << "Display List is empty";
        return;
    } else {
        do {
            cout << current->data << " ";
            current = current->next;
        }
        while (current != start);
    }
    cout << endl;
}
void getMinMax(Node **start){
    if(*start == NULL){
        return;
    }
    Node* current;
    current = *start;
    int min = INT_MAX, max = INT_MIN;
    while (current->next != *start) {
        if (current->data < min) {
            min = current->data;
        }
        if (current->data > max) {
            max = current->data;
        }
        current = current->next;
    }
    cout << "Minimum: " << min << ", Maximum: " << max;
}
int main() {
    int data[] = {99, 11, 22, 10, 44, 55, 66};
    int n = sizeof(data)/sizeof(data[0]);
    Node *start = NULL;
    for(int i = 0; i<n; i++){
        insert(&start, data[i]);
    }
    displayList(start);
    getMinMax(&start);
}

실행 결과

99 11 22 10 44 55 66
Minimum: 10, Maximum: 99

시간 복잡도 분석

위 알고리즘은 리스트의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 여기서 n은 리스트에 포함된 노드의 개수입니다. 추가적인 메모리 사용 없이 기존 변수 두 개(min, max)만으로 해결할 수 있으므로 공간 복잡도는 O(1)입니다.

참고로 위 코드의 getMinMax 함수는 while 조건이 current->next != start일 때 반복되므로, 마지막 노드(start 바로 앞 노드)는 비교 대상에서 제외될 수 있습니다. 모든 노드를 확실히 검사하려면 do-while 문을 사용해 순회하는 것이 더 안전합니다.