XORリストの基本概念

XORリストは、各ノードが前後のノードのアドレスをXOR演算子を使って1つのポインタフィールドに格納する特別な連結リストです。これにより、通常の双方向リストで必要な2つのポインタ（前と次）の代わりに、1つのポインタフィールドで済むため、メモリ使用量を削減できます。

この手法の鍵となるのは、XOR演算子の性質です。AとBがポインタ（アドレス）である場合、A ^ Bの結果は、AとBの両方のビットが異なる部分を表します。そして、この結果に再度BをXORすると、元のAが復元されます。

例: (A ^ B) ^ B = A

この性質を利用して、ノード内に「前のノードのアドレス ^ 次のノードのアドレス」という値を保存します。これにより、現在のノードと「直前に訪れたノード」のアドレスが分かれば、「次のノード」のアドレスを計算で求めることができます。

実装

まず、ノードとリストの構造体を定義します。ポインタのアドレス演算を行うため、uintptr_t型を使用します。

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

typedef struct XORNode {
    int data;
    uintptr_t ptr; // 前のノードと次のノードのアドレスをXORした値
} XORNode;

typedef struct XORList {
    XORNode* head;
    XORNode* tail;
} XORList;

ノードの作成

新しいノードを作成するヘルパー関数です。データと、初期状態のXORポインタ（0）を設定します。

XORNode* createNode(int value) {
    XORNode* newNode = (XORNode*)malloc(sizeof(XORNode));
    if (!newNode) return NULL; // メモリ確保失敗

    newNode->data = value;
    newNode->ptr = 0; // 初期状態では前後のノードがないため0
    return newNode;
}

ノードの追加

リストの末尾に新しいノードを追加する関数です。空のリストの場合と、すでにノードがある場合で処理を分けます。

void appendNode(XORList* list, int value) {
    XORNode* newNode = createNode(value);

    if (list->head == NULL) {
        // リストが空の場合
        list->head = newNode;
        list->tail = newNode;
    } else {
        // リストが空でない場合
        // 新しいノードのptrを、現在の末尾ノードのアドレスとXORする
        newNode->ptr = (uintptr_t)list->tail;
        // 現在の末尾ノードのptrを更新する
        // 末尾ノードのptrは「前のノード ^ 次のノード」なので、
        // 新しいノードのアドレスをXORして「前のノード ^ 新しいノード」にする
        list->tail->ptr ^= (uintptr_t)newNode;
        // リストの末尾を新しいノードに更新
        list->tail = newNode;
    }
}

リストの走査

リストを順方向に走査するための関数です。前のノードのアドレスを覚えておく必要があります。

XORNode* getNextNode(XORNode* currentNode, XORNode** prevNode) {
    XORNode* nextNode = (XORNode*)(currentNode->ptr ^ (uintptr_t)*prevNode);
    *prevNode = currentNode; // 前のノードを更新
    return nextNode;
}

void traverseList(XORList* list) {
    XORNode* currentNode = list->head;
    XORNode* prevNode = NULL;

    while (currentNode != NULL) {
        printf("%d ", currentNode->data);
        XORNode* temp = currentNode;
        currentNode = getNextNode(currentNode, &prevNode);
    }
    printf("
");
}

末尾ノードの削除

リストの末尾からノードを削除する関数です。

void detachTail(XORList* list) {
    if (list->tail == NULL) {
        // リストが空
        return;
    }

    if (list->head == list->tail) {
        // ノードが1つだけの場合
        free(list->tail);
        list->head = NULL;
        list->tail = NULL;
    } else {
        // ノードが2つ以上の場合
        XORNode* oldTail = list->tail;
        XORNode* newTail = (XORNode*)(oldTail->ptr); // 新しい末尾ノード

        // 新しい末尾ノードのptrを更新する
        // これまでのptrは「前のノード ^ 旧末尾ノード」なので、
        // 旧末尾ノードのアドレスをXORして「前のノード」だけに戻す
        newTail->ptr ^= (uintptr_t)oldTail;

        // リストの末尾を更新して、旧末尾ノードを解放
        list->tail = newTail;
        free(oldTail);
    }
}