Example: XOR Linked List

XOR linked lists are used to reduce the memory requirements of doubly-linked lists.

We know that each node in a doubly-linked list has two pointer fields which contain the addresses of the previous and next node. On the other hand, each node of the XOR linked list requires only a single pointer field, which doesn’t store the actual memory addresses but stores the bitwise XOR of addresses for its previous and next node.

// cpp example, direct bits manipulation in java is not allowed, you would have to use
// some trick such as associating and maintaining a map between a counter and the node
// to retrieve a valid number to XOR
struct Node {
    int data;
    Node* both; // XOR of the previous and next node addresses
}

void forwardTraversal() {
    // address of next Node = (address of prev Node) ^ (both)
    Node* prev;
    // Curr points to the first node
    // of the XOR Linked list
    Node* curr = head;
    Node* next;
    While(curr != NULL) {
        cout << curr->data;
        // both represents the XOR value .
        next = prev ^ curr->both;
        prev = curr;
        curr = next;
    }
}

void backwardTraversal() {
    // address of previous Node = (address of next Node) ^ (both)
    Node* curr = lastNode;
    Node* prev, *next=NULL;
    While (curr != NULL) {
        cout << curr->data;
        // both represents the XOR value .
        next = prev ^ curr->both;
        prev = curr;
        curr = next;
    }
}

void headInsert(int data)
{
    Node* newNode = new Node();
    newNode ->data = data;
    newNode ->both = XOR(nullptr, head);

    if (head) {
        head->both = XOR(newNode , XOR(head->both, nullptr));
    }
    else {
        // If the list was empty, the new
        // node is both the head and the
        // tail
        tail = newNode ;
    }
    // Update the head to the new node
    head = newNode ;
}