C++에서 단일 연결 리스트를 XOR 연결 리스트로 변환하는 방법

이 튜토리얼에서는 C++를 사용하여 단일 연결 리스트(singly linked list)를 XOR 연결 리스트(XOR linked list)로 변환하는 방법을 알아봅니다. 주어진 단일 연결 리스트의 노드들을 그대로 활용해, 각 노드의 포인터를 XOR 연산 기반 구조로 바꾸는 것이 목표입니다.

XOR 연결 리스트란?

XOR 연결 리스트는 메모리 사용량을 줄이기 위해 고안된 특수한 형태의 연결 리스트입니다. 각 노드는 포인터 필드를 하나만 가지며, 이 필드에는 이전 노드의 주소와 다음 노드의 주소를 비트 단위 XOR 연산한 값이 저장됩니다. 덕분에 양방향 탐색이 가능하면서도 일반적인 이중 연결 리스트보다 노드당 포인터 하나를 절약할 수 있습니다.

변환 원리

변환은 생각보다 간단합니다. 리스트를 처음부터 끝까지 순회하면서 각 노드의 next 필드에 (이전 노드 주소) XOR (다음 노드 주소) 값을 저장하면 됩니다. 첫 번째 노드는 이전 노드가 없으므로 NULL과 다음 노드 주소를 XOR하게 되는데, 이는 다음 노드 주소 그 자체와 같습니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;

// 연결 리스트의 노드 구조체
struct Node {
    int data;
    struct Node* next;
};

// 새로운 노드 생성
Node* newNode(int data){
    Node* temp = new Node;
    temp->data = data;
    temp->next = NULL;
    return temp;
}

// 단일 연결 리스트 출력
void print(Node* head){
    while (head) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

// 두 노드 주소의 XOR 값 계산
Node* XOR(Node* a, Node* b){
    return (Node*)((uintptr_t)(a) ^ (uintptr_t)(b));
}

// 단일 연결 리스트를 XOR 연결 리스트로 변환
void convert(Node* head){
    Node* curr = head;
    Node* prev = NULL;
    Node* next = curr->next;
    while (curr) {
        next = curr->next;
        curr->next = XOR(prev, next);
        prev = curr;
        curr = next;
    }
}

// XOR 연결 리스트 출력
void printXOR(Node* head){
    Node* curr = head;
    Node* prev = NULL;
    while (curr) {
        cout << curr->data << " ";
        Node* temp = curr;
        curr = XOR(prev, curr->next);
        prev = temp;
    }
    cout << endl;
}

int main(){
    Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    cout << "Before Conversion : " << endl;
    print(head);
    convert(head);
    cout << "After Conversion : " << endl;
    printXOR(head);
    return 0;
}

코드 설명

newNode() : 새로운 노드를 생성하고 데이터를 초기화한 뒤 반환합니다.
print() : 변환 전의 일반 단일 연결 리스트를 순서대로 출력합니다.
XOR() : 두 노드의 주소를 uintptr_t로 캐스팅하여 비트 단위 XOR 연산을 수행한 후, 다시 Node* 형태로 반환합니다.
convert() : prev, curr, next 세 개의 포인터를 활용해 리스트를 순회하면서 각 노드의 next 필드를 XOR 값으로 교체합니다.
printXOR() : 이전 노드의 주소를 추적하며 XOR 값을 디코딩해, 변환된 리스트를 올바른 순서로 출력합니다.

실행 결과

Before Conversion :
1 2 3 4
After Conversion :
1 2 3 4

출력 결과에서 볼 수 있듯이 변환 전후의 데이터 출력은 동일합니다. 내부적으로는 각 노드의 next 포인터가 XOR 연산된 주소 값으로 대체되었지만, printXOR() 함수가 이전 노드 정보를 이용해 원래의 순서를 복원하기 때문입니다.

마무리

이처럼 단일 연결 리스트는 각 노드의 next 포인터를 '이전 노드 XOR 다음 노드' 값으로 교체하는 것만으로 간단히 XOR 연결 리스트로 변환할 수 있습니다. 다만 포인터에 대한 비트 연산은 플랫폼에 따라 동작이 달라질 수 있고 디버깅이 까다롭기 때문에, 실무에서는 메모리 제약이 매우 엄격한 임베디드 환경 등에서 주로 활용됩니다.