이 글에서는 이중 연결 리스트(Doubly Linked List)를 다루고, C++로 이 리스트를 반전(뒤집기)하는 여러 가지 방법을 설명합니다. 예를 들면 다음과 같습니다.
입력 : {1, 2, 3, 4}
출력 : {4, 3, 2, 1}보통 떠오르는 방법은 한 가지지만, 여기서는 두 가지 방법을 모두 살펴보겠습니다. 바로 일반적인(normal) 방법과 비전통적(unorthodox) 방법입니다.
1. 일반적인 방법 — 순회하면서 포인터 교환하기
이 방법은 리스트를 처음부터 끝까지 순회하면서, 지나가는 각 노드의 next 포인터와 prev 포인터를 서로 맞바꾸는 방식입니다. 순회가 끝나면 원래 마지막에 있던 노드가 자연스럽게 새로운 head가 됩니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node *next;
Node *prev;
};
void reverse(Node **head_ref) {
auto temp = (*head_ref) -> next;
(*head_ref) -> next = (*head_ref) -> prev;
(*head_ref) -> prev = temp;
if(temp != NULL) {
(*head_ref) = (*head_ref) -> prev;
reverse(head_ref);
}
else
return;
}
void push(Node** head_ref, int new_data) {
Node* new_node = new Node();
new_node->data = new_data;
new_node->prev = NULL;
new_node->next = (*head_ref);
if((*head_ref) != NULL)
(*head_ref) -> prev = new_node;
(*head_ref) = new_node;
}
int main() {
Node* head = NULL;
push(&head, 6);
push(&head, 4);
push(&head, 8);
push(&head, 9);
auto node = head;
cout << "Before\n";
while(node != NULL) {
cout << node->data << " ";
node = node->next;
}
cout << "\n";
reverse(&head);
node = head;
cout << "After\n";
while(node != NULL) {
cout << node->data << " ";
node = node->next;
}
return 0;
}
실행 결과
Before
9 8 4 6
After
6 4 8 9
이 방법의 시간 복잡도는 O(N)으로 매우 효율적입니다. 덕분에 데이터 크기(N)가 커지는 높은 제약 조건에서도 충분히 빠르게 동작합니다.
2. 비전통적 방법 — 스택(Stack) 활용하기
이름 그대로 사용자가 흔히 떠올리기 어려운 방식이지만, 알아두면 유용한 기법입니다. 이 방법에서는 리스트를 순회하면서 모든 노드를 스택에 차례로 넣고(push), 이후 스택에서 하나씩 꺼내면서(pop) 각 노드의 prev와 next 포인터를 서로 교체해 리스트 전체를 반전시킵니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node *next;
Node *prev;
};
void push(Node** head_ref, int new_data) {
Node* new_node = new Node();
new_node->data = new_data;
new_node->prev = NULL;
new_node->next = (*head_ref);
if((*head_ref) != NULL)
(*head_ref) -> prev = new_node;
(*head_ref) = new_node;
}
int main() {
Node* head = NULL;
push(&head, 6);
push(&head, 4);
push(&head, 8);
push(&head, 9);
auto node = head;
cout << "Before\n";
while(node != NULL) {
cout << node->data << " ";
node = node->next;
}
cout << "\n";
// 모든 노드를 스택에 저장하면서 마지막 노드를 head로 갱신
stack<Node*> s;
node = head;
while(node) {
head = node;
s.push(node);
node = node -> next;
}
// 스택에서 꺼내면서 prev와 next 포인터를 교환
while(!s.empty()) {
auto x = s.top();
auto temp = x -> prev;
x -> prev = x -> next;
x -> next = temp;
s.pop();
}
node = head;
cout << "After\n";
while(node != NULL) {
cout << node->data << " ";
node = node->next;
}
return 0;
}
실행 결과
Before
9 8 4 6
After
6 4 8 9
코드 설명
이 방법의 핵심 동작은 다음과 같습니다.
첫 번째 단계에서는 리스트를 순회하면서 모든 노드를 스택에 쌓습니다. 이때 순회가 끝난 시점의 head는 자동으로 마지막 노드를 가리키게 됩니다. 두 번째 단계에서는 스택이 빌 때까지 노드를 하나씩 꺼내면서 각 노드의 prev와 next 포인터를 맞바꿉니다. 이 과정이 끝나면 연결 방향이 완전히 뒤집혀 리스트가 반전됩니다.
참고로 원본 코드에는 출력 스트림 연산자가 >>로 잘못 표기된 부분이 있었는데, 올바른 출력을 위해서는 위 코드처럼 cout <<를 사용해야 합니다.
이 프로그램의 시간 복잡도 역시 O(N)이므로, 높은 제약 조건에서도 무리 없이 사용할 수 있습니다.
마무리
이번 글에서는 이중 연결 리스트를 스택을 사용하거나 사용하지 않고 반전하는 문제를 해결했습니다. 두 방법 모두 O(N) 시간 복잡도(N은 리스트의 크기)를 가지며, 각각의 완전한 구현 코드와 접근 과정을 함께 살펴보았습니다. 같은 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다. 이 글이 여러분의 학습에 도움이 되기를 바랍니다.