Posted by chunyang on July 5, 2020

### Problem

An XOR linked list is a more memory efficient doubly linked list. Instead of each node holding next and prev fields, it holds a field named both, which is an XOR of the next node and the previous node. Implement an XOR linked list; it has an add(element) which adds the element to the end, and a get(index) which returns the node at index.

If using a language that has no pointers (such as Python), you can assume you have access to get_pointer and dereference_pointer functions that converts between nodes and memory addresses.

### Solution

• Assume: get(index), index >=0, a valid index
#include <iostream>
using namespace std;

template<int n>
struct PointerSize {
typedef int Type;
};

template<>
struct PointerSize<8> {
typedef long Type;
};

template<>
struct PointerSize<4> {
typedef int Type;
};

typedef PointerSize<sizeof(int*)>::Type  PointerType;

struct ListNode {
int val;
PointerType both;
ListNode(int v): val(v), both(0) {};
};

public:

}

cout << "Adding value: " << val << endl;
if (tail == nullptr) {
head = tail = new ListNode(val);
} else {
ListNode* new_node = new ListNode(val);
tail->both = tail->both ^ (PointerType)(new_node);
new_node->both = (PointerType)tail;
tail = new_node;
}
cout << "head: " << head->val << " tail: " << tail->val << endl;
}
void print() {
PointerType prev = 0;
while (node) {
cout << node->val << ", ";
ListNode* next = (ListNode*)(node->both ^ prev);
prev = (PointerType)node;
node = next;
}
cout << endl;
}
ListNode* get(int index) {
int count = 0;
ListNode* prev = 0;
while (count < index) {
ListNode* next = (ListNode*)(node->both ^ (PointerType)prev);
prev = node;
node = next;
++count;
}
return node;

}

private:
ListNode* tail;
};

int main() {