XOR Linked List

It is a doubly linked list with an advantage of storage requirements than the previous by storing only one pointer. The pointer stores the XOR of the previous and the next node.

 ...  A        B         C         D         E  ...
         <–>  A⊕C  <->  B⊕D  <->  C⊕E  <-> 

For traverisng the list in the forward direction i.e. if you are in C and you need the address of D you can XOR the location of C with the location of B giving you the location of D.Similarly in the case of moving backward to get the location of B we can XOR the location of C and D. Notice however that we always need two locations to start traversing. Hence even though the storage requirements are reduced a number of fallbacks exist between this and the doubly linked lists.

The disadvantages of using a XOR linked list include :
1. Less space requirement increases code complexity
2. Garbage collection schemes wont work with data structures that donot contain literal pointers
3. XOR of pointers is not defined in some context as in C hence need to convert them to integers and store
4. Ability to delete a node knowing only the address of the node is not present
5. Ability to insert a node knowing only its address is not present

The program below shows a doubly linked list using a single pointer to the next node with add and display functions.

#include<iostream>
#include<cstdlib>
using namespace std;

struct Node {
 int data;
 unsigned int next;
}*start,*end,*newNode;

typedef struct Node NODE;

int menu(){
 int choice;
 cout << "1. Add" << endl;
 cout << "2. Display" << endl;
 cout << "3. Exit" << endl;
 cin >> choice;
 return choice;
}

void add(){
 newNode = (NODE *)malloc(sizeof(NODE));
 newNode->next = 0;
 cout << "Enter nodes data:" ;
 cin >> (newNode->data);
 if(start==NULL){
  start = end = newNode;
 }else{
  newNode->next = (unsigned int)end ^ 0;
  end->next = (end->next^0)^(unsigned int)newNode;
  end=newNode;
 }
}

void display(){
 NODE *temp,*curr,*prev;
 prev = curr = temp = NULL;
 for ( curr = start; curr != end ; temp = prev ,\
    prev = curr , curr = ( NODE * ) ( curr -> next ^ (unsigned int)temp ) )
       cout << curr -> data << endl;
    cout << curr -> data << endl;
}

int main()
{
 int choice;
 while(1){
  choice = menu();
  if(choice==3)
   break;
  switch(choice){
  case 1: add();break;
  case 2: display();break;
  }
 }
 return 0;
}