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

문제 개요

불변(immutable) 연결 리스트가 하나 주어져 있다고 가정해 보겠습니다. 이 리스트는 수정할 수 없기 때문에 일반적인 방법처럼 포인터를 조작해 뒤집을 수 없으며, 대신 주어진 인터페이스를 활용해 각 노드의 값을 역순으로 모두 출력해야 합니다.

ImmutableListNode — 불변 연결 리스트의 인터페이스이며, 리스트의 머리(head) 노드가 입력으로 주어집니다.

연결 리스트에 접근할 수 있는 함수는 아래 두 가지뿐입니다.

printValue() — 현재 노드의 값을 출력합니다.
getNext() — 다음 노드를 반환합니다.

예를 들어 리스트가 [0, -4, -1, 3, -5]라면, 출력 결과는 역순인 [-5, 3, -1, -4, 0]이 되어야 합니다.

접근 방법: 스택 활용

리스트가 불변이므로 직접 뒤집는 것은 불가능하지만, 스택의 LIFO(후입선출) 특성을 활용하면 매우 간단하게 해결할 수 있습니다. 노드를 앞에서부터 차례대로 스택에 쌓은 뒤, 하나씩 꺼내면서 출력하면 자연스럽게 역순으로 값이 나옵니다.

알고리즘 단계

ImmutableListNode 타입의 노드를 저장할 스택 st를 선언합니다.
head가 null이 아닐 때까지 반복합니다.
- 현재 head 노드를 스택 st에 삽입합니다.
- head를 다음 노드(getNext())로 이동시킵니다.
스택이 빌 때까지 반복합니다.
- 스택 최상단(top) 노드의 값을 출력합니다.
- 스택에서 해당 노드를 제거(pop)합니다.

C++ 구현 예제

아래 구현을 통해 더 잘 이해해 보겠습니다.

class Solution {
public:
    void printLinkedListInReverse(ImmutableListNode* head) {
        stack<ImmutableListNode*> st;
        while(head){
            st.push(head);
            head = head->getNext();
        }
        while(!st.empty()){
            st.top()->printValue();
            st.pop();
        }
    }
};

실행 예시

입력

[0,-4,-1,3,-5]

출력

[-5,3,-1,-4,0]

복잡도 분석

시간 복잡도: O(n) — 리스트를 한 번 순회하고, 스택에서 각 노드를 한 번씩 꺼내므로 전체적으로 선형 시간이 소요됩니다.

공간 복잡도: O(n) — 모든 노드를 스택에 저장해야 하므로 노드 수에 비례하는 추가 메모리가 필요합니다.

참고: 재귀를 이용한 대안

스택 자료구조 대신 재귀 호출의 콜 스택을 활용할 수도 있습니다. 다음 노드부터 먼저 처리한 뒤 현재 노드의 값을 출력하도록 재귀 함수를 작성하면, 별도의 컨테이너 없이도 역순 출력이 가능합니다. 단, 리스트가 매우 긴 경우에는 스택 오버플로우가 발생할 수 있으므로 상황에 맞게 선택하는 것이 좋습니다.