C 언어로 연결 리스트(Linked List)를 실제로 뒤집지 않고 역순으로 출력하기

이 글에서는 재귀 함수를 이용해 주어진 연결 리스트(Linked List)를 역순으로 출력하는 방법을 알아봅니다. 여기서 중요한 점은 리스트의 노드 순서는 그대로 유지한 채, 화면에는 역순으로 출력만 한다는 것입니다. 즉, 실제로 리스트를 뒤집지 않습니다.

프로그램은 첫 번째 노드의 주소를 담고 있는 head 포인터가 마지막 노드에 저장된 NULL을 만날 때까지 다음 노드로 이동하면서, 각 단계에서 head 노드의 데이터를 출력하는 방식으로 동작합니다.

동작 원리

먼저 노드들을 리스트에 삽입하고, 포인터가 삽입된 노드들을 가리키도록 합니다. 리스트가 완성되면 temp 포인터를 첫 번째 노드로 초기화하고, 마지막 노드의 next 주소가 NULL이 될 때까지 계속 앞으로 이동시킵니다. 그런 다음 재귀 호출이 되감기면서 마지막 노드부터 head 포인터 방향으로 거슬러 올라가며 데이터를 출력합니다.

핵심 아이디어는 재귀 호출을 먼저 수행하고, 복귀 시점에 데이터를 출력하는 것입니다. 이렇게 하면 리스트 구조를 변경하지 않고도 자연스럽게 역순 출력이 가능합니다.

예제

입력: 29 34 43 56
출력: 56 43 34 29

알고리즘

START
    Step 1 -> 노드 구조체 변수 생성
        int data 선언
        node 타입 포인터 *next 선언
    Step 2 -> void reverse(node* head) 함수 선언
        IF head == NULL
            return
        reverse(head->next) 재귀 호출
        head->data 출력
    Step 3 -> void push(node** header, char newdata) 함수 선언
        malloc으로 메모리 할당
        newnode->data = newdata 설정
        newnode->next = (*header) 설정
        (*header) = newnode 설정
    Step 4 -> main() 함수에서
        node* head = NULL 로 리스트 생성
        push(&head, 56) 등으로 요소 삽입
        reverse(head) 호출
STOP

C 언어 구현 코드

아래 코드는 위에서 설명한 알고리즘의 C 언어 구현 예시입니다.

#include<stdio.h>
#include<stdlib.h>
// 노드를 위한 구조체 정의
struct node {
    int data;
    node* next;
};
// 리스트의 데이터를 역순으로 출력하는 함수
void reverse(node* head) {
    if (head == NULL)
        return;
    reverse(head->next);
    printf("%d ", head->data);
}
// 리스트에 노드를 삽입(push)하는 함수
void push(node** header, char newdata) {
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    newnode->data = newdata;
    newnode->next = (*header);
    (*header) = newnode;
}
int main() {
    node* head = NULL;
    push(&head, 56); // 리스트에 56 삽입
    push(&head, 43);
    push(&head, 34);
    push(&head, 29);
    reverse(head);
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

reverse of a linked list 56 43 34 29

정리

이 방법의 장점은 원본 연결 리스트를 전혀 수정하지 않으면서도 O(n) 시간 복잡도로 역순 출력이 가능하다는 것입니다. 다만 재귀 호출 특성상 리스트가 매우 길 경우 스택 오버플로(stack overflow)가 발생할 수 있으므로, 대용량 데이터에는 반복문 기반 방식을 고려하는 것이 좋습니다.