노드들로 구성된 순환 연결 리스트가 주어졌을 때, 이 리스트에 포함된 노드의 개수를 계산하는 것이 목표입니다.
순환 연결 리스트(Circular Linked List)는 연결 리스트의 한 변형으로, 첫 번째 요소가 마지막 요소를 가리키고 마지막 요소가 다시 첫 번째 요소를 가리키는 구조를 가집니다. 단일 연결 리스트(Singly Linked List)와 이중 연결 리스트(Doubly Linked List) 모두 순환 연결 리스트로 만들 수 있습니다.
이 글에서는 단일 연결 리스트를 순환 연결 리스트 형태로 구현한 뒤, 해당 리스트의 노드 개수를 계산하는 방법을 알아보겠습니다.
예시
입력 − 노드: 20, 1, 2, 3, 4, 5
출력 − 노드 개수: 6
입력 − 노드: 20, 1, 2, 3, 4, 5, 7, 8, 9, 12
출력 − 노드 개수: 10
아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.
노드가 담고 있는 데이터와 다음 노드의 주소를 포함하는 단일 연결 리스트용 구조체(struct)를 정의합니다.
노드에 데이터를 삽입하는 push() 함수를 작성합니다.
마지막 노드에 첫 번째 노드의 주소를 저장하여, 단일 연결 리스트가 순환 연결 리스트처럼 동작하도록 만듭니다.
순환 연결 리스트에 존재하는 전체 노드의 개수를 세는 count_fun() 함수를 작성합니다.
예제 코드
#include <stdio.h>
#include <stdlib.h>
/* 노드 구조체 정의 */
struct node {
int data;
struct node* next;
};
// 순환 리스트에 노드 삽입
void push(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 count_fun(struct node* head){
struct node* temp = head;
int result = 0;
if (head != NULL){
do {
temp = temp->next;
result++;
} while (temp != head);
}
return result;
}
int main(){
/* 리스트를 빈 상태로 초기화 */
struct node* head = NULL;
push(&head, 10);
push(&head, 20);
push(&head, 30);
push(&head, 40);
printf("노드 개수: %d", count_fun(head));
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
노드 개수: 4
핵심은 count_fun() 함수에서 do-while 반복문을 사용한다는 점입니다. 순환 연결 리스트는 시작점으로 되돌아오기 때문에 일반 while 문 대신, 최소 한 번은 본문을 실행한 뒤 조건을 검사하는 do-while 문이 종료 조건 처리에 더 적합합니다. 또한 리스트가 비어 있는 경우(head == NULL)를 먼저 확인하여 잘못된 참조를 방지하고 0을 반환하도록 처리했습니다.