#include <iostream>
#include <stdint.h>
#include <stdlib.h>
using namespace std;
class XORNode {
int value;
uintptr_t both; // uintptr_t is an unsigned integer capable of storing a pointer
public:
// Constructor
XORNode(int val, uintptr_t addr = 0) {
value = val;
both = addr;
}
int getValue() {
return value;
}
uintptr_t getAddr() {
return both;
}
void setValue(int val) {
value = val;
}
void setAddr(uintptr_t addr) {
both = addr;
}
};
class XORLinkedList {
XORNode* head;
XORNode* tail;
int elements;
public:
XORLinkedList() { // Creates an empty XOR Linked List
head = NULL;
tail = NULL;
elements = 0;
}
// Declaration of other methods
void add(int val);
XORNode* get(int val);
};
void XORLinkedList::add(int val) {
XORNode *prev = NULL, *curr = head, *temp;
/* Since we are adding element to the end, let's traverse to the last element */
if (head != NULL) {
while ((XORNode*)(curr->getAddr() ^ (uintptr_t)prev) != NULL) {
temp = prev;
prev = curr;
curr = (XORNode*)(curr->getAddr() ^ (uintptr_t)temp);
}
}
/* Allocate memory and set the value of the element. The memory address field will
be the XOR of the previous and next pointers of the newNode. The previous pointer
of the newNode is the current last node (curr) and the next pointer is NULL */
XORNode *newNode = (XORNode*)malloc(sizeof(XORNode));
newNode->setValue(val);
newNode->setAddr((uintptr_t)curr ^ (uintptr_t)NULL);
// If the list is empty, make the newNode as the head of the linked list
if (head == NULL && tail == NULL) {
head = newNode;
}
/* The memory address field of the current last node (curr) will be the XOR of
its previous node (prev) and the newNode */
curr->setAddr((uintptr_t)prev ^ (uintptr_t)newNode);
tail = newNode;
elements++; // We'll understand its use a little later
cout << "Inserted node with value " << val << "\n"; // Helpful message
}
XORNode* XORLinkedList::get(int index) {
/* Check if index is less than the number of elements */
if (index >= elements) {
cout << "Not as many values!" << endl;
exit(1);
}
/* Element is located in the first half of the linked list,
so start searching from the beginning of the list (Now you know
why we were storing the number of elements in the list) */
if (index < elements/2) {
XORNode *prev = NULL, *curr = head, *temp;
int curr_index = 0;
while (curr != NULL) {
if (curr_index == index) {
return curr;
}
temp = prev;
prev = curr;
curr = (XORNode*)(curr->getAddr() ^ (uintptr_t)temp);
curr_index++;
}
}
/* Element is located in the last half of the linked list,
so start searching from the end of the list */
else {
XORNode *prev = NULL, *curr = tail, *temp;
int curr_index = elements-1;
while (curr != NULL) {
if (curr_index == index) {
return curr;
}
temp = prev;
prev = curr;
curr = (XORNode*)(curr->getAddr() ^ (uintptr_t)temp);
curr_index--;
}
}
}
int main() {
XORLinkedList linked_list = XORLinkedList();
linked_list.add(2);
linked_list.add(3);
linked_list.add(4);
linked_list.add(5);
cout << "Element at index 0: " << linked_list.get(0) -> getValue() << endl;
cout << "Element at index 1: " << linked_list.get(1) -> getValue() << endl;
cout << "Element at index 2: " << linked_list.get(2) -> getValue() << endl;
cout << "Element at index 3: " << linked_list.get(3) -> getValue() << endl;
return 0;
}
