C++로 순환 연결 리스트(원형 링크드 리스트) 노드 합계 구하기

이 문제에서는 순환 연결 리스트(Circular Linked List)가 주어지며, 우리의 과제는 리스트에 포함된 모든 노드 값의 합을 계산하는 프로그램을 작성하는 것입니다.

즉, 연결 리스트를 순회하면서 각 노드의 데이터 값을 모두 더한 뒤 그 결과를 반환하면 됩니다.

핵심 개념 정리

연결 리스트(Linked List)

연결 리스트는 데이터 요소들이 포인터(링크)를 통해 서로 연결된 선형 자료구조입니다. 배열과 달리 크기가 고정되어 있지 않아 삽입과 삭제가 유연합니다.

순환 연결 리스트(Circular Linked List)

순환 연결 리스트는 일반 연결 리스트의 변형으로, 마지막 노드가 첫 번째 노드를 가리키는 구조입니다. 이 때문에 리스트의 어느 지점에서 시작해도 전체를 한 바퀴 돌 수 있습니다.

• 단일 연결 리스트(Singly Linked List)와 이중 연결 리스트(Doubly Linked List) 모두 순환 구조로 만들 수 있습니다.

문제 예시

입력:

14 -> 1 -> 7 -> 9 -> 2 -> 6

출력:

39

설명:

합계 = 14 + 1 + 7 + 9 + 2 + 6 = 39

해결 접근 방법

이 문제는 순환 연결 리스트를 처음부터 끝까지 한 바퀴 순회하면서 각 노드의 값을 누적 변수(sum)에 더하는 방식으로 해결할 수 있습니다.

일반 연결 리스트와 달리 마지막 노드가 NULL이 아니라 head를 다시 가리키기 때문에, 종료 조건은 "포인터가 NULL이 될 때"가 아니라 "포인터가 다시 head로 돌아올 때"가 됩니다. 따라서 do-while 반복문을 사용하는 것이 적합합니다.

알고리즘

1단계: sum = 0으로 초기화하고, sumPointer를 head로 설정합니다.

2단계: do-while 반복문을 사용하여 sumPointer != head인 동안 다음을 수행합니다.

• 2-1단계: 현재 노드의 값을 sum에 더합니다. (sum += sumPointer->data)
• 2-2단계: 포인터를 다음 노드로 이동시킵니다. (sumPointer = sumPointer->next)

3단계: 전체 리스트 순회가 끝나면 sum을 반환합니다.

C++ 구현 코드

#include <iostream>
using namespace std;

struct Node {
    int data;
    struct Node* next;
};

// 새 노드를 순환 연결 리스트에 삽입하는 함수
void pushNode(struct Node** head_ref, int data) {
    struct Node* ptr1 = (struct Node*)malloc(sizeof(struct Node));
    struct Node* temp = *head_ref;
    ptr1->data = data;
    ptr1->next = *head_ref;

    if (*head_ref != NULL) {
        while (temp->next != *head_ref)
            temp = temp->next;
        temp->next = ptr1;
    }
    else {
        // 첫 번째 노드는 자기 자신을 가리켜 순환 구조 형성
        ptr1->next = ptr1;
    }
    *head_ref = ptr1;
}

// 순환 연결 리스트의 노드 합계를 계산하는 함수
int CalcSumCirList(struct Node* head) {
    struct Node* sumPointer = head;
    int sum = 0;

    if (head != NULL) {
        do {
            sumPointer = sumPointer->next;
            sum += sumPointer->data;
        } while (sumPointer != head);
    }
    return sum;
}

int main() {
    struct Node* head = NULL;
    pushNode(&head, 4);
    pushNode(&head, 7);
    pushNode(&head, 12);
    pushNode(&head, 1);
    pushNode(&head, 9);
    pushNode(&head, 6);

    cout << "순환 연결 리스트의 합계는 " << CalcSumCirList(head);
    return 0;
}

실행 결과

순환 연결 리스트의 합계는 39

마무리

이 알고리즘은 리스트를 정확히 한 바퀴만 순회하므로 시간 복잡도는 O(n), 추가 공간 없이 두 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다. 순환 연결 리스트에서는 종료 조건을 head와의 비교로 설정한다는 점이 일반 연결 리스트와의 가장 중요한 차이점이며, 이를 놓치면 무한 루프에 빠질 수 있으니 주의해야 합니다.