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

I’m having trouble implementing the solution in Swift. The problem is with accessing the pointers. Until I come up with a better solution, here is a C++ implementation:

``````/* C/C++ Implementation of Memory efficient Doubly Linked List */
#include
#include

// Node structure of a memory efficient doubly linked list
struct node {
int data;
struct node* npx; /* XOR of next and previous node */
};

/* returns XORed value of the node addresses */
struct node* XOR (struct node *a, struct node *b) {
return (struct node*) ((unsigned int) (a) ^ (unsigned int) (b));
}

/* Insert a node at the begining of the XORed linked list and makes the
newly inserted node as head */
void insert(struct node **head_ref, int data) {
// Allocate memory for new node
struct node *new_node = (struct node *) malloc (sizeof (struct node) );
new_node->data = data;

/* Since new node is being inserted at the begining, npx of new node
will always be XOR of current head and NULL */

/* If linked list is not empty, then npx of current head node will be XOR
of new node and node next to current head */
// *(head_ref)->npx is XOR of NULL and next. So if we do XOR of
// it with NULL, we get next
struct node* next = XOR((*head_ref)->npx, NULL);
}

}

// prints contents of doubly linked list in forward direction
void printList (struct node *head) {
struct node *prev = NULL;
struct node *next;

printf ("Following are the nodes of Linked List: \n");

while (curr != NULL) {
// print current node
printf ("%d ", curr->data);

// get address of next node: curr->npx is next^prev, so curr->npx^prev
// will be next^prev^prev which is next
next = XOR (prev, curr->npx);

// update prev and curr for next iteration
prev = curr;
curr = next;
}
}

// Driver program to test above functions
int main () {
/* Create following Doubly Linked List

// print the created list

return (0);
}
`````` 