用c++实现异或链表

#include <iostream>
#include <cstdint>

struct Node {
    int data;
    uintptr_t both; // 存储前后节点地址异或结果
};

class XORLinkedList {
public:
    XORLinkedList() : head(nullptr), tail(nullptr) {}

    void add(int data) {
        Node* newNode = new Node();
        newNode->data = data;

        if (head == nullptr) {
            newNode->both = 0;
            head = newNode;
            tail = newNode;
        } else {
            newNode->both = reinterpret_cast<uintptr_t>(tail);
            tail->both ^= reinterpret_cast<uintptr_t>(newNode);
            tail = newNode;
        }
    }

    void traverseForward() {
        Node* current = head;
        Node* prev = nullptr;
        Node* next;

        while (current != nullptr) {
            std::cout << current->data << " ";

            next = reinterpret_cast<Node*>(current->both ^ reinterpret_cast<uintptr_t>(prev));
            prev = current;
            current = next;
        }

        std::cout << std::endl;
    }

    void traverseBackward() {
        Node* current = tail;
        Node* prev = nullptr;
        Node* next;

        while (current != nullptr) {
            std::cout << current->data << " ";

            next = reinterpret_cast<Node*>(current->both ^ reinterpret_cast<uintptr_t>(prev));
            prev = current;
            current = next;
        }

        std::cout << std::endl;
    }

private:
    Node* head;
    Node* tail;
};

int main() {
    XORLinkedList list;
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);

    std::cout << "Forward traversal: ";
    list.traverseForward();

    std::cout << "Backward traversal: ";
    list.traverseBackward();

    return 0;
}