C++에서 스택을 활용해 연결 리스트 반전하기

개요

연결 리스트(Linked List)는 각 노드가 데이터와 다음 노드를 가리키는 포인터로 구성되며, 필요할 때마다 메모리를 동적으로 할당하는 자료 구조입니다. 흥미롭게도 이러한 연결 리스트는 스택을 구현하는 데에도 활용할 수 있습니다. 이 글에서는 스택의 LIFO(Last In First Out, 후입선출) 특성을 활용하여 C++로 연결 리스트를 반전시키는 방법을 알아봅니다.

알고리즘

연결 리스트를 반전하기 위해 다음과 같은 절차를 따릅니다.

START
    Step 1: node 포인터 타입의 빈 스택을 생성한다
    Step 2: 리스트를 처음부터 끝까지 순회하며 모든 노드의 값을 스택에 push 한다
    Step 3: 헤드(head) 노드부터 리스트를 다시 한 번 순회한다
    Step 4: 스택 최상단(top)에서 값을 하나씩 pop 한다
    Step 5: pop 한 값들을 역순으로 연결한다
    Step 6: 결과를 출력한다
STOP

예제 코드

위 알고리즘을 바탕으로 작성된 C++ 코드는 아래와 같습니다. 여기서 stdlib.h 헤더 파일은 malloc() 같은 동적 메모리 할당 관련 핵심 함수를 제공하며, 스택은 크기 30의 정수형 배열과 top 인덱스 변수를 이용해 구현됩니다.

#include <iostream>
#include <stdlib.h>
using namespace std;
struct linked_list {
    int data;
    struct linked_list *next;
};
int stack[30], top = -1;
struct linked_list* head = NULL;
int printfromstack(int stack[]) {
    cout<<"\nStack after Reversal::";
    while(top>=0) {
        cout<<stack[top--]<<" ";
    }
}
int push(struct linked_list** head, int n) {
    struct linked_list* newnode = (struct linked_list*)malloc(sizeof(struct linked_list));
    newnode->data = n;
    newnode->next = (*head);
    (*head) = newnode;
}
int intostack(struct linked_list* head) {
    cout<<"Linked list::";
    while(head!=NULL) {
        printf("%d ", head->data);
        stack[++top] = head->data;
        head = head->next;
    }
}
int main(int argc, char const *argv[]) {
    push(&head, 7);
    push(&head, 20);
    push(&head, 3);
    push(&head, 40);
    intostack(head);
    printfromstack(stack);
    return 0;
}

코드를 살펴보면 기능별로 함수가 깔끔하게 분리되어 있습니다. push() 함수는 새 노드를 동적으로 할당해 리스트 맨 앞에 삽입하고, intostack() 함수는 연결 리스트를 순회하며 각 노드의 데이터를 스택에 차례대로 저장합니다. 마지막으로 printfromstack() 함수가 스택 최상단부터 값을 꺼내 출력하면서 반전된 순서를 보여줍니다. main() 함수에서는 7, 20, 3, 40을 순서대로 삽입한 뒤 이 두 함수를 호출해 전체 과정을 실행합니다.

실행 결과

Linked list:: 40 3 20 7
Stack after Reversal::7 20 3 40

push()가 항상 리스트의 맨 앞에 노드를 삽입하기 때문에 원본 연결 리스트는 40 → 3 → 20 → 7 순서로 출력됩니다. 그런데 이 값들이 스택에 들어갔다가 top부터 차례로 꺼내지면 7 → 20 → 3 → 40, 즉 완전히 반전된 순서가 됩니다. 이처럼 스택의 후입선출 특성만 잘 활용하면 별도의 포인터 재배열 없이도 연결 리스트를 손쉽게 반전시킬 수 있습니다.