Problem-6
c++
Question
This problem was asked by Google. 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.
#include <iostream>
class Node;
Node* XOR(Node* a,Node* b){
return (Node*) ((uintptr_t) (a) ^ (uintptr_t) (b));
};
class Node{
public:
int val;
Node* nextPtr;
Node(int val,Node* prev,Node* next){
this->val = val;
this->nextPtr = XOR(prev,next);
}
Node* getNext(Node* prev){
return XOR(prev,this->nextPtr);
}
};
void add(Node* &head,int val);
int get(int index, Node* current);
void printList(Node* head);
int main(){
Node* head = NULL;
add(head,3);
add(head,4);
add(head,5);
add(head,7);
std::cout << get(0,head) << std::endl;
std::cout << get(1,head) << std::endl;
std::cout << get(2,head) << std::endl;
return 0;
}
int get(int index, Node* current){
Node* prev = NULL;
while(index && current!=NULL){
Node* next = XOR(prev,current->nextPtr);
prev = current;
current = next;
index--;
}
return current->val;
}
void printList(Node* head){
Node* current = head;
Node* pre = NULL;
Node* next;
while(current!=NULL){
std::cout << current->val << std::endl;
next = XOR(pre,current->nextPtr);
pre = current;
current = next;
}
}
void add(Node* &head,int val){
if(head == NULL){
head = new Node(val,NULL,NULL);
}
else{
Node* prev = NULL;
Node* current = head;
Node* next = XOR(prev,current->nextPtr);
while(next!=NULL){
prev = current;
current = next;
next = XOR(prev,current->nextPtr);
}
Node* node = new Node(val,current,NULL);
current->nextPtr = XOR(prev,node);
}
}