C 언어로 연결 리스트(Linked List)의 길이 구하기 – 재귀 함수 활용 완벽 가이드

연결 리스트(Linked List)는 동적 메모리 할당(dynamic memory allocation)을 사용하는 자료구조입니다. 즉, 데이터가 추가되거나 삭제될 때 필요에 따라 크기가 늘어나거나 줄어들 수 있습니다.

연결 리스트는 여러 개의 노드(node)로 구성된 집합으로 정의되며, 각 노드는 두 부분으로 이루어져 있습니다.

• 데이터(Data) : 실제 저장되는 값
• 링크(Link) : 다음 노드를 가리키는 포인터

연결 리스트의 종류

연결 리스트는 크게 네 가지 유형으로 나눌 수 있습니다.

• 단일 연결 리스트(Singly Linked List)
• 이중 연결 리스트(Doubly Linked List)
• 원형 단일 연결 리스트(Circular Singly Linked List)
• 원형 이중 연결 리스트(Circular Doubly Linked List)

재귀 함수로 길이를 구하는 핵심 로직

연결 리스트의 길이(노드 개수)를 구할 때 재귀(recursion) 방식을 활용하면 코드가 매우 간결해집니다. 기본 아이디어는 다음과 같습니다.

1. 현재 노드가 NULL이면(리스트의 끝에 도달하면) 지금까지 센 값을 반환합니다.
2. NULL이 아니라면 카운트를 1 증가시키고, 다음 노드를 인자로 하여 자기 자신을 다시 호출합니다.

int length(node *temp){
    if(temp==NULL)
        return l;
    else{
        l=l+1;
        length(temp->next);
    }
}

C 프로그램 전체 코드

다음은 사용자로부터 데이터를 입력받아 연결 리스트를 만든 뒤, 재귀 함수를 통해 리스트의 길이를 출력하는 C 프로그램입니다.

#include <stdio.h>
#include <stdlib.h>
typedef struct linklist{
    int data;
    struct linklist *next;
}node;
int l=0;
int main(){
    node *head=NULL,*temp,*temp1;
    int len,choice,count=0,key;
    do{
        temp=(node *)malloc(sizeof(node));
        if(temp!=NULL){
            printf("\nenter the elements in a list : ");
            scanf("%d",&temp->data);
            temp->next=NULL;
            if(head==NULL){
                head=temp;
            }else{
                temp1=head;
                while(temp1->next!=NULL){
                    temp1=temp1->next;
                }
                temp1->next=temp;
            }
        }else{
            printf("\nMemory is full");
        }
        printf("\npress 1 to enter data into list: ");
        scanf("%d",&choice);
    }while(choice==1);
    len=length(head);
    printf("The list has %d no of nodes",l);
    return 0;
}
//길이를 구하는 재귀 함수
int length(node *temp){
    if(temp==NULL)
        return l;
    else{
        l=l+1;
        length(temp->next);
    }
}

코드 동작 방식

• malloc()을 사용해 새 노드를 동적으로 생성하고, 사용자에게 데이터를 입력받습니다.
• 첫 번째 노드라면 head에 저장하고, 그렇지 않으면 마지막 노드까지 순회한 뒤 새 노드를 연결합니다.
• 사용자가 1을 입력하면 계속 데이터를 추가하고, 다른 값을 입력하면 입력을 종료합니다.
• 마지막으로 length() 함수를 호출하여 전체 노드 수를 계산해 출력합니다.

실행 결과

위 프로그램을 실행하면 다음과 같은 결과를 확인할 수 있습니다.

Run 1:
enter the elements in a list: 3
press 1 to enter data into list: 1
enter the elements in a list: 56
press 1 to enter data into list: 1
enter the elements in a list: 56
press 1 to enter data into list: 0
The list has 3 no of nodes
Run 2:
enter the elements in a list: 12
press 1 to enter data into list: 1
enter the elements in a list: 45
press 1 to enter data into list: 0
The list has 2 no of nodes

첫 번째 실행에서는 3개의 노드를, 두 번째 실행에서는 2개의 노드를 입력했으며, 프로그램이 각각 올바른 노드 개수를 정확히 출력한 것을 확인할 수 있습니다.