xor linked list.c

/*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) whi\
ch 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 bet\
ween nodes and memory addresses.
*/
#include <stdlib.h>
#include <stdio.h>

struct Node {
  int value;
  unsigned int pnx;
};


unsigned int XOR(struct Node* a, struct Node* b){
  return  (unsigned int)a ^ (unsigned int)b;
}
struct Node* get_last_node(struct Node* root){

  struct Node* prev = NULL;
  struct Node* current = root;

  while(current != NULL){
    unsigned int next_addr = XOR(  (struct Node*) current->pnx, prev);
    prev = current;
    current = (struct Node*) next_addr;
  }

  return prev;
}

struct Node* insert_first(int value, struct Node* next){

  struct Node *node = (struct Node*) malloc(sizeof(struct Node));
  node->value = value;

  node->pnx = XOR(next, NULL);
  if(next != NULL){
    next->pnx = XOR( node, (struct Node*)next->pnx);
  }
  return node;
}

struct Node* insert_last(int value, struct Node* head){

  struct Node* last = get_last_node(head);

  struct Node *node = (struct Node*) malloc(sizeof(struct Node));
  node->value = value;
  last->pnx = XOR( (struct Node*) last->pnx, (struct Node*)node);
  node->pnx = XOR( NULL, last);

  return node;
}

int main(){

  struct Node* node = insert_first(10, NULL);
  insert_last(9, node);
  insert_last(8, node);
  insert_last(7, node);
  insert_last(6, node);
  insert_last(5, node);
  insert_last(4, node);
  struct Node* prev = NULL;
  struct Node* current = node;

  while(current != NULL){
    printf("%d, %u\n", current->value, current->pnx);
    unsigned int next_addr = XOR(  (struct Node*) current->pnx, prev);
    prev = current;
    current = (struct Node*) next_addr;
  }
  return 0;
}