단일 연결 리스트(Singly Linked List)는 각 요소가 두 부분으로 이루어진 자료구조입니다. 하나는 데이터 값이고, 다른 하나는 다음 요소를 가리키는 링크(포인터)입니다.
따라서 연결 리스트에 저장된 모든 요소의 합을 구하려면 리스트의 첫 번째 노드부터 마지막 노드까지 차례대로 순회하면서, 각 노드의 데이터 값을 합계(sum) 변수에 더해주면 됩니다.
예시
연결 리스트: 2 -> 27 -> 32 -> 1 -> 5
sum = 2 + 27 + 32 + 1 + 5 = 67
노드의 합을 구하는 방법은 크게 두 가지가 있습니다. 각각의 원리와 구현 코드를 살펴보겠습니다.
방법 1: 반복문(Loop)을 이용한 방식
반복문을 사용하여 연결 리스트의 모든 노드를 처음부터 끝까지 순회하며 합계를 계산합니다. 반복문은 현재 노드의 포인터가 NULL을 가리킬 때, 즉 리스트의 마지막에 도달할 때까지 실행됩니다.
예제 코드
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void push(struct Node** nodeH, int nodeval) {
struct Node* new_node = new Node;
new_node->data = nodeval;
new_node->next = (*nodeH);
(*nodeH) = new_node;
}
int main() {
struct Node* head = NULL;
int sum = 0;
push(&head, 95);
push(&head, 60);
push(&head, 87);
push(&head, 6);
push(&head, 12);
struct Node* ptr = head;
while (ptr != NULL) {
sum += ptr->data;
ptr = ptr->next;
}
cout << "Sum of nodes = "<< sum;
return 0;
}
실행 결과
Sum of nodes = 260
위 코드에서는 while 문이 헤드 포인터(ptr)를 기준으로 한 칸씩 앞으로 이동하면서 각 노드의 data 값을 sum에 누적합니다. 리스트 전체를 한 번만 순회하므로 시간 복잡도는 O(n)입니다.
방법 2: 재귀 함수(Recursive Function)를 이용한 방식
재귀 함수를 활용하면 반복문 없이도 노드의 합을 구할 수 있습니다. 재귀 함수는 연결 리스트에 노드가 남아 있는 동안 자기 자신을 계속 호출하며, 호출 시마다 다음 노드의 주소와 합계 변수의 주소를 매개변수로 전달합니다. 리스트의 끝(NULL)에 도달하면 재귀 호출이 종료되고, 돌아오는 과정에서 각 노드의 값이 합산됩니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void push(struct Node** head_ref, int new_data) {
struct Node* new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void nodesum(struct Node* head, int* sum) {
if (!head)
return;
nodesum(head->next, sum);
*sum = *sum + head->data;
}
int main() {
struct Node* head = NULL;
int sum= 0;
push(&head, 95);
push(&head, 60);
push(&head, 87);
push(&head, 6);
push(&head, 12);
nodesum(head,&sum);
cout << "Sum of nodes = "<<sum;
return 0;
}
실행 결과
Sum of nodes = 260
재귀 방식 역시 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 다만 재귀 호출이 깊어질 경우 스택 메모리를 추가로 사용한다는 점을 유의해야 하며, 노드 수가 매우 많은 리스트라면 반복문 방식이 더 안전한 선택이 될 수 있습니다.
정리
단일 연결 리스트의 노드 합은 반복문 방식과 재귀 함수 방식 두 가지로 구현할 수 있으며, 두 방법 모두 동일한 결과(O(n))를 얻을 수 있습니다. 상황과 메모리 제약 조건에 맞는 방법을 선택해 사용하면 됩니다.