Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++에서 연결 리스트를 역순으로 출력하는 흥미로운 방법

연결 리스트(Linked List)는 데이터 요소들을 연결된 형태로 저장하는 대표적인 자료구조입니다. 각 노드는 실제 데이터를 담는 data 필드와 다음 노드를 가리키는 링크(next 포인터)로 구성됩니다.

연결 리스트의 역순 출력은 알고리즘 문제 해결에서 자주 만나게 되는 기본적인 과제 중 하나입니다. 이 글에서는 C++ 프로그래밍 언어로 연결 리스트를 역순으로 출력하는 색다르고 흥미로운 방법을 소개합니다.

일반적으로 연결 리스트를 역순으로 출력하려면 리스트 구조 자체를 뒤집거나, 재귀 호출이나 스택을 활용해 여러 번 순회해야 합니다. 하지만 여기서 소개하는 방법은 리스트를 전혀 수정하지 않으면서도 단 한 번의 순회만으로 역순 출력을 완료할 수 있습니다.

핵심 아이디어: 캐리지 리턴 활용하기

이 방법의 핵심은 캐리지 리턴(carriage return)입니다. 캐리지 리턴은 원래 프린터에게, 화면 환경에서는 커서에게 현재 줄에서 특정 위치로 이동하라는 명령을 내리는 제어 문자로, 터미널에서는 보통 커서를 그 줄의 맨 앞으로 되돌리는 역할을 합니다.

동작 원리를 정리하면 다음과 같습니다.

  1. 리스트의 길이를 n이라고 할 때, 첫 번째 요소를 출력하기 전에 n칸 분량의 공백을 먼저 확보한 상태에서 요소를 출력한 뒤, 캐리지 리턴으로 커서를 줄의 처음으로 되돌립니다.
  2. 두 번째 요소부터는 앞에 남기는 공백을 하나씩 줄여가며(예제 코드에서는 두 칸씩) 같은 방식으로 출력합니다. 즉, 첫 번째 요소 앞에는 n-1칸, 두 번째 요소 앞에는 n-2칸의 공백이 남습니다.
  3. 커서가 매번 줄의 맨 앞으로 돌아가기 때문에 새로 출력되는 요소는 이전 요소보다 왼쪽에 기록됩니다. 모든 노드의 순회가 끝나면 화면에는 요소들이 역순으로 나열된 결과가 완성됩니다.

먼저 출력된 요소일수록 화면 오른쪽 끝에 가까워지는 구조이므로, 리스트를 뒤집거나 추가 자료구조를 사용하지 않고도 역순 출력 효과를 얻을 수 있습니다. 시간 복잡도는 O(n)으로, 리스트를 정확히 한 번만 순회한다는 점이 이 방법의 가장 큰 장점입니다.

그럼 이 개념을 확인할 수 있는 예제 프로그램을 살펴보겠습니다.

예제 코드

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
struct Node {
   int data;
   struct Node* next;
};
void printReverse(struct Node** head_ref, int n) ;
void push(struct Node** head_ref, int new_data) ;
int printList(struct Node* head) ;
int main(){
   struct Node* head = NULL;
   push(&head, 2);
   push(&head, 7);
   push(&head, 3);
   push(&head, 5);
   push(&head, 4);
   push(&head, 6);
   printf("Given linked list:\n");
   int n = printList(head);
   printf("\nReversed Linked list:\n");
   printReverse(&head, n);
   return 0;
}
void printReverse(struct Node** head_ref, int n){
   int j = 0;
   struct Node* current = *head_ref;
   while (current != NULL) {
      for (int i = 0; i < 2 * (n - j); i++)
         cout<<" ";
      cout<<current->data<<"\r";
      current = current->next;
      j++;
   }
}
void push(struct Node** head_ref, int new_data){
   struct Node* new_node =
   (struct Node*)malloc(sizeof(struct Node));
   new_node->data = new_data;
   new_node->next = (*head_ref);
   (*head_ref) = new_node;
}
int printList(struct Node* head){
   int i = 0;
   struct Node* temp = head;
   while (temp != NULL) {
      printf("%d ", temp->data);
      temp = temp->next;
      i++;
   }
   return i;
}

실행 결과

Given linked list:
6 4 5 3 7 2
Reversed Linked list:
2 7 3 5 4 6

참고 사항

이 기법은 캐리지 리턴을 올바르게 처리하는 터미널 환경에서만 의도한 대로 동작합니다. 출력을 파일로 리디렉션하거나 캐리지 리턴을 지원하지 않는 환경에서는 요소들이 한 줄로 이어져 출력되므로 주의해야 합니다. 또한 실무 코드에서는 리스트를 실제로 뒤집거나 재귀·스택을 활용하는 방식이 더 안전하고 범용적이기 때문에, 이 방법은 재미있는 학습용 트릭으로 이해하는 것이 좋습니다.