C++で単方向リンクリストをXORリンクリストに変換する方法

はじめに

このチュートリアルでは、単方向リンクリスト(片方向連結リスト)をXORリンクリストに変換するプログラムについて解説します。

単方向リンクリストが与えられたとき、その要素を保持したまま、各ノードのnextポインタを「前のノードのアドレスと次のノードのアドレスのXOR値」に書き換えることで、XORリンクリストへと変換するのが目的です。

XORリンクリストとは

XORリンクリストは、通常の双方向リンクリストで必要となるprevポインタとnextポインタを1つのポインタにまとめた、メモリ効率に優れたデータ構造です。各ノードには「前のノードのアドレス XOR 次のノードのアドレス」のみを格納し、走査時には直前に訪れたノードのアドレスを利用して次のノードのアドレスを復元します。

アルゴリズムの流れ

1. 現在のノード(curr)と前のノード(prev)を用意し、curr->nextから次のノード(next)を取得します。
2. curr->nextをXOR(prev, next)の結果で上書きします。
3. prev = curr、curr = next として更新し、リストの末尾まで繰り返します。

C++での実装例

#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));
}
// 単方向リンクリストの変換
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;
}

出力結果

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

コードのポイント

XOR関数では、ポインタをuintptr_t型にキャストしてからXOR演算を行い、その結果を再びNode*型にキャストして返しています。これにより、アドレス同士を安全にビット演算できます。

printXOR関数では、直前に参照したノードのアドレス(prev)と各ノードに格納されたXOR値を組み合わせることで、次のノードのアドレスを順に復元しながら走査しています。出力結果から、変換後もデータが同じ順序(1 2 3 4)で保持されていることが確認できます。