Normally, a doubly linked list requires two fields for previous and next pointers other than data field(s). An XOR list requires only one field with each node other than data field(s).

The idea is to store XOR of previous and next addresses in this field.

As XOR is a special kind of operation where if you XOR the answer with one of the numbers in question, you get the other number in question.

Example: If A XOR B = C then, A XOR C = B as well as, B XOR C = A

By using this property we can create an XOR list which requires only one field for addressing.

Consider a list as follows:

A -> B -> C -> D

Here, address variable (let's call it x_ptr) of each node will contain following information:

Node A: x_ptr = NULL XOR address(B)

Node B: x_ptr = address(A) XOR address(C)

Node C: x_ptr = address(B) XOR address(D)

Node D: x_ptr = address(C) XOR NULL

We can traverse this linked list in both forward and reverse directions. To get the next node we will require the address of previous node.

Example: Operations to traverse from A to D (We have Node A) are as follows :

B = NULL XOR A->x_ptr

C = A XOR B->x_ptr

D = B XOR C->x_ptr

Similarly, List can be traversed in backward direction.

Following Code Demonstrates the insertion and printing operations on XOR List:

#include <stdio.h>
#include <stdlib.h>

//Node Structure of XOR List
struct Node
{
  int data;
  struct Node *x_ptr;
};

//XOR Operation on addresses of two nodes
struct Node * xor(struct Node *m, struct Node *n)
{
  return (struct Node *)((unsigned)m ^ (unsigned)n);
}

//Inserting into XOR List from start of list
void insert(struct Node **head, int x)
{
  //Create a new node to be inserted 
  struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
  temp->data = x;

  //As it is inserted at beginning its x_ptr will (NULL XOR head)
  temp->x_ptr = xor(NULL,(*head));

  //If list is not empty then x_ptr of head will be (new node XOR next node)
  if((*head) != NULL)
  {
    //Get address of Next Node
    struct Node *nextNode = xor(NULL,(*head)->x_ptr);

    //Store XOR of new node and next node
    (*head)->x_ptr = xor(temp,nextNode);
  }

  //Make the new node as head
  *head = temp;
}

//Printing XOR List
void printList(struct Node *head)
{
  struct Node *previous, *current, *next;
  previous = NULL;
  current = head;

  while(current)
  {
    //print data of current node
    printf(" %d ",current->data);

    //get address of next node as (previous node XOR (previous XOR next node)) 
    //where current->x_ptr = (previous XOR next node)
    next = xor(previous,current->x_ptr);

    //update previous and current for next iteration
    previous = current;
    current = next;
  }

  printf("\n");
}

int main()
{
  /*Create doubly linked list as 10->20->30->40->50 */

  struct Node *head=NULL;
  insert(&head,50);
  insert(&head,40);
  insert(&head,30);
  insert(&head,20);
  insert(&head,10);

  //Print the XOR list
  printList(head);

  return 0;
}

Note: XOR of pointers is not defined by C/C++ standard so, above implementation may work on most of the platforms but not all platforms.

Thanks for reading!